社交網絡種子節點搜索算法

張 璐，蔡皖東，彭 冬

（1.西安市煙草專賣局，陜西 西安710061；2.西北工業大學 計算機學院，陜西 西安710072）

0 引 言

隨著Web2.0技術的發展，社交網絡已成為互聯網中非常流行的網絡應用[1]。目前，一些大規模在線社交網站，如Facebook的訪問量已經超過谷歌，成為美國第一大網站[2]。社交網站每天都有數百萬在線用戶，這包含著巨大潛在的商機，比如一些公司可以利用社交網站在線用戶來推銷他們的產品。

在社交網絡中，種子節點的影響力對推動信息傳播是非常重要的。一些通過病毒式市場營銷方式來推銷其產品、服務的公司或用戶對如何選擇具有影響力的種子節點懷有很大的興趣。比如A公司想在社交網站為其產品做廣告，由于廣告費用有限，只能投放K個用戶，A公司希望這些最初的用戶能夠喜歡其產品，并以他們作為種子節點，在社交網絡中以口碑相傳方式來影響他們的朋友，讓他們的朋友也喜歡其產品，而他們的朋友又通過社交網絡進一步影響更多的朋友，使更多的用戶都能喜歡其產品。A公司當然希望最初選擇的用戶 （即種子節點）都具有較大影響力，所影響的人數盡可能地多，從而花費少量的費用就可達到最大的廣告效益?？梢?，種子節點在網絡信息傳播過程中發揮了重要的作用，他們相當于意見領袖，通過他們的引導和影響，局部意見可能演化為網絡輿論。統計數據顯示，網絡中的大部分用戶不經常參與信息的制造與傳播，他們做出的決定往往跟隨意見領袖。有效地識別網絡意見領袖，通過意見領袖發表引導性信息來影響所在網絡用戶而非直接說服他們，可以有效地觸發整個網絡或社會的影響力，對于推動信息傳播，提高廣告效應具有重要的現實意義。

人們從不同角度研究了社交網絡意見領袖發現和識別問題，通過搜索社交網絡中影響力最大的種子節點來發現和識別意見領袖是其中的一種重要方法，并引起業界的關注和重視，將此類問題歸結為影響力最大化問題。

目前，影響力最大化算法主要分為兩類:復雜網絡算法，比如基于節點度和基于中心的算法等，這類算法存在的主要問題是所得到的種子節點影響力偏低；貪婪算法，其主要問題是計算效率較低、計算時間不穩定以及可擴展性較差等。

為了克服以上算法的不足，本文提出了一個新的啟發式貪婪算法，其主要特點是在部分度數高的節點中搜索種子節點并計算影響力，在不損失影響力的情況下，使計算效率有了較大提高。

1 相關工作

近年來，影響力最大化問題得到學者的廣泛關注和研究，比較有代表性研究成果如下。

文獻[3]提出了一種基于帖子內容分析的博客重要用戶分析方法ThreadRank，該方法通過分析大量的博客內容來判斷其用戶的重要性，需要耗費大量的時間用于內容清理和分析，效率較低。

文獻[4]提出一種意見領袖識別方法InfluenceRank，該方法根據與其他博客相比較來判斷用戶的重要性，以及這些用戶對整個網絡所做的貢獻來計算用戶權值，該文采用了余弦定理計算不同博客實體的相似性，復雜性較高，開銷大。

文獻[5]提出了一種Twitter網絡節點計算方法TwitterRank，該方法根據Twitter中的用戶關系、粉絲與關注者之間的分布以及在信息傳播的過程中各種用戶群體所起到的作用進行權重計算，該算法主要基于話題進行分析，召回率不高。

文獻[6]研究了如何對社會影響力進行定量分析，通過因子圖建模，提出了3種學習算法，但文中用到的LDA和因子圖降低了其效率。

文獻[7]根據社交網絡節點之間的交互信息和拓撲信息，利用線性回歸模型預測節點之間的影響力大小，結果表明交互信息其主導作用，拓撲信息作用較小。該方法僅利用了Facebook上的數據，結論是否適合于其他社交網絡待進一步驗證。

文獻[8]以Twitter為實驗對象，比較了基于粉絲數排序、基于微博轉發數排序和基于PageRank排序等3種影響力排序方法以及不同排序方法之間的相關性。

文獻[9]基于用戶發表話題的關注程度，對影響力進行度量和排序，但沒有與其它影響力排序方法進行比較。

文獻[10，11]從不同的角度，對PageRank方法進行擴展和改進，對用戶影響力進行度量和計算。但沒有從根本上克服PageRank方法自身的缺陷。

文獻[12]提出一個基于子模函數理論的優化貪婪算法 （cost－effective lazy forward selection，CELF），算法在部分影響力較大節點中搜索種子節點，由于搜索空間的減少，算法效率有了較大提高。實驗結果顯示，CELF算法得到的種子節點影響力與原始貪婪算法相同，而計算速度提高了近700倍，但對于大規模社交網絡，它的計算效率依然比較低。

文獻[13]提出一個新的貪婪算法 （new greedy），基本思想是在社交網絡圖中，以節點間影響因子p選擇相關邊，建立一個全新的子圖，然后選擇子圖中度數最大的節點作為種子節點，并且還提出一個MixGreedy算法，它分為兩部分:第一部分采用NewGreedy算法思想選取第一個種子節點；第二部分采用CELF算法思想選取余下種子節點。MixGreedy算法結合了NewGreedy算法和CELF算法的優點，其計算效率比CELF算法有所提高。由于在線性閾值模型中節點間并不以影響因子p來相互激活，MixGreedy算法需要從獨立級聯模型或帶權級聯模型中求得種子節點，再在線性閾值模型中計算它們的影響力，因此其影響力大小與其他貪婪算法有時相差較大，在線性閾值模型中可擴展性較差。

2 種子節點搜索算法

下面首先介紹經典貪婪算法，然后給出本文提出的算法。

在描述算法之前，定義σ（·）為影響力函數，S為種子節點集合，U為搜索節點集合。σ（S）是種子節點集合S的影響力，即集合S影響節點數目大小。

基于優化貪婪算法的種子搜索算法

定義1 如果對于任何元素x，y∈RK有f（x∨y）＋f（x∧y）≤f（x）＋f（y），則函數f:Rk→R是子模函數。

由定義1可以得出如下結論。

結論1:如果f是子模函數，則ABN，j∈N＼B，有f（A＋j）－f（A）≥f（B＋j）－f（B）。

由此可見，任何子模函數具有單調、非負等性質。

結論2:在獨立級聯模型、帶權級聯模型和線性閾值模型的任何一個實例中，影響力函數σ（·）是一個子模函數。

由結論2可知，隨著集合S的節點數目增多，集合U中所有節點的影響力都在逐漸減弱，具有單調遞減性。

為此，文獻[12]基于影響力具有子模函數的性質提出了CELF優化貪婪算法，它可分為兩個步驟:在第一個步驟中，算法計算所有節點影響力，選擇影響力最大的節點作為第一個種子節點加入到種子節點集合中；在第二個步驟中，算法選擇余下的種子節點，在每次選擇種子節點過程中，基于影響力具有子模函數性質的算法只計算部分影響力大的節點。

下面給出CELF算法的偽代碼:

基于啟發式貪婪算法的種子節點搜索算法

相比于原始貪婪算法，CELF算法的計算效率有了較大提高，但是在大規模社交網絡中搜索種子節點依然非常耗時。本節將首先分析社交網絡特征，然后給出改進算法。

為了使實驗條件相同，本文使用的數據集與文獻[13，14]中所用的數據集相同，均來源于論文共享網站arxiv（www.arxiv.org），其中網絡中的節點代表學者，邊代表學者間科研合作關系，而科研合作關系主要體現在論文合作方面。第一個科研合作網來自于 “高能物理理論”版塊，從1991年至2003年，用NetHEPT表示，它包含15233個節點和58891條邊。第二個科研合作網來自于 “物理學”版塊，用NetPHY表示，它包含37154個節點和231584條邊，本文將對此數據集進行分析，包括節點的度分布以及節點的度與影響力的關聯性。

對于節點的度與影響力的關聯性，上述兩種網絡選擇在獨立級聯模型中計算所有節點的影響力，分析度與影響力的關聯性，圖1給出了節點的度與影響力散點圖，其中橫坐標表示節點度大小，縱坐標表示節點的影響力均值。

圖1 獨立級聯模型中節點的度與影響力散點

由圖1可見，節點度數越高，影響力也就越大，但是在度數較大節點中影響力均值偏差較大，原因是由于度數較大節點數量少，個別節點的影響力對均值影響較大。比如在NetPHY中所有度數大于150的節點只有157個，其平均在每個節點度的分布約為2.5個，所以節點的度數與影響力存在著較強的關聯性。這也符合實際的社交網絡，比如在人際關系網中用戶的朋友關系越多，那么受他影響的人數一般也就越多，其深層次的原因是在社交網絡中邊是信息傳播的唯一路徑，度數高的節點連接著大量的邊，因而其影響的范圍相對也就較大。

節點的度呈冪律分布以及節點的度與影響力強關聯性說明，社交網絡存在著大量影響力較小的節點和少量影響力較大的節點，而在影響力最大化問題中種子節點具有較大影響力，大量影響力較小的節點，即度數低的節點，成為種子節點的概率非常低，可以考慮將它們排除在種子節點搜索范圍之外，從而縮小種子節點搜索的范圍。

基于以上分析，本文提出了一種新的啟發式貪婪算法－高節點度貪婪算法 （HD＿Greedy），算法描述如下:

該算法考慮了節點度數大小，其基本思想是在極小部分高度數節點中搜索種子節點，其過程分為兩個步驟:在第一個步驟中，算法首先輸入高度數節點占所有節點的百分比r，0＜r≤1，對所有節點按度數由大到小排序，選擇排序前r的節點形成新的節點集合，然后在新的節點集合中搜索種子節點，選擇其中影響力最大的節點作為第一個種子節點；在第二個步驟中，算法在新的節點集合中搜索余下種子節點，其方法與CELF算法在第二個步驟中的方法相似。

3 實驗結果及分析

下面的實驗將HD＿Greedy算法與其他經典算法進行對比分析，實驗包括各個算法分別在NetHEPT和NetPHY中得到的種子節點影響力以及計算時間。

所有實驗都在同一臺PC機上進行，其中CPU是Intel酷睿雙核E7200，主頻2.53GH，內存2G。由于當r＝1%時，高節點度貪婪算法性能最優，實驗將取r＝0.01的高節點度貪婪算法 （HD＿Greedy＿01）分別在獨立級聯模型、帶權級聯模型和線性閾值模型等3個不同信息傳播模型上與其它算法進行對比實驗，算法包括CELF算法、基于度的算法 （Degree）、NewGreedy算法和MixGreedy算法等。在下列各圖中，HD＿Greedy＿01表示選取r＝0.01的HD＿Greedy算法，Greedy表示CELF算法，Degree表示基于度的算法。獨立級聯模型的節點影響因子p取值與文獻[13，14]中一致，均為0.01。

種子節點的數目為50，取值與文獻[13，14]一致，另外，為了確保節點影響力的精確性，每個算法對節點的影響力計算20000次，取平均值作為節點最終影響力，以防止隨機概率引起的誤差。由于Degree算法在尋找種子節點過程中只選取度數最大的節點，不需計算節點的影響力，它的計算時間非常短，約為0.004秒，比其它算法快6個數量級以上，所以在各個算法的計算時間對比時，Degree算法不做比較。

獨立級聯模型實驗

圖2為各個算法在獨立級聯模型中的比較，其中縱坐標為影響力平均值，橫坐標為種子節點數目。由圖2可見，在NetHEPT和NetPHY中，HD＿Greedy＿01算法與Greedy、NewGreedy和MixGreedy這3個算法得到的種子節點影響力增長曲線幾乎重疊，而且最終的影響力相差不到1%，明顯高于Degree算法，尤其在NetPHY中，差值達到17%。這說明HD＿Greedy＿01算法得到的種子節點影響力與Greedy、NewGreedy和 MixGreedy三個算法相近，而明顯高于Degree算法。從圖2還可以看出，HD＿Greedy算法得到的種子節點影響力增長曲線與Greedy算法幾乎完全重疊，最終影響力相差很少，這說明所有種子節點幾乎都集中在部分度數較高的節點集合中，HD＿Greedy算法只在少部分高度數節點集合中搜索種子節點并不會損失種子節點影響力。

圖2 獨立級聯模型中不同算法影響力對比

圖3 為獨立級聯模型下的算法計算時間對比情況，時間單位為秒 （s）。從圖3可見，在NetHEPT和NetPHY中，HD＿Greedy＿01算法相對于Greedy算法計算時間分別縮短了75%和64%，效率大為提高，而且也明顯低于MixGreedy和NewGreedy算法的計算時間。實驗發現，在NetHEPT和NetPHY中，NewGreedy和MixGreedy算法計算時間不穩定，NewGreedy算法在NetPHY中的計算時間比Greedy算法快了近60%，而在NetHEPT中的計算時間甚至比Greedy算法還要慢，同樣的情況也出現在MixGreedy算法中，計算時間的不穩定性不利于算法的性能評估。HD＿Greedy＿01算法不但大大縮短了計算時間，而且具有良好的穩定性。因此，在獨立級聯模型的算法對比實驗中，HD＿Greedy＿01算法性能更好。

帶權級聯模型實驗

圖4 給出了各個算法在帶權級聯模型中的比較，其中縱坐標為影響力平均值，橫坐標為種子節點數目。

圖4 帶權級聯模型中不同算法的影響力對比

相比于獨立級聯模型，在帶權級聯模型中種子節點影響力增大，但 HD＿Greedy＿01算法與 Greedy、NewGreedy和MixGreedy這3個算法得到的種子節點影響力的增長曲線也幾乎是重疊的，各個貪婪算法最終的影響力大小差距也不大，不到1.5%。而Degree算法得到的種子節點影響力明顯不及貪婪算法，在NetHEPT和NetPHY中分別僅有貪婪算法的85.5%、62.3%。另外，隨著網絡節點數目增多，Degree算法得到的種子節點影響力與貪婪算法差距也在增大，這也說明Degree算法不適合在大規模社交網絡中求解種子節點影響力。

圖5是在帶權級聯模型下各個算法計算時間對比情況，時間單位為秒 （s）。從圖5可以看出，在NetHEPT中，HD＿Greedy＿01算法比Greedy算法的計算時間縮短了48.5%，而在NetPHY中計算時間縮短了55.6%。同時它還是速度最快的算法，比次快的MixGreedy算法在NetHEPT和NetPHY中分別快了44.5%和11.2%。NewGreedy算法的計算時間比較長，比Greedy算法還長，在NetHEPT中的計算時間是Greedy算法的244%，在NetPHY中則達到了275%。

圖5 帶權級聯模型中不同算法計算時間對比

線性閾值模型實驗

由于NewGreedy和MixGreedy算法是基于獨立級聯模型提出的，僅適應于獨立級聯模型和帶權級聯模型。為了擴展到線性閾值模型中，首先在獨立級聯模型和帶權級聯模型中用MixGreedy算法求得種子節點，然后在線性閾值模型中計算種子節點的影響力。為了便于比較，本文與文獻[14]的過程一致，其中 MixGreedyIc和 MixGreedyWc分別表示在獨立級聯模型和帶權級聯模型下MixGreedy算法得到的結果。

圖6是在線性閾值模型中不同算法得到的影響力情況，其中縱坐標為影響力平均值，橫坐標為種子節點數目。由圖6可見，在線性閾值模型中，HD＿Greedy＿01算法與Greedy算法的種子節點影響力增長曲線幾乎是重疊的，MixGreedyWc算法得到的種子節點影響力與它們的相差也很小。Degree算法在NetPHY中得到的種子節點影響力僅為Greedy算法的67.3%。值得一提的是，MixGreedyIc算法在NetPHY中得到的種子節點影響力與HD＿Greedy＿01、Greedy和MixGreedyWc這3個算法相差比較大，達到了23.9%，而在獨立級聯模型中MixGreedy算法得到的種子節點影響力與其它貪婪算法相差很小。這也從側面反映了MixGreedy算法在獨立級聯模型或帶權級聯模型中得到的種子節點并不能在線性閾值模型中得到很好的擴展。

圖6 線性閾值模型中不同算法的影響力對比

4 結束語

在不同信息傳播模型中，HD＿Greedy算法得到的種子節點影響力與其它貪婪算法接近，但計算效率有了較大提高。尤其在大規模較的社交網絡中，它的計算效率更高，這表明HD＿Greedy算法更適應于大規模社交網絡。雖然NewGreedy和MixGreedy算法得到的種子節點影響力與CELF算法非常接近，但存在著計算時間不穩定以及在線性閾值模型中可擴展性較差等問題。而Degree算法得到的種子節點影響力與所有貪婪算法相差較大。因此，在上述算法中，HD＿Greedy算法性能更優。

HD＿Greedy算法也有一些問題有待于進一步研究，比如如何確定高度數節點占所有節點的百分比r值使得算法具有最優的性能，r值設置過小，算法得到的種子節點影響力將受到損失；r值設置過大，算法的計算效率將大大降低；當r＝1時，它完全蛻變為CELF算法。r值的確定與許多參數是相關聯的，如社交網絡中節點數目及拓撲結構、信息傳播模型的影響因子大小以及種子節點數目等，還需要做進一步的研究。

本文針對CELF算法計算時間過長的問題，基于社交網絡節點的度呈冪律分布以及節點的度與影響力強關聯性，提出了HD＿Greedy算法，通過實驗表明，在不同的信息傳播模型中，HD＿Greedy算法在保證影響力不受損失情況下明顯提高了計算效率，并具有良好的計算時間穩定性和可擴展性。

[1]Nielsen Online Report.Social networks ＆blogs now 4th most popular online activity[EB／OL].http:／／tinyurl.com／cfzjlt，2009.

[2]http:／／news.xinhuanet.com／internet／2010－03／17／content＿1 3186 77.htm[OL].2010.

[3]Shinsuke Nakajima，Junichi Tatemura.Discovering important bloggers based on analyzing blog threads[C]／／WWW 2005 2nd Annual Workshop on the weblogging Ecosystem，2005.

[4]Song X，Chi Y，Hino K.Identifying opinion leaders in the blogosphere[C]／／ACM 978－1－59593－803－9／07／0011，2007.

[5]Weng J，Lim E P，Jiang J.Twitterrank:Finding topic－sensitive influential twitterers[C]／／Proc of the third ACM international conference on Web search and data mining，2010.

[6]Tang J，Sun J，Wang C，et al.Social influence analysis in large－scale networks[C]／／Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009.

[7]Gilbert E，Karahalios K.Predicting tie strength with social media[C]／／Proceedings of CHI，2009.

[8]Cha M，Haddadi H，Benevenuto F.Measuring user influence on twitter[C]／／ICWSM，2010.

[9]Leavitt A，Burchard E，Fisher D.The influentials:New approache for analyzing influence on twitter[EB／OL].http:／／www.twylah.com／stilescarrie／tweets／245590531631872，2012.

[10]Bakshy E，Hfman J，Mason W.Identifying influencers on twitter[EB／OL].http:／／thenoisychannel／2011／04／16／identifying－influencers－on－twitter／，2013.

[11]Lu L，Zhang Y C，Yeung C H.Leaders in social networks，the delicious case[J].PLoS ONE，2011，6 （6）.

[12]Leskovec J，Krause A，Guestrin C，et al.Cost－effective outbreak detection in networks[C]／／Proceedings of the 13th ACM SIGKDD Conference on Knowledge Discovery and Data Mining，2007:420－429.

[13]Wei Chen，Yajun Wang，Siyu Yang.Efficient influence maximization in social networks.To insert individual citation into a bibliography in a word－processor，select your preferred citation style below and drag－and－drop it into the document[C]／／Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009:199－208.

[14]Kimura M，Saito K.Tractable models for information diffusion in social networks[C]／／Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases，2006:259－271.