基于線程池的社交網絡影響力最大化

賈蘇 符精晶 張君

摘要：互聯網的發展也帶動了社會網絡的發展，但社會網絡規模較大，網絡結構較為稀疏，都給實際應用帶來了挑戰，且單線程算法對算力的使用不充分，因此在單機上開展了對算法并行化研究，使用線程池技術，通過實驗證明減少了算法運行的實際時間。

關鍵詞：社會網絡;影響力最大化;線程池

中圖分類號：TP391? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）19-0119-03

1 引言

隨著互聯網的快速發展，越來越多的人開始從傳統的線下社交轉移到線上社交，這給社交網絡[1]的發展帶來了前所未有的機遇，涌現出了一批像Facebook、Twitter、QQ等知名互聯網社交產品。社交網絡在方便人們溝通的同時，也會影響著人們實際的社會行為，這給我們對社交網絡的分析與應用帶來了機遇，比如商家想要通過在線上的活躍用戶的推薦獲取其銷量上的提升，也就是病毒式營銷（virtal -marketing）[2]。病毒式營銷基于具有較大影響力的個體群體向其他的個體進行推薦，感化其他不具有購買意愿的個體，因此如何找出社交網絡中影響力最大的群體是病毒式營銷開展的關鍵。

影響力最大化問題（Influence Maximization）最先由Domingos和Richardson等人[3]提出并定義，Kempe等人[4]在此基礎上進一步研究，提出了top-k的影響力最大化問題，并證明了影響力最大化問題是一個NP-hard問題。并提出了一個貪心算法，可以保證在[1-1/e]的范圍內接近最優解。

2 背景知識

2.1 影響力最大化問題（Influence Maximization）

將社交網絡抽象為一個圖[G=V，E]，其中[V]是網絡中個體的集合，[E]是網絡中個體之間關系的集合。網絡中的個體我們使用[v∈V]來代表，節點[v]的狀態有兩種，一種是活躍（active），在營銷中表示具有購買欲望，另一種是不活躍（inactive），營銷中表示不具有購買欲望。個體間的關系使用[e∈E] 來代表。網絡上不同節點之間的影響力是不同的，我們使用[Pu，v→（0，1）] 代表節點[u]對節點[v]的影響力即集合E中邊[u，v]上的值。

影響力最大化問題就是希望從[V]中選擇k（0<=k<=|V|）個節點作為種子集合[S]，種子集合中所有節點的狀態均為活躍。非種子集合的節點均為不活躍。然后在擴散模型下，種子集合中的節點去激活非激活狀態的節點。節點一旦激活便不再改變。我們希望最終的被激活的節點是最多的，即找到這樣的一個種子集合[S]：

[S*=argmaxInf（S）]

表示種子集合S的影響力擴散的大小。

2.2 影響力傳播模型-獨立級聯模型（Independent Cascade Model）

獨立級聯模型[4-6]最初是Jacob Goldenberg提出，是一個離散的概率模型。在此模型下，節點的狀態分為兩種，一種是激活狀態，另一種是不激活狀態。激活狀態的節點會嘗試激活不激活狀態的節點，節點對節點的激活作用是相互獨立的，不會累積，而且只能嘗試激活一次，只能從不激活狀態變為激活狀態且激活之后狀態不再發生改變。節點間激活狀態的改變模擬了信息的傳播，在此傳播模型下，連續的信息傳播被分解為獨立、離散的過程，也更有利于分析統計。

Kempe首次使用獨立級聯模型作為影響力傳播的模型，節點激活的狀態代表節點被影響力影響了，處于非激活的狀態代表此時節點尚未被影響。此模型下的影響力傳播過程如下：

初始時刻[t=0]， 網絡中只有種子節點處于激活狀態，其余非種子節點處于未激活狀態。

在任意時刻[t>0] ， 任意一個[t-1]時刻被激活的節點[u]有且僅有一次機會以概率[puv]去嘗試激活它的每一個處于非激活狀態的鄰居[v]。[puv]是節點[u]和[v]邊上的傳播概率。

如果存在多個處于激活狀態的節點同時嘗試激活它們的共同鄰居節點[v]，按照獨立級聯模型的定義，節點間的激活順序是獨立的，那么這些節點以隨機且獨立的順序去嘗試激活[v]，一旦激活，節點[v]的狀態即改變，不再受其他節點的影響。

在[t]時刻被激活的節點，會在[t+1]時刻也嘗試激活其鄰居節點。

重復上述過程，直到某一個時刻網絡中不再有新的節點被激活，影響力傳播過程終止。此時，網絡中被激活的非種子節點數就是此種子集合影響力的規模。

3 影響力最大化算法及其多線程實現

影響力最大化的貪心算法如下：

其中[InfS?v] 為種子集合加入節點[v]之后的影響力規模，為了準確地度量，我們使用Monto-carlo模擬來模擬影響力擴散的過程。由于每加入一個節點都需要多次的模擬，所以造成了算法所需要的時間很高。解決此問題有兩種思路：第一種是對其算法進行一定的改進，第二種是使用并行化手段完成算法的運行。

為了縮短算法運行所需要的時間，我們使用了多線程技術。針對當前機器核心數為4，我們使用了大小為4的線程池，其中每一個線程都去度量在當前種子集合的影響力大小，使用Callable接口去持有線程返回的結果。篩選出具有最大增益的非種子節點后更新種子集合，完成此輪種子節點選擇。線程池的使用可以降低傳統多線程創建和銷毀帶來的開銷，并對線程進行了統一的分配和監控，處理大量計算任務時其優勢更加明顯。

使用線程池具體代碼如下：

private Set select_seeds（） throws InterruptedException， ExecutionException {

// 線程池

ExecutorService threadPool = Executors.newFixedThreadPool（4）;

// 初始化非種子節點

noseeds.addAll（fromNodes）;

for （int i = 0; i < k; i++） {

Map candidate_Spread = new HashMap<>（）;

int ca_c = 0;

for （Integer candidate ： noseeds） {

if（edges.get（candidate）.size（） == 0） //當節點->目的節點的個數不為0

continue;

int count_Once = 0;

for （int j = 0; j < 100; j++） { // monto_carlo

Callable c = new diffusion_Thread（edges， seeds， candidate）;

// 執行任務并獲取Future對象

Future f = threadPool.submit（c）;

while （！f.isDone（）） { // no execute end loop it

//System.out.println（"? ?In while"）;

}

count_Once += f.get（）; // spread的累加

} //end for

candidate_Spread.put（candidate， count_Once）;

}

// refresh seeds

Optional> max_vlu = candidate_Spread.entrySet（）.stream（）

.max（Map.Entry.comparingByValue（））;

// 這里避免了每次都加入具有最大值spred值的candidate

if （！seeds.contains（max_vlu.get（）.getKey（））） {

seeds.add（max_vlu.get（）.getKey（））;// 更新seeds

noseeds.remove（max_vlu.get（）.getKey（））;// 從noseeds中刪除當前種子

}

}

return seeds;

}

4 數據集以及實驗結果

4.1 數據集及實驗相關設置

本文選擇了DBLP數據集和LiveJournal作為實驗的數據集（來自：http：//snap.stanford.edu/data/com-DBLP.html）。DBLP是一個關于科研論文發表共同作者的網絡，其中如果兩位作者至少發表一篇論文，則可以將他們聯系起來，即將作者看成是社交網絡中的節點，聯系則是節點間的邊。LiveJournal是一個擁有近1000萬會員的免費在線社區，它允許成員維護日志、個人日志和組日志，并且允許人們標記其他成員是他們的朋友。數據集的具體的拓撲信息如表2所示：

實驗代碼使用Java進行編寫，運行于Windows10機器上，處理器為I5 9500，內存8GB。實驗中使用獨立級聯模型（IC）作為影響力傳播模型。為了保證實驗結果的準確性，我們設置蒙特卡洛模擬的次數[R=2000]，這個過程也是實驗中最為耗時的過程，為了縮短運行所需要的時間，我們在這個過程中加入了多線程。

4.2 實驗結果

（1） 在DBLP上的實驗結果

（2） 在LiveJournal上的實驗結果

5 總結和展望

本文回顧了社會網絡上影響力最大化的發展及在其上的應用—病毒式營銷，針對影響力最大化的貪心算法做出了多線程的實現，在不影響實驗結果精度的情況下，縮短了實驗運行所需要的時間，并在DBLP和LiveJournal這兩個真實的社會網絡集合上進行了實驗，將影響力最大化的貪心算法進行了并行化 ，并將實驗運行時使用單線程和線程池所需的時間進行了對比。實驗證明通過并行化可以減少算法運行的時間。

在企業的實際操作中，希望很快地獲取他們期待的結果以供做出相對應的決策。因此，即使加入了多線程，也難以滿足企業級的實時性。下一步，我們將對算法進行一定的改進以提高算法的效率，并使用服務器集群技術完成現有計算任務。

參考文獻：

[1] 汪小帆，李翔，陳關榮.網絡科學導論[M].北京：高等教育出版社，2012.

[2] Bass F M.A new product growth for model consumer durables[J].Management Science，1969，15（5）：215-227.

[3] Domingos P， Richardson M. Mining the network value of customers[J].Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco，USA，2001.

[4] Kempe . Maximizing the spread of influence through a social network[J]. Proc.of Acm Sigkdd Intl Conf.on Knowledge Discovery & Data Mining， 2003.

[5] Goldenberg J ， Muller L E . Talk of the Network： A Complex Systems Look at the Underlying Process of Word-of-Mouth[J]. Marketing Letters， 2001， 12（3）：211-223.

[6] Goldenberg J， Libai B， Muller E. Using complex systems analysis to advance marketing theory development： Modeling heterogeneity effects on new product growth through stochastic cellular automata[J]. Academy of Marketing Science Review，2001，2001：1.

收稿日期：2021-09-18

基金項目：沙洲職業工學院青年教師基金（SGJJ2021B09）

作者簡介：賈蘇（1993—），江蘇寶應人，男，沙洲職業工學院電子信息工程系助教;符精晶（1994—），江蘇江都人，女，沙洲職業工學院電子信息工程系助教;張君（1986—），江蘇張家港人，男，沙洲職業工學院電子信息工程系助教。