社交網(wǎng)絡種子節(jié)點搜索算法

張 璐，蔡皖東，彭 冬

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

0 引 言

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

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

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

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

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

1 相關工作

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

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

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

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

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

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

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

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

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

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

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

2 種子節(jié)點搜索算法

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

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

基于優(yōu)化貪婪算法的種子搜索算法

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

由定義1可以得出如下結(jié)論。

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

由此可見，任何子模函數(shù)具有單調(diào)、非負等性質(zhì)。

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

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

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

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

基于啟發(fā)式貪婪算法的種子節(jié)點搜索算法

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

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

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

圖1 獨立級聯(lián)模型中節(jié)點的度與影響力散點

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

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

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

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

3 實驗結(jié)果及分析

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

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

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

獨立級聯(lián)模型實驗

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

圖2 獨立級聯(lián)模型中不同算法影響力對比

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

帶權(quán)級聯(lián)模型實驗

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

圖4 帶權(quán)級聯(lián)模型中不同算法的影響力對比

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

圖5是在帶權(quán)級聯(lián)模型下各個算法計算時間對比情況，時間單位為秒 （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 帶權(quán)級聯(lián)模型中不同算法計算時間對比

線性閾值模型實驗

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

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

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

4 結(jié)束語

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

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

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

[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，F(xiàn)isher 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.