[發(fā)明專(zhuān)利]一種基于圖形處理單元的影響最大化并行加速方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210248732.3
• 申請(qǐng)日: 2012-07-18
• 公開(kāi)（公告）號(hào): CN102819664B
• 公開(kāi)（公告）日: 2015-02-18
• 發(fā)明（設(shè)計(jì)）人: 李?yuàn)檴?/a>;廖湘科;劉曉東;吳慶波;戴華東;彭紹亮;王蕾;付松齡;魯曉佩;鄭思
• 申請(qǐng)（專(zhuān)利權(quán)）人: 中國(guó)人民解放軍國(guó)防科學(xué)技術(shù)大學(xué)
• 主分類(lèi)號(hào): G06T1/20
• 分類(lèi)號(hào): G06T1/20
• 代理公司: 國(guó)防科技大學(xué)專(zhuān)利服務(wù)中心 43202
• 代理人: 郭敏

技術(shù)領(lǐng)域

本發(fā)明涉及海量數(shù)據(jù)挖掘領(lǐng)域中社會(huì)網(wǎng)絡(luò)影響最大化問(wèn)題的解決方法，尤 其指針對(duì)大規(guī)模社會(huì)網(wǎng)絡(luò)的海量用戶挖掘，提出的一種基于圖形處理單元GPU 的并行加速方法。

背景技術(shù)

Web2.0技術(shù)的快速發(fā)展推動(dòng)了社會(huì)媒體的蓬勃發(fā)展。各類(lèi)社交網(wǎng)站不斷 涌現(xiàn)，例如國(guó)外的Facebook、Twitter以及國(guó)內(nèi)的人人網(wǎng)、新浪微博等網(wǎng)站用戶 數(shù)量增長(zhǎng)十分迅速，當(dāng)前Facebook的活躍用戶已經(jīng)超過(guò)了8.5億。社交網(wǎng)站不 僅是人們溝通和交流的橋梁，同時(shí)還成了信息傳播和擴(kuò)散的重要媒介。研究表 明，68%的顧客會(huì)在購(gòu)買(mǎi)產(chǎn)品之前詢問(wèn)其家人、朋友的意見(jiàn)。病毒式營(yíng)銷(xiāo)（Viral? Marketing）正是利用了用戶之間口碑傳播的原理，進(jìn)行品牌推廣等網(wǎng)絡(luò)傳銷(xiāo)方 法。而且隨著社會(huì)網(wǎng)絡(luò)用戶的持續(xù)快速增長(zhǎng)，病毒式營(yíng)銷(xiāo)已經(jīng)成為一種十分高 效的信息傳播方式。

影響最大化問(wèn)題是社會(huì)網(wǎng)絡(luò)分析中關(guān)于影響傳播的經(jīng)典問(wèn)題。設(shè)想如下場(chǎng) 景：一家公司要進(jìn)行新產(chǎn)品推廣，其推廣策略是：選擇K名顧客免費(fèi)試用新產(chǎn) 品，之后利用這K名顧客對(duì)產(chǎn)品的宣傳推廣和影響傳播吸引更多的顧客購(gòu)買(mǎi)新 產(chǎn)品，從而達(dá)到利益最優(yōu)的目的。影響最大化問(wèn)題可以形式化描述為：對(duì)于社 會(huì)網(wǎng)絡(luò)圖G＝(V，E，W)，其中V＝{v₀，v₁，...，v_n-1}是節(jié)點(diǎn)集合，V中節(jié)點(diǎn)個(gè)數(shù) 為n；E是節(jié)點(diǎn)集合V中節(jié)點(diǎn)之間的有向邊集合，即E中有向邊的條 數(shù)為m；W是G中節(jié)點(diǎn)權(quán)重的集合，表征了各節(jié)點(diǎn)的影響力（初始值設(shè)定為1， 即僅能影響節(jié)點(diǎn)自身）。給定網(wǎng)絡(luò)圖G和初始活躍節(jié)點(diǎn)集合中的節(jié)點(diǎn)個(gè)數(shù)K，影 響最大化問(wèn)題是從節(jié)點(diǎn)集合V中選擇最佳的K個(gè)節(jié)點(diǎn)作為初始活躍節(jié)點(diǎn)集合S， 通過(guò)影響傳遞，使得影響擴(kuò)散的最終范圍最大。影響最大化問(wèn)題的核心在于如 何定位網(wǎng)絡(luò)中最有影響力的K名成員，即網(wǎng)絡(luò)中的意見(jiàn)領(lǐng)袖，從而通過(guò)病毒式 營(yíng)銷(xiāo)使得最終被影響的用戶數(shù)目最大。影響最大化問(wèn)題的研究不僅對(duì)市場(chǎng)營(yíng)銷(xiāo) 有著十分重要的現(xiàn)實(shí)意義,同時(shí)還對(duì)輿情預(yù)警、疫情發(fā)現(xiàn)等方面有著十分重要 的應(yīng)用。自從Pedro?Domingos和Matt?Richardson于2001年ACM?SIGKDD會(huì) 議公布的文章Mining?the?network?value?ofcustomers中提出影響最大化問(wèn)題后， 該問(wèn)題受到了越來(lái)越多研究者的關(guān)注。David?Kempe等人在2003年ACM SIGKDD會(huì)議公布的文章Maximizing?tte?Spread?of?Influence?through?a?Social? Network中證明了影響最大化問(wèn)題隸屬于NP-Hard問(wèn)題，并且提出了一種爬山 貪心算法來(lái)獲得近似最優(yōu)解。雖然爬山貪心算法可以達(dá)到1-1／e的最優(yōu)逼近（e 是自然對(duì)數(shù)底），但是由于David?Kempe采用多次的蒙特卡洛模擬（例如20000 次）來(lái)計(jì)算各個(gè)節(jié)點(diǎn)的影響值，因此需要消耗大量時(shí)間，而且無(wú)法擴(kuò)展應(yīng)用到 大規(guī)模的網(wǎng)絡(luò)中。

很多研究人員都致力于設(shè)計(jì)新的方法來(lái)解決影響最大化的效率問(wèn)題。爬山 貪心算法中的核心問(wèn)題在于需要多次蒙特卡洛模擬以計(jì)算所有節(jié)點(diǎn)的影響值。 為了解決該問(wèn)題，Jure?Leskovec等人在ACM?SIGKDD2007中公布的文章 Cost-effective?Outbreak?Detection?in?Networks中根據(jù)影響擴(kuò)散函數(shù)的半模特性 設(shè)計(jì)了新的優(yōu)化方法CELF，可以很大程度地降低蒙特卡洛模擬的計(jì)算量，從 而減少了計(jì)算時(shí)間。之后，Wei?Chen等人在ACM?SIGKDD2009中公布文章 Efficient?Influence?Maximization?in?Social?Networks，文章中提出了目前最優(yōu)的貪 心算法MixGreedy。該算法的改進(jìn)在于在每次蒙特卡洛模擬時(shí)為網(wǎng)絡(luò)中所有節(jié) 點(diǎn)計(jì)算影響值，因而進(jìn)一步降低了算法的復(fù)雜度。同時(shí)MixGreedy整合了CELF 算法，大大降低了算法執(zhí)行時(shí)間。然而由于影響最大化計(jì)算復(fù)雜度很高，即使 目前最優(yōu)的MixGreedy算法在處理大規(guī)模社會(huì)網(wǎng)絡(luò)時(shí)仍然十分耗時(shí)；例如從 37154個(gè)社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)中選擇50個(gè)最有影響用戶就需要2個(gè)小時(shí)以上。因此， 如何從大規(guī)模社會(huì)網(wǎng)絡(luò)海量用戶中快速挖掘最有影響用戶成為了亟待解決的問(wèn) 題。