張 璐，蔡皖東，彭 冬

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

0 引 言

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

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

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

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

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

1 相關(guān)工作

近年來(lái)，影響力最大化問(wèn)題得到學(xué)者的廣泛關(guān)注和研究，比較有代表性研究成果如下。

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

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

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

文獻(xiàn)[6]研究了如何對(duì)社會(huì)影響力進(jìn)行定量分析，通過(guò)因子圖建模，提出了3種學(xué)習(xí)算法，但文中用到的LDA和因子圖降低了其效率。

文獻(xiàn)[7]根據(jù)社交網(wǎng)絡(luò)節(jié)點(diǎn)之間的交互信息和拓?fù)湫畔?，利用線性回歸模型預(yù)測(cè)節(jié)點(diǎn)之間的影響力大小，結(jié)果表明交互信息其主導(dǎo)作用，拓?fù)湫畔⒆饔幂^小。該方法僅利用了Facebook上的數(shù)據(jù)，結(jié)論是否適合于其他社交網(wǎng)絡(luò)待進(jìn)一步驗(yàn)證。

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

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

文獻(xiàn)[10，11]從不同的角度，對(duì)PageRank方法進(jìn)行擴(kuò)展和改進(jìn)，對(duì)用戶影響力進(jìn)行度量和計(jì)算。但沒(méi)有從根本上克服PageRank方法自身的缺陷。

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

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

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

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

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

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

定義1 如果對(duì)于任何元素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）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

獨(dú)立級(jí)聯(lián)模型實(shí)驗(yàn)

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

圖2 獨(dú)立級(jí)聯(lián)模型中不同算法影響力對(duì)比

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

帶權(quán)級(jí)聯(lián)模型實(shí)驗(yàn)

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

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

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

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

圖5 帶權(quán)級(jí)聯(lián)模型中不同算法計(jì)算時(shí)間對(duì)比

線性閾值模型實(shí)驗(yàn)

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

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

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

4 結(jié)束語(yǔ)

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

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

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

[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.