基于前驅后繼節(jié)點的社會網(wǎng)絡影響最大化算法

覃 俊，易金莉

(中南民族大學 計算機科學學院，武漢 430074)

基于前驅后繼節(jié)點的社會網(wǎng)絡影響最大化算法

覃 俊，易金莉

(中南民族大學 計算機科學學院，武漢 430074)

針對社會網(wǎng)絡影響最大化問題，基于挖掘“潛在影響力”節(jié)點的策略并結合貪心算法可有效降低問題復雜度，綜合考慮了節(jié)點與其前驅后繼節(jié)點的相互影響，對“潛在影響力”進行了重新定義，基于線性閾值模型提出了基于前驅及后繼節(jié)點的影響最大化算法．實驗結果表明：與目前的同類算法相比，該算法具有更好的信息擴散范圍．

影響最大化；潛在影響力；前驅后繼節(jié)點

社會網(wǎng)絡是關于社會實體如個人、團體或組織之間關系的網(wǎng)絡．隨著對社會網(wǎng)絡中大規(guī)模數(shù)據(jù)宏觀和微觀擴散的可用性認知的不斷增強，信息、產(chǎn)品等如何在社會網(wǎng)絡中傳播方面的研究受到越來越多的關注[1]．信息在社會網(wǎng)絡中通過節(jié)點之間的影響從一個節(jié)點傳播到另一個節(jié)點，查找社會網(wǎng)絡中最具影響力的節(jié)點，對于研究社會學和“病毒式營銷”[2]等而言是一個重要的課題．

結合上述“潛在影響力”一類方法，本文根據(jù)信息在網(wǎng)絡中擴散的動態(tài)性，基于LT模型，綜合考慮節(jié)點與其前驅和后繼節(jié)點之間的相互影響，優(yōu)化“潛在影響力”節(jié)點的選取策略，結合貪心策略提出了基于前驅后繼節(jié)點的社會網(wǎng)絡影響最大化算法(PSH)，并選取多個真實的社會網(wǎng)絡數(shù)據(jù)集對本方法進行了驗證．

1 背景知識

1.1 LT模型

LT模型中，對于一個表示社會網(wǎng)絡的有向圖，任一節(jié)點v初始時分配[0,1]范圍內的閾值θv，邊(w,v)分配權重bwv，對應節(jié)點w對節(jié)點v的影響力，且所有指向v的邊的權重滿足：

(1)

其中pre(v)表示節(jié)點v的直接前驅節(jié)點集合．若所有已激活鄰節(jié)點對v的影響力之和大于或等于閾值，即：

(2)

則節(jié)點v被激活．其中aPre(v)表示節(jié)點v已激活的直接前驅節(jié)點．LT模型下，對于給定的初始節(jié)點集合，最終的擴散范圍是確定的．

1.2 相關工作

基于挖掘“潛在影響力”節(jié)點的方法通常都是結合貪心策略的混合式算法，即首先啟發(fā)式地選擇一部分具有潛在影響力的節(jié)點，然后使用貪心策略選取當前最具影響力的節(jié)點，在前一階段的基礎上，網(wǎng)絡圖中部分節(jié)點已被激活，因此本階段計算規(guī)模顯著降低，效率和效果都大大提升．相關工作如下：

1)爬山貪心算法[5].每一步選擇使得當前影響范圍最大的節(jié)點，定義：

m(v|Si-1)=|I(Si-1∪{v})|-|I(Si-1)|.

(3)

其中I(Si-1)表示Si-1節(jié)點集合能激活的節(jié)點個數(shù)，m(v|Si-1)表示節(jié)點v相對于Si-1產(chǎn)生的影響范圍增量．

2)混合式影響最大化算法(HPG).田家堂等人[9]首次提出基于挖據(jù)“潛在影響力”節(jié)點的方法，利用節(jié)點的度數(shù)和節(jié)點對其未激活直接后繼節(jié)點的影響力之和來選取潛在影響力節(jié)點，結合HCG提出了HPG算法．

3)基于閾值的影響最大化算法(TBH).陳浩等人[10]基于HPG，考慮節(jié)點閾值的變化和節(jié)點之間的影響共同決定節(jié)點的潛在影響力．定義：

(4)

p(u,v)為u對v的影響，值為1表示u能激活v，其中θvt表示u在t時刻的閾值.

(5)

2 基于前驅后繼節(jié)點的影響最大化算法

2.1 現(xiàn)有問題分析

前期研究者在選取潛在影響力節(jié)點時僅考慮節(jié)點對其直接后繼節(jié)點的影響，忽略了該節(jié)點對更多層級后繼節(jié)點可能存在的影響．此外，前驅節(jié)點的累積影響決定著該節(jié)點自身是否更易被激活，這種情形也未見討論．雖然基于局部結構的方案復雜度較低，但潛在影響力的輻射范圍有局限．本文針對以上缺陷，對“潛在影響力”的度量方法進行改進，在選取種子節(jié)點時，同時考慮節(jié)點與其前驅后繼節(jié)點間的相互影響，即自身不易被激活，但激活后對其后繼節(jié)點能產(chǎn)生更大影響的節(jié)點，據(jù)此提出了基于前驅后繼節(jié)點影響最大化算法．

本文提出的方法對有向圖和無向圖均適用，下面主要針對有向圖進行分析，無向圖的處理方式見3.3節(jié)．

2.2 潛在影響力分析

2.2.1 對多級后繼節(jié)點的影響

潛在影響力旨在積累更多的潛在影響，即對更多的節(jié)點產(chǎn)生影響(激活或使其閾值減小)．若某節(jié)點在t時刻被激活，則該節(jié)點會直接或間接地影響其后繼節(jié)點，這種間接的影響同樣應該在該節(jié)點的影響范圍內，即潛在影響力為節(jié)點對其后繼節(jié)點產(chǎn)生的直接或間接影響力的累加：

(6)

(6)式的解釋需考慮以下兩種情況：

1) 計算u的潛在影響力時，不僅需要計算u對其直接后繼節(jié)點v的影響，同時需要考慮這些v節(jié)點的潛在影響力，以此類推．如圖1(a)(深色圓圈表示已激活節(jié)點，下同)，在計算節(jié)點u的潛在影響力時，若有buv3≥θv3t，則若在當前時刻激活節(jié)點u，節(jié)點v3會在下一時刻受u的影響而被激活，v3繼而影響其自身的未激活的后繼節(jié)點．

(a) 多級后繼傳播 (b) 不同路徑傳播圖1 對直接和間接后繼節(jié)點的影響Fig.1 Influence on direct and indirect successor nodes

2) 計算u的潛在影響力時，需要考慮其經(jīng)不同路徑對同一后繼節(jié)點的影響．如圖1(b)，若θu=θv1=θv2=0.5，buv1=0.2，buv2=0.5，bv2v1=0.3，則在當前時刻節(jié)點u對節(jié)點v1的影響不足以將其激活，而u可以將v2激活，之后v2對v1的影響與u之前對v1的影響兩者累加后能夠將v1激活，v1繼續(xù)對自身的后繼節(jié)點產(chǎn)生影響．

2.2.2 受前驅節(jié)點的影響

節(jié)點受其前驅節(jié)點的累積影響越大，該節(jié)點被激活的概率越大，而在初始節(jié)點選取時，應考慮自身不易被激活的節(jié)點．因此基于(6)式，將前驅節(jié)點對自身的影響考慮在內，根據(jù)前驅節(jié)點的影響力大小，對PI“打折”，消除前驅節(jié)點的影響：

(7)

其中aPre(u)表示節(jié)點u已激活的直接前驅節(jié)點．

(7)式相關解釋如圖2，根據(jù)(6)式若有PI(u1)=PI(u2)且PI(u2)=PI(u3)，節(jié)點u1存在已激活的直接前驅節(jié)點w2．LT模型下w2對u1的影響持續(xù)保留直至u1被激活．因此可以認為，相較于u2、u3而言，u1更易受其他節(jié)點的影響而被激活．

圖2 直接前驅節(jié)點激活狀態(tài)對比Fig.2 Comparison of direct previous nodes′ active status

綜上，同時考慮節(jié)點對其后繼節(jié)點產(chǎn)生的直接或間接影響，以及前驅節(jié)點對節(jié)點本身影響的積累，結合(6)、 (7)式提出節(jié)點潛在影響力計算方法為：

(8)

環(huán)路的考慮：由PI的定義可以看出，網(wǎng)絡圖中存在環(huán)時，可能會出現(xiàn)PI值循環(huán)迭代相加的情況．為避免這種問題，可標記節(jié)點是否受到影響而激活，若是，則接下來的計算過程中若再次訪問到該節(jié)點，不再對其PI值進行累加．

2.3 算法框架

根據(jù)以上分析，參考文獻[9,10]基于潛在影響力一類方法的框架，這里給出PSH的算法描述．首先啟發(fā)式選擇PI值大的一部分節(jié)點，再用貪心策略選取剩余部分節(jié)點，其中僅PI值計算發(fā)生變化．為增強可比性，啟發(fā)因子c∈[0,1]含義不變，1-c表示通過潛在影響力選取節(jié)點所占的比例．

輸入：圖G=(V,E)，初始節(jié)點集合大小k，啟發(fā)因子c.

輸出：初始節(jié)點集S(|S|=k)，激活節(jié)點個數(shù).

1) 根據(jù)(8)式計算所有節(jié)點的PI值；

2) 選擇PI值最大的節(jié)點放入S，基于S進行一輪激活并計數(shù)，更新未激活節(jié)點的PI值，重復此步驟k-「ck?次；

3) 根據(jù)(3)式計算每個未激活節(jié)點的影響范圍增量，選擇當前能產(chǎn)生最大影響范圍增量的節(jié)點放入S，基于S進行一輪激活并計數(shù)，重復此步驟「ck?次．

2.4 算法復雜度分析

對于圖G=(V,E)，記節(jié)點個數(shù)|V|，啟發(fā)階段PI值的計算為常數(shù)時間，選取PI值最大的節(jié)點的時間復雜度為O(|V|)．相較于TBH，時間差主要在PI值的計算上．實際傳播過程中，節(jié)點對其后繼節(jié)點的直接或間接影響級數(shù)較小，因此PSH相較于TBH時間復雜度略高．考慮離線狀態(tài)下時間性能要求不高，因此可以接受．

3 實驗

3.1 實驗設計

在同一平臺下進行實驗驗證，選取LT模型作為信息擴散模型．θv均取0.5[5]，權值bwv的處理參考文獻[9,10]．

1-c表示通過潛在影響力選取的節(jié)點個數(shù)占目標節(jié)點個數(shù)k的比例．c=0即僅考慮潛在影響力對結果的影響；c=1時初始節(jié)點全都由貪心策略選取，此時PSH與TBH退化為HCG；c∈(0,1)時，通過潛在影響力選取k-「ck?個節(jié)點，通過貪心策略選取「ck?個節(jié)點．實驗設計如下：①僅考慮潛在影響力因素，即c=0時，與TBH比較，對比兩種潛在影響量化標準，與HCG比較，分析潛在影響力因素下的最終擴散效果；②潛在影響力所占比例c∈(0,1)對結果的影響，同樣與TBH、HCG比較，分別對比潛在影響的累積效果和對最終擴散結果的影響．

3.2 實驗數(shù)據(jù)集

本方法選取3個常用的真實數(shù)據(jù)集進行實驗驗證，數(shù)據(jù)集分別來源于Stanford大學大型網(wǎng)絡數(shù)據(jù)集和Geom lib基礎幾何數(shù)據(jù)庫[9]，如表1.

表1 數(shù)據(jù)集基本信息

Wiki_vote數(shù)據(jù)集是Wikepedia的投票歷史網(wǎng)絡，有向無權圖．節(jié)點代表Wikipedia的用戶，有向邊(u,v)表示u給v投票．

Facebook數(shù)據(jù)集記錄了Facebook應用用戶的社交信息，節(jié)點代表該應用用戶，無向邊(u,v)表示用戶u、v為好友關系，無向無權圖．

Geom數(shù)據(jù)集代表計算幾何合著社會網(wǎng)絡，記錄作者之間合作關系的無向帶權圖．節(jié)點代表作者，無向邊(u,v)代表作者u與v之間的合作，邊的權值表示合作次數(shù)．

3.3 無向圖的處理

對于無向圖，若節(jié)點u、v之間存在邊，則認為u、v之間存在相互影響，加入由u指向v的有向邊(u,v)和由v指向u的有向邊(v,u)，分別表示u對v的影響和v對u的影響．

3.4 實驗結果

3.4.1 無向無權圖上的實驗結果

僅考慮潛在影響力對結果的影響．選取無向無權網(wǎng)絡數(shù)據(jù)集2驗證PSH的性能，見表2．

表2 Facebook數(shù)據(jù)集上影響范圍對比

1)比較兩種潛在影響力的影響范圍．k取不同值時PSH相較于TBH均具有更好的激活范圍．這是因為在計算潛在影響力時，PSH相對于TBH而言考慮了節(jié)點更多層級之間的結構關系，而非單層的局部結構，即PSH選取的是對更多節(jié)點具有潛在影響的節(jié)點．

2)僅用潛在影響力選取節(jié)點的擴散結果．與HCG相比，k≤40時，PSN擴散效果較差，k≥50時，PSH激活范圍顯著提升，這是因為PSH需要一個潛在影響的累積過程，才能使后續(xù)擴散過程中更多的節(jié)點更易被激活．

3.4.2 有向無權圖上的實驗結果

考慮潛在影響力所占比例對結果的影響，選取數(shù)據(jù)集1驗證PSH在有向無權圖上的性能．

1)比較不同潛在影響的積累產(chǎn)生的不同結果．考慮c的大小，k取定值80，PSH與TBH擴散效果對比如表3，PSH均表現(xiàn)出較TBH更好的激活效果，驗證了3.4.1的實驗結論，即PSH的潛在影響力量化標準較TBH更優(yōu)．隨著c值增大，通過潛在影響力選取的節(jié)點所占比例減小而貪心策略選取的節(jié)點較多，兩者激活范圍差距隨之減小．

表3 k=80時，Wiki_vote數(shù)據(jù)集上不同c值下的比較Tab.3 Comparison based on dataset Wiki_vote under different c when k=80

2)討論潛在影響所占比例對結果的影響．同時考慮c,k，PSH與HCG擴散效果如表4.c=0.4時PSH相較于HCG(即c=1)具有更好的激活范圍，也就是說當潛在影響力比重較大而貪心策略比重較小時，PI的潛在影響積累使得更多的節(jié)點更易被激活，PSH可以達到比HCG更好的結果，且隨著k增大，優(yōu)勢越明顯．另外，PSH每一步只需更新受影響節(jié)點的PI值，而HCG則需要計算所有未激活節(jié)點的影響范圍增量，因此PSH運行時間更短．

表 4 Wiki_vote數(shù)據(jù)集上不同k和c的影響范圍對比

3.4.3 無向帶權圖上的實驗結果

為了驗證PSH算法在帶權網(wǎng)絡上的有效性，選取數(shù)據(jù)集3進行同樣的實驗．同時考慮k、c的變化，驗證不同潛在影響力的積累對結果的影響．如表5，k≥40，c取不同值，隨著k值的增大，PSH均表現(xiàn)出較TBH更優(yōu)的擴散效果．PSH相較于TBH考慮的是范圍更廣的鄰節(jié)點結構，因此需要更多的節(jié)點來累積潛在影響，如k≤30時，擴散效果會出現(xiàn)較TBH差的情況，此時k值較小，但隨著k值的增大，PSH優(yōu)勢越明顯．

表 5 Geom數(shù)據(jù)集上不同k和c的影響范圍對比

同樣，c=0.4即c較小時，PSH激活范圍超過HCG，驗證了3.4.2的結論．

綜上，PSH中改進的潛在影響力量化標準在大多數(shù)情況下的擴散效果都較TBH好，僅當k值較小時，由于PSH需要更多的節(jié)點來累積潛在影響，可能出現(xiàn)擴散效果較差的結果；此外，c值較小時，PSH就能達到較HCG更好的擴散效果且運行時間更短，k值越大，優(yōu)勢越顯著．

4 結語

本文基于線性閾值模型，提出了基于前驅后繼節(jié)點的影響最大化算法，實驗結果表明：相較于基于閾值的影響最大化算法，我們的算法在大部分情況下具有更好的擴散范圍；通過潛在影響力選取的節(jié)點比例較大時，我們的算法能達到比爬山貪心算法更好的擴散效果，運行時間也更優(yōu)．

本文對社會網(wǎng)絡影響最大化問題進行了探究，提出的算法雖然在時間復雜度上比同類算法略高，但擴散效果明顯較好．另外，本算法存在進一步改進的空間，如初始節(jié)點集要求較小時，由于潛在影響的累積較少，本算法擴散效果可能較差；還有，節(jié)點閾值不同的情況下，算法的適用性研究等，這些工作有待后期深入研究．

[1] Rodriguez M G, Song L. Diffusion in social and information networks: research problems, probabilistic models and machine learning methods[C]//ACM. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2015: 2315-2316.

[2] Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//ACM. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 1029-1038.

[3] Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing[C]// ACM. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2002: 61-70.

[4] Kemple D, Kleinberg J, Tardos E. Maximizing the spread of influence in a social network[C]// ACM. Proceeding of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003: 137-146.

[5] Kemple D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network[J]. Theory of Computing, 2015, 11(4): 105-147.

[6] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]// ACM. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 420-429.

[7] Goyal A, Lu W, Lakshmanan L V S. Celf++: optimizing the greedy algorithm for influence maximization in social networks[C]// ACM. Proceedings of the 20th International Conference Companion on World Wide Web. New York: ACM, 2011: 47-48.

[8] Chen W,Wang Y,Yang S. Efficient influence maximization in social networks[C]// ACM. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM,2009: 199-208.

[9] 田家堂,王軼彤,馮小軍. 一種新型的社會網(wǎng)絡影響最大化算法[J]. 計算機學報，2011,34(10): 1956-1965.

[10] 陳 浩 王軼彤. 基于閾值的社交網(wǎng)絡影響力最大化算法[J]. 計算機研究與發(fā)展，2012,49(10): 2181-2188.

Previous and Successor Nodes-Based Heuristic Algorithm for Influence Maximization

Qin Jun, Yi Jinli

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

Strategies based on mining “potential influence” nodes combined with Greedy Algorithm could effectively reduce the complexity of the influence maximization problem for social networks. In this paper, we redefined “potential influence” by considering the interaction influence between nodes and their previous and successor nodes, and proposed the Previous and Successor Nodes-Based Heuristic Algorithm for Influence Maximization based on linear threshold model. Experimental results demonstrate that our algorithm significantly outperforms the similar algorithms in information diffusion.

influence maximization; potential influence; previous and successor node

2016-09-05

覃 俊(1968-)，女，教授，博士，研究方向：智能優(yōu)化、數(shù)據(jù)挖掘，E-mail：498011695@qq.com

國家民委基金資助項目(2015BAD29B00)

TP311

A

1672-4321(2016)04-0095-06