基于拓撲勢的影響力最大化算法

2020-04-24 03:07:40王秀芳牛煒南孫承愛仇麗青

計算機工程與設計 2020年3期

王秀芳，牛煒南，孫承愛，仇麗青

(山東科技大學計算機科學與工程學院，山東青島 266510)

0 引言

近年來，很多大型社交網絡不斷涌現，人們可以通過微信，qq和微博等社交網絡獲取有價值的信息。于是，商家趨向于在社交網絡上發布廣告信息，讓信息通過社交網絡傳播的更廣。例如，商家在想要推銷一款產品時，首先選擇一些有影響力的人來接受它們，讓他們推薦給自己的朋友，朋友的朋友，依次影響更多的人購買這款產品，這就是“口碑效應”。最近比較流行一種職業-美妝博主，他們通過在線試妝，根據用戶的要求試該產品，然后分析其產品的優點，推薦該產品，使得很多人對此產品滿意，主動去搶購該產品，最終使得產品庫存不足，那么，這些商家如何選擇合適的美妝博主為他們試妝，使得產品推廣的更好，這就是“影響力最大化問題”。當然，社交網絡中的影響力最大化問題還有很多其余的應用。比如，職業路徑的預測。用戶根據自己的基本信息，提取到人生的各個階段中最具影響力的因素和特征，從而預測未來可能從事的職業。這樣對自己的人生規劃有著重要的意義。

IMP(influence maximization problem)作為數學優化問題解決的第一個模型是由Kempe等建立的，驗證了影響力最大化問題是一個NP問題，提出運用貪心算法和Monte Carlo模擬解決該問題，然而貪心算法的時間復雜度高，不適合大型社交網絡。為了提高算法的運行時間，一系列啟發式算法被研究者們相繼提出。然而，啟發式算法在準確率方面還有待提高。研究發現，貪心階段和啟發階段相結合的綜合型算法可以適當均衡影響力和運行時間，這是最近的研究熱點。拓撲勢理論[1]首次在物理學中提出，近年來被應用到社交網絡中用來衡量節點重要性，并取得了一定的效果。

因此，為了均衡運行時間和影響力，從而更有效解決影響力最大化問題，本文提出了一種基于拓撲勢的影響力最大化算法，TSH(topology-stage-heuristic)算法。首先，啟發式階段：基于拓撲勢理論，識別“山峰”，“山谷”和“斜坡”節點，選擇“山峰”和“斜坡”節點作為候選種子集。然后，貪心階段：使用CELF算法[2]從候選種子集中選擇最優種子集。

1 相關研究

影響力最大化問題被Kempe等提出后，因為其廣泛的應用，得到了研究者們極大的關注。目前，研究者對此問題的解決方法可以歸納為兩類：貪心算法和啟發式算法。

自從Richardson和Domingos等[1]將影響力最大化問題歸納為算法問題后，Kempe等[2]提出了貪心算法來解決此問題。貪心算法需要重復計算節點的影響增益，然后選擇影響力增益最大的節點作為種子節點，導致了其在大規模社交網絡上運行時間慢，不適合大規模社交網絡。為了解決貪心算法時間效率低的問題，一些優化算法被提出，比如經典的CELF算法[3]，它利用子模性來減少計算的時間，從而提高運行時間。然而，這些優化算法雖然提高了運行時間，但是在面對大規模社交網絡時仍存在時間效率問題。因此，一系列啟發式算法被研究者們提出[4-20]。Nguyen等[5]提出了一種基于概率的多跳擴散方法來解決影響力最大化問題，該算法考慮了多跳鄰居節點的影響，從而提高算法的準確性。Han Meng等[6]將時間延遲，接受率和傳播寬度這3個因素相結合，研究了一個新的模型，其運行結果優于傳統的算法。另外，Kyomin Jung等[7]提出了包括信息排序和信息評估兩個方面的IRIE(influence ranking influence estimation)算法，此算法在運行時間和影響范圍上有了明顯的提高。與上述研究方向不同，Cao等[8]結合度和核提出了CCA(core covering algorithm)算法，首先從核心開始選擇度比較大的節點作為種子節點，一旦某個節點被選為種子節點，其鄰居節點將會被覆蓋。該算法可能覆蓋部分影響力較高的節點，使得影響范圍不太準確。為了解決重疊社區的影響力問題，Qiu等[20]提出了IM-BOC(influence maximization algorithm based on overlapping community)算法。該算法分為3個階段：劃分社區，啟發階段和貪心階段。

近年來，很多研究者將拓撲勢理論應用于社交網絡[21-24]，并取得了很好效果。復雜網絡中，每個節點并不是孤立存在的，而是通過邊相互聯系，從而可以使用拓撲勢場來進行模擬。假設一個節點為一個場源，則它會作用于場中的其它節點，從而構成了拓撲勢場。文獻[21]基于拓撲勢，提出了一種基于位置的重疊社區發現方法。文獻[22]利用拓撲勢來評估節點重要性。與上述不同的是，何婧等[23]利用拓撲勢來進行動態社區挖掘。

綜上所述，為了解決影響力最大化問題中效率和效益問題，本文首先使用拓撲勢理論挖掘社交網絡中的“山峰”，“山谷”和“斜坡”節點，選取“山峰”和“山谷”節點作為候選種子集。然后，采用CELF算法確定最優種子集。這樣，在保證影響范圍的情況下，有效提高了算法的運行時間，從而彌補傳統算法的缺陷。

2 影響力最大化與傳播模型

2.1 問題描述

用網絡圖G(V,E) 表示是社交網絡，V表示節點，E表示邊。按照某種指標(度指標，介數指標，最短路徑等)，從所有節點中選取k個影響力最大的節點作為種子節點(激活狀態)，按照規定的傳播模型將其消息傳播給其鄰居節點，使得最終影響到的節點最多。其具體表示如下所示

σ(S*)=max{σ(S)|S?V,|S|=k}

(1)

2.2 傳播模型

社交網絡信息傳播的模型中，有兩種比較常用的傳播模型：獨立級聯(independent cascade，IC)模型和線性閾值(linear threshold，LT)模型。在這兩種模型中，節點只有一種狀態，要么激活態，要么非激活態。一個節點只可從非激活態轉換為激活態，反之，不成立。一旦節點被其它節點激活或者未被其它節點激活，這個節點將保持激活態或者未激活態，不會再改變。IC模型假設種子集處于激活態，其它節點為未激活態，種子節點有且僅有一次機會去激活其鄰居節點，鄰居節點要么被激活，要么未被激活。而LT模型是對節點的激活概率進行累計，當達到一定閾值時，節點則會被激活。否則，節點將不會再被激活，保持非激活態。因為IC模型容易理解，而且比較符合信息傳播特征，大多數研究采用IC模型，因此，本文也選用IC模型。該模型的傳播流程如下所示：

(1)設種子集S為激活狀態，其余節點為未激活態；

(2)激活態節點S以概率p去嘗試激活其每一個鄰居節點v；

(3)若節點v被激活，則v為激活狀態，v將會重復(2)。否則，v是為未激活狀態，它將保持此狀態，不會再改變狀態；

(4)不斷重復上述過程，直至所有的節點都保持一種狀態。

3 算法實現

為了均衡影響力范圍和運行時間，本文提出了一種基于拓撲勢的影響力最大化算法。該算法主要由以下兩個階段組成：啟發式階段和貪心階段。啟發式階段，運用拓撲勢理論，鑒別“山峰”，“山谷”和“斜坡”節點。“山峰”節點為影響力較大的節點，而“斜坡”節點為連接節點，我們將“山峰”和“山谷”節點加入候選種子集中。貪心階段，采用CELF算法從候選種子集中確定最優種子集。其結構框架如圖1所示。

圖1 算法框架

3.1 啟發式階段：選取候選種子集

拓撲勢理論自從被提出后，很多研究者將其用于社交網絡。本文中，我們將節點的拓撲勢作為衡量節點影響力指標。拓撲勢理論需要研究的重點是如何評估節點的質量，節點的影響力因子以及節點間的最短路徑。因為節點之間距離越遠，受到的影響可能越小。

3.1.1 拓撲勢

定義1 拓撲勢：節點v的拓撲勢計算方法如下

(2)

其中，nn為節點v的二度鄰居節點，u為節點v的鄰居節點，m(u) 為節點u的質量(如式(4)所示)，σ為影響力因子(如式(3)所示)，dvu為節點v和節點u之間的距離，取值為1或2(若鄰居節點，則取值為1；若二度鄰居節點，則取值為2)。

3.1.2 影響力因子

影響力因子σ用來控制節點的影響范圍。通常可根據網絡中節點的勢熵來篩選。勢熵的大小與網絡的不確定性有關。勢熵越小，網絡的不確定性越小，網絡的分布越不均勻。

定義2 勢熵：設節點v的拓撲勢為φ(v)，則勢熵為

(3)

由式(2)可知，當σ=0時，φ(u→v)→0時，則說明u和v之間無作用力，即φ(v)=mv=M，此時，勢熵趨近于最大值logN。當φ(u→v)→∞時，φ(u→v)→mu，則說明u和v的影響力相同，此時，勢熵趨近于最大值logN。因此，σ∈[0,∞)，H∈[0,logN]。它們的關系如圖2所示。因為勢熵越小，網絡的分布越均勻，所以，取H=logN，此時σ≈2。因此，我們取節點的拓撲勢的影響范圍主要是由二度鄰居決定。

圖2 勢熵與影響因子關系

3.1.3 節點質量

節點的度是指與該節點直接相連的邊的數量，其在一定程度上能夠反應節點影響力，節點的度越大，說明其影響力越高。然而，若一個度很大的節點，其卻很少進行傳播信息，即其傳播概率很小，這樣，其影響力整體上來說，應該相對較小。因此，本文中，我們將傳播概率和度結合，提出了加權度，作為衡量節點質量的指標。

定義3 節點質量：節點u的質量m(u) 的計算方法如下所示

(4)

其中，du和dw為節點u和w的度，N(u) 為u的鄰居節點，puw為節點u激活v的概率。

3.1.4 節點位置

我們根據相鄰節點的拓撲勢，將節點的位置分為以下3類：山峰，山谷和斜坡。山峰節點代表著影響力相對較大，為相鄰節點間的代表。斜坡節點相當于邊緣節點，與外界聯系密切，其充當“中介”的作用。山谷節點是內部節點且其影響力較小。我們根據影響因子將影響范圍考慮為二度鄰居節點。

(1)山峰。對于社交網絡中節點v滿足?φ(v)≥φ(u)，其中u為v的二度鄰居節點，則v為山峰節點。

(2)山谷。對于社交網絡中節點v滿足?φ(v)≤φ(u), 其中u為v的二度鄰居節點，則v為山谷節點。

(3)斜坡。對于社交網絡中節點v滿足?φ(v)<φ(u) 或者?φ(v)>φ(u)，其中u為v的二度鄰居節點，則v為斜坡節點。

為了更加清楚的解釋山峰，山谷和斜坡節點，我們以一個包含10個節點的社交網絡為例，其簡易圖如圖3所示。根據拓撲勢公式(式(2)和式(4))，社交網絡中的10個節點的拓撲勢及節點的位置，見表1。

3.1.5 候選種子集

根據以上小節，我們已確定節點的相對位置：山峰，山谷，斜坡。在影響力傳播的過程中，我們不僅需要影響力大的節點，而且需要邊緣節點與外界進行聯系。因此，為了提高算法的準確性，我們按照節點質量大小選取k個山峰節點和k個山谷節點作為候選種子集。

圖3 社交網絡

表1 社交網絡中節點拓撲勢及位置

節點12345678910拓撲勢16162423232120171710位置山谷山谷山峰斜坡斜坡斜坡斜坡斜坡斜坡山谷

3.2 貪心階段：確定最終種子集

通過上一小節我們得到了由k個山峰節點和k個山谷節點組成的候選種子集，本小節的主要任務就是利用CELF算法從候選種子集中選出最優種子集，使得最終影響力最大。CELF算法主要是在貪心算法的基礎上利用節點的影響力具有子模性進行優化，使得時間效率比原始的貪心算法快了近700倍。

定義4 CELF算法：對于節點A，B和C，在節點A加入種子節點后，在下一輪選擇種子節點時，若B在此輪的影響力增益大于C在上一輪的影響力增益，利用子模性，C在此輪的影響力必定小于其在上一輪的影響力增益，因此，B在此輪的影響力增益大于C。所以，我們可以直接將節點B加入種子節點，不需要再額外計算C的影響力增益，從而提高時間效率。

CELF算法利用子模型改進了貪心算法，在準確率上有了一定的保證，但是，其運行時間雖然比貪心算法快了700倍，仍然不適用于大型網絡。所以，我們先根據拓撲勢理論劃分節點的位置，將山峰節點和斜坡節點作為候選集，再利用CELF算法從候選集中選擇最優種子集，從而提高時間效率。該算法的偽代碼如下。

算法1：TSH算法

輸入：社交網絡G=(V,E)，種子數量k

輸出:種子集S

(1)初始化: 種子集S←φ

(2)forv∈V：

(3) 計算節點v的拓撲勢φ(v)

(4)判斷節點的位置

(5)從山峰山谷節點中：

(6) 按照加權度選取k個山峰節點和k個斜坡節點組成候選種子集

(7)對候選種子集進行CELF算法，尋找最優k個種子

(8)返回種子集S

時間復雜度：假設社交網絡G=(V,E) 有n個節點，m條邊，TSH算法的時間復雜度分析如下：第(2)～(3)行，計算節點拓撲勢的時間復雜度為O(nemax2)，其中emax為最大連邊數。第(4)行判斷節點的位置的時間復雜度為O(n)。第(5)～(6)行選取候選種子集的時間復雜度為O(2k)。因此，該算法的總的時間復雜度為O(nemax2+n+2k)≈O(nemax2)。

4 實驗與分析

4.1 實驗數據集

為了驗證算法的合理性，本文從斯坦福網站(http://snap.Stanford.edu/data/)上選取了4種不同類型的數據集：Ca-AstroPh，As-Caida，Email-Enron和Amazon數據集。其中，Ca-AstroPh源自e-print Arxiv，是由提交文章的科學家之間的協作關系所構成的。As-Caida是從地理和拓撲上不同位置的幾種不同類型的數據中收集的。Email-Enron數據集是由CALO項目得出，它是由大約150個員工進行交流溝通所構成的網絡。最后，Amazon數據集是通過爬取Amazon網站的評論和鏈接等而收集的。這4種數據集的基本信息見表2。

表2 數據集基本信息

4.2 對比算法及參數設置

為了驗證算法的有效性，我們將TSH算法在IC模型的基礎上，與CELF，PMIA，IRIE，Degree Discount和CCA算法進行比較。這6種算法的簡要介紹如下所示。

TSH：該算法分為啟發式算法和貪心算法。啟發式階段根據拓撲勢找出候選種子集；貪心階段使用CELF算法求出最優種子集。

CELF：貪心算法的代表算法，使用子模性原理優化了貪心算法。

PMIA：基于最短傳播路徑的較為經典的啟發式算法。

IRIE：由IR和IE兩個階段組成，在時間效率和影響力范圍上表現較好。

Degree Discount：在度中心性的基礎上，對種子節點的鄰居節點進行打折，從而提高了算法的準確性。

CCA：基于核覆蓋理論，為了減少影響力重疊，將種子的節點的鄰居進行覆蓋。本文設radius=2。

為了評估上述6種算法的優劣，我們在IC模型的基礎上，用蒙特卡羅模擬了10 000次實驗，并在4.3.1中給出了影響力擴散的平均值。

4.3 結果分析

影響范圍和運行時間是衡量社交網絡影響力最大化的兩個標準。目前現存的大部分算法存在影響力計算的準確性或者運行時間的問題。本節中，我們從影響力和運行時間兩方面對我們的TSH算法和5個對比算法在4種不同的數據集上進行評估。

4.3.1 影響范圍

圖4(a)～圖4(d)分別描述TSH，CELF，PMIA，IRIE，Degree Discount，和CCA算法在Ca-AstroPh，As-Caida，Email_Enron和Amazon數據集上的傳播范圍。通過比較這4種數據集上表現，我們可以輕易地發現CCA算法的影響范圍整體上來說相對較低，其影響力分別低于TSH算法54%，78%，74%和44%。這可能是由于CCA算法雖然考慮了節點的度和核，但是其為了減少影響力重疊，覆蓋了種子的鄰居節點，這可能覆蓋了過多的影響力高的節點，導致其影響范圍不準確。PMIA算法整體上影響力明顯低于TSH，CELF，IRIE和Degree Discount。比如，在Amazon數據集上，當種子集為100時，PMIA低于TSH算法36%。這可能是因為PMIA僅考慮了最短路徑這一個因素，導致其影響力存在一定的誤差。另外，Degree Discount算法的表現相對較好，明顯高于PMIA和CCA算法，而且跟IRIE的影響范圍相差無幾。值得注意的是，TSH算法在4個數據集上仍分別以4%，5%，4%和11% 高于Degree Discount算法。這可能是因為DegreeDiscount算法將度大的節點看作影響力大的節點，沒有考慮網絡的整體結構，可能導致其影響力存在一定的誤差。除此之外，當種子集為100時，TSH在4種數據集上的影響范圍分別以2%，6%，6%和1%高于IRIE算法，充分說明了TSH算法的優越性。在這4個數據集上，TSH算法影響力跟CELF算法差不多，但是，由圖4可知，CELF算法在Ca-AstroPh，As-Caida，Email-Enron和Amazon這4個數據集上的運行時間分別是1090 s，1733 s，13 401 s和12 850 s，不適合大型網絡。而TSH算法在262 111個節點，1 234 877 條邊的Amazon算法上的運行時間僅需344 s。綜合考慮，TSH算法有效均衡了影響力和運行時間，不僅其準確率較高，而且其運行時間較快，適合大規模的社交網絡。

圖4 影響范圍

4.3.2 運行時間

TSH，CELF，PMIA，IRIE，Degree Discount和CCA算法的時間復雜度分別是O(nemax2)，O(knm)，O(ntiθ+knoθniθlogn)，O(∑v∈Vdout(v))，O(klongn+m) 和O(km)。由于各種數據集的內部屬性不同可能導致其運行時間存在差距，因此，我們從斯坦福網站上選擇了4種不同類型的數據集進行比較，以增強說服性。圖5描述了TSH，CELF，PMIA，IRIE，Degree Discount和CCA算法在Ca-AstroPh，As-Caida，Email-Enron和Amazon數據集上的運行時間。從圖5中可以看出，CCA算法的運行時間最快，而TSH算法的運行時間僅次于CCA算法。但是由圖4可知，當種子集為100時，CCA算法在4個數據集上的影響范圍約占TSH算法的45%，20%，25%和56%，影響力較低。圖4顯示CELF算法影響力較大，但是從圖5中可知，其運行時間最長，尤其在Email-Enron數據集上的運行時間高達12 850 s，約是TSH運行時間的兩倍。Degree Discount算法的運行時間整體上來看運行效率較高，但是，Degree Discount未重復考慮網絡的整體結構，僅從局部角度評估節點的影響力，所以，其運行結果可能不太準確。TSH算法的運行時間在4個數據集上比PMIA分別快了77%，66%，41%和96%。另外，TSH算法的運行時間在4個數據集上比IRIE分別快了57%，73%，42%和24%。雖然TSH算法在計算拓撲勢時，需要考慮節點間的傳播度，導致了其運行時間稍長。但是，TSH在中大型社交網絡Amazon上僅用344 s，比CELF，PMIA，IRIE，Degree Discount快了97%，59%，90%和24%，說明了TSH算法在大規模社交網絡的可行性。