基于用戶聚類的社交網絡影響力最大化傳播模型

曾燕清，陳志德，李翔宇

(1. 福建江夏學院，福建 福州 350108；2. 福建師范大學，福建 福州 350007) 3. 閩江師范高等?？茖W校，福建 福州 350007)

基于用戶聚類的社交網絡影響力最大化傳播模型

曾燕清1，陳志德2，李翔宇3

(1. 福建江夏學院，福建 福州 350108；2. 福建師范大學，福建 福州 350007) 3. 閩江師范高等?？茖W校，福建 福州 350007)

本文針對的是社交網絡中的影響力最大化問題。在經典線性閾值傳播模型基礎上，對社交網絡中的用戶進行聚類分析，并在此基礎上提出改善的K-LT傳播模型。在K-LT傳播模型基礎上，進一步提出K-KK影響力最大化算法。通過采集真實社交網絡數據，進行試驗仿真。試驗結果表明，改進的K-KK影響力最大化算法與未改進時相比，算法性能有較好提升。

社交網絡；傳播模型；影響力最大化

0 引言

社交網絡影響力是指用戶受其他社交網絡用戶信息傳播的過程。社交網絡中影響力最大化問題是指在給定傳播模型的情況下，從網絡中選取k個初始種子節(jié)點，讓其在網絡中傳播影響，使得最終傳播影響范圍最大。信息在社交網絡傳播過程中都遵循一定的規(guī)則，這些規(guī)則稱為傳播模型。挖掘社交網絡中有影響力的用戶，在營銷、信息檢索、信息推薦和社區(qū)挖掘[12-14]等領域都得到了廣泛的應用。因而，在給定播模型基礎上，研究影響力最大化問題具有重要應用價值。傳播模型主要可以分為基于傳播過程的模型、基于影響力的模型和基于轉發(fā)因素的模型。主要的一些基本傳播模型有線性閾值模型（LTM）、獨立級聯模型（ICM）、加權級聯模型（WC）和熱傳播模型等[1]。在經典的線性閾值模型中，對節(jié)點的差異性處理是通過節(jié)點的出入度，即節(jié)點的網絡結構來體現的，節(jié)點的權重和閾值則屬于隨機生成，無法體現不同個體對信息的要求高低，也無法體現對其他個體影響的差異。我們認為網絡中除出入度以外，節(jié)點的相關性和重要性是衡量其影響力重要指標。因此，本文基于兩種考慮：不同用戶對信息需求不同、不同用戶影響力不同，提出基于用戶聚類的改進的K-LT傳播模型，并在該傳播模型下對KK貪心算法進行改進，提出基于用戶聚類的K-KK貪心算法來近似求解影響力最大化問題。實驗表明，在本文提出的傳播模型中，其傳播過程相較于傳統(tǒng)線性閾值傳播模型更接近于實際傳播過程；在該模型下處理影響力最大化問題相較于傳統(tǒng)線性閾值傳播模型而言，計算效率大幅度提高，并且傳播效果并未消耗傳播效果。

本文第二節(jié)介紹相關工作；第三節(jié)對問題進行定義；第四節(jié)介紹本文提出的K-LT模型和尋找Top-k節(jié)點的貪心算法K-KK；第五節(jié)中我們將介紹在采集的數據集上進行的實驗及結果分析；在本文最后將對工作進行總結。

1 相關工作

影響力最大化問題是社交網絡研究中的重要問題，該問題最早由Domingos和Richhardson等人[2]提出。在此基礎上，Kempe等[3]提出top-k影響力最大化問題，即如何在網絡中找到k個初始節(jié)點使得通過這k個節(jié)點所產生的影響傳播范圍最大。同時，Kempe等人證明，在線性閾值和獨立級聯模型下，影響力最大化問題為NP難問題[4]，并提出了近似比為（1-1/e）的KK貪心算法來解決此問題。該貪心算法的復雜度太高，對大規(guī)模社交網絡而言伸縮性將遇到挑戰(zhàn)。為解決貪心算法效率問題，研究者們提出了一系列改進的貪心算法和新的啟發(fā)式算法。

Leskovec等[5]通過改進影響函數的子模特性，提出CELF算法，此算法很大程度上減少了評估種子影響范圍的次數，但當網絡規(guī)模迅速擴大時，仍有計算量大問題。Goyal等在CELF基礎上提出了CELF++算法，進一步提高了算法性能[6]。Chen[7]等人對Kempe的貪心算法進行了優(yōu)化，隨后提出degree-discount算法，改算法提升了計算性能，但其基于在獨立級聯模型下所有邊影響概率值相同的假設，跟實際傳播過程不符。除了貪心算法之外，還有啟發(fā)式算法。Chen和Wang在LT傳播模型下，提出構造局部有向無環(huán)圖的啟發(fā)式算法LDAG[8]，但改算法只考慮相鄰節(jié)點的直接影響力。Kimura和Saito等提出了基于最短路徑的SPM和SP1M模型[9],在SPM和SP1M模型下，節(jié)點的影響力范圍可以進行準確計算，但這些模型未考慮用戶的影響力問題，僅僅使用最短路徑而忽略影響力在傳播過程中的重要作用。在以上介紹的模型中針對LT模型提出的方法在衡量節(jié)點差異性時，是通過節(jié)點的出入度來體現；而節(jié)點的權重和閾值則基于隨機生成的假設，未考慮不同類型個體對信息的要求高低和對其他個體影響力的差異?；谝陨峡紤]，本文研究考慮個體信息要求差異和影響力差異的社交網絡影響力最大化問題，首先對用戶進行聚類分析，以優(yōu)化閾值和影響力參數；接著提出基于聚類的改進的K-LT傳播模型；再給出基于聚類的優(yōu)化的K-KK貪心算法，并通過實驗對比了所提出的算法的性能。

2 問題定義

2.1 傳播模型

給定社交網絡圖G=(V, E, w)，其中V表示網絡中的節(jié)點集合，E表示節(jié)點間邊的集合，w表示邊上的權重，則傳統(tǒng)線性閾值傳播模型是以接受者為中心的模型。則給定活躍節(jié)點初始集合A，信息傳播模型M可以表示如下表1所示：

表1 線性閾值傳播模型Tab.1 Linear-threshold propagation model

其中，閾值θv表示當父節(jié)點u為活躍節(jié)點（該節(jié)點發(fā)表或轉發(fā)了某個信息）時，其子節(jié)點v成為活躍節(jié)點的潛在傾向性概率。LT模型是一個與0-1分布有關的概率模型，節(jié)點的閾值θv在[0,1]范圍內選取隨機值；ω(u，v)表示v節(jié)點的活躍父節(jié)點對v的影響權重，同樣是隨機生成，且∑ω(u，v)≤1?；谝陨厦枋?，對于一個給定的活躍節(jié)點初始集合A（A∈V），用RS(A)表示社交網絡中最終活躍節(jié)點的集合，φ(A)＝|RS(A)|表示隨機激活過程結束時活躍節(jié)點的個數，φ(A)是一個隨機變量，用δ(A)表示φ(A)的期望值，我們稱δ(A)為初始集合A的影響度。

在上述線性閾值模型中，節(jié)點的差異性是通過節(jié)點的出入度，即節(jié)點的網絡結構來體現的。而所有節(jié)點的權重和閾值都用同樣的隨機方式生成，且生成值時取值區(qū)間相同，無法體現不同個體對信息的要求高低，以及不同個體對其他個體影響力的差異。為了更好的模擬現實中的社交網絡，我們將在下一節(jié)中使用聚類方法來優(yōu)化閾值和影響力參數。

2.2 影響力最大化問題定義

在給定上述線性閾值傳播模型下，我們可以對影響力最大化問題進行定義。

定義1 給定社交網絡G=（V,E,w）、傳播模型M和k≤|V|，尋找k個節(jié)點的種子集合，使得φ(A)=|RS(A)|最大，RS(A)表示社交網絡中最終活躍節(jié)點的集合，φ(A)表示在傳播模型M下傳播結束后激活的節(jié)點的總數目。

3 K-LT及K-KK算法

3.1 用戶聚類分析

在社交網絡中，依照用戶在社交網絡上的轉發(fā)數、出入度和發(fā)帖頻率等屬性，可以將用戶分為核心用戶、活躍用戶、非活躍用戶和水軍等不同類別。對于不同類別的用戶，其在LT模型中的閾值θ和影響權重ω都會有顯著差異，應差別處理。故本節(jié)中將對用戶進行聚類分析。

k-means是經典的聚類劃分算法之一，它把集合D中的對象劃分為k個簇，并通過目標函數評估簇的質量，使簇內對象相似，簇間對象相異。它的基本算法原理如下表2所示：

表2 k-means算法基本原理Tab.2 K-means algorithm

使用k-means算法進行聚類的第一步，需要確定k的數量。在對社交網絡用戶進行分析的模型中，我們將k定義為用戶可以劃分的類型數目。根據社交網絡的用戶特征，可以將用戶分為六種類型[12]:游民型用戶、關注他人型用戶、積極型用戶、自我關注型用戶、持久貢獻型和明星型用戶。按照其受影響閾值和影響力的差異，可以將上述類別進一步合并為三類：核心用戶、活躍用戶和非活躍用戶。對應到聚類的結果中，可以參照各個簇的數據特征將其定義：被轉發(fā)較多的核心用戶、轉發(fā)較多而被轉發(fā)較少的活躍用戶、轉發(fā)和被轉發(fā)都較低的非活躍用戶，故本文中將k的值定義為3，對用戶進行聚類分析，聚類結果將在實驗部分給出并進行分析。聚類分析結束后，將聚類的結果作為本文所提出改進的K-LT線性閾值模型的輸入，具體將在下一節(jié)中闡述。

3.2 K-LT線性閾值模型

在確定用戶的聚類數目后，對三類用戶的閾值選擇區(qū)間參數進行優(yōu)化：考慮核心用戶是被轉發(fā)較多，設定核心用戶V1:[a,1];活躍用戶是轉發(fā)較多而被轉發(fā)較少，設定V2：[0,1];非活躍用戶轉發(fā)和被轉發(fā)都較少，設定V3:[b,1]。對于影響力同樣加入權重：核心用戶對其他用戶影響較大，設定核心用戶V1：從c*ω(u，v)；活躍用戶V2:ω(u，v);非活躍用戶V3：d*ω(u，v)。參照微博中三類用戶的轉發(fā)量比例[10]，本模型中，設定參數取值為：a=0.5，b=0.2，c=2，d=1/2。給定活躍節(jié)點的初始集合A，則信息按照如下表3中所示過程進行傳播。

以上得到基于聚類優(yōu)化的線性閾值K-LT模型，模型模擬了社交網絡的信息傳播過程，以該信息傳播模型為基礎，將在下一節(jié)中進一步解決影響力最大化問題。

3.3 K-KK影響力最大化貪心算法

KK貪心算法的影響最大化效果較好，最優(yōu)解概率大于60%，但缺點在于計算量較大。算法的每一步都要重新計算未激活節(jié)點的邊際效應，時間復雜性為O（n^2*m*n），m為每個節(jié)點的平均邊數，n為圖中所有節(jié)點的總數。由于核心用戶節(jié)點的影響力遠高于其他節(jié)點，故可進行假設最大影響力的節(jié)點一定在核心用戶中?；谏鲜黾僭O，在加入聚類優(yōu)化后，可以將節(jié)點選擇的范圍從全部未激活節(jié)點集合，縮小至未激活的核心用戶節(jié)點集合；進而可以大幅減少計算量以優(yōu)化這一問題?；谝陨峡紤]，我們對KK算法進行改進，提出基于聚類的優(yōu)化的K-KK算法，改進后的算法如下表4所示。

表3 K-LT傳播算法Tab.3 K-LT propagation model

通過聚類優(yōu)化后，K-KK算法選擇節(jié)點的范圍從過去的KK算法全部節(jié)點V范圍，縮小到了核心節(jié)點集V1范圍，大幅減少了計算量、提高算法效率。

表4 K-KK算法Tab.4 K-KK algorithm

4 實驗分析

4.1 實驗數據獲取及預處理

我們用具有開放性、交流內容公開和用戶關系公開等特性的微博平臺作為實驗對象，獲取真實網絡數據集對算法性能進行驗證。數據集是通過編寫網絡爬蟲在新浪微博上以某個節(jié)點為初始節(jié)點，按廣度優(yōu)先方式，進行數據爬取，爬取流程如圖1所示。

圖1 微博用戶關系爬取流程Fig.1 Micro-blog user relationship crawling process

爬蟲先模擬登陸新浪微博，從種子節(jié)點用戶ID開始，首先采集該節(jié)點節(jié)基本信息，并用解析器進行數據解析，然后獲取該節(jié)點的關注列表和粉絲列表網頁URL，接著通過關注列表和粉絲列表網頁URL獲取關注或粉絲用戶ID和URL信息，并放入待爬取隊列，以此類推，直到達到指定的的爬取深度N為止。但是，新浪微博具有反爬策略，每個用戶最多只能采集其200個關注用戶和粉絲用戶，用戶基本信息如表5所示。

表5 微博用戶模型Tab.5 Micro-blog user model

同時，獲取每個用戶的關注和粉絲信息如表6、表7所示。

除了爬取用戶基本信息外，對每個用戶，用另一個爬蟲獲取其前5頁微博數據，并獲取點贊數、轉發(fā)數、評論數等信息，存儲的數據如表8所示。

表6 關注關系Tab.6 Followee relationship

表7 粉絲關系Tab.7 Followwer relationship

表8 微博數據Tab.8 Micro-blog data

基礎數據抓取完畢后，對基礎數據進行清洗和處理[11]，進一步完善用戶模型，如下表9所示。其中，Follower_list為粉絲的ID列表，Followee_list為關注的ID列表，Crawl_postnum，Yc_post, Post_forwardnum，Yc_forwardnum由統(tǒng)計得出。

表9 微博用戶模型Tab.9 Micro-blog user model

因新浪的反爬策略，爬取的粉絲不一定都在數據中，并且許多用戶間關系在用戶模型中無法體現，無法形成完整和封閉的傳播網絡，需要對數據進一步做預處理操作。首先我們對節(jié)點進行加邊操作，具體步驟為：（1）取用戶列表中的用戶IDi，在IDi的Follower_list（Followee_list）中依次取出一個IDj；（2）在用戶列表中找到IDj，若IDi不在IDj的Followee_list（Follower_list）中，則將IDi加入到該Followee_list（Follower_list）中，作為該節(jié)點的一條出度。當加邊操作結束后，即可開始構建實驗傳播網絡。將微博網絡中的用戶表示為試驗網絡中的節(jié)點，用戶的關注和粉絲關系表示為節(jié)點間的有向邊。例如，用戶A關注B，則A為B的粉絲，在網絡中生成一條由B指向A的有向邊，作為消息傳播方向；雙向關注則添加雙向有向邊。

4.2 實驗結果分析

1. 用戶聚類分析

參照4.1中對簇特性的定義，對實驗網絡的用戶進行聚類分析，其聚類結果信息如下表10所示。聚類之后，網絡3個類別節(jié)點情況如下表10所示。

表10 用戶聚類結果Tab.10 user clustering result

2. 影響力最大化分析

在進行算法性能測試時，所使用的計算服務器（虛擬化平臺）硬件參數為：內存64G，CPU30核，硬盤50G。在改進的K-LT模型中，對用戶進行了聚類分析，并對閾值θv和權重ω(u，v)參數進行了優(yōu)化。選取不同的top-k節(jié)點，時間消耗情況如下圖2中所示，通過分析可知，在未改進的KK算法中，隨著選取節(jié)點數的增加，其計算時間大幅度增加，在K-KK算法中，隨著k值的增加，其計算增長幅度較為平緩，遠小于KK算法的增長幅度，相比較而言對不同的k其計算時間有大幅度效率提高。

5 小 結

圖2 算法時間消耗情況對比Fig.2 Comparison of algorithm time consumption

本文針對社交網絡中的傳播影響力最大化問題，基于個體對信息要求差異和影響力差異兩方面考慮，提出改進的K-LT模型和K-KK算法。在傳播網絡中，先對用戶進行聚類分析，將用戶劃分到不同類別，對不同類別用戶，考慮其對信息的需求不同，對其他用戶產生的影響也不同，進而對影響力和接受信息閾值參數進行優(yōu)化。在參數優(yōu)化后，給出基于聚類的K-LT傳播模型，以K-LT模型為基礎，給出基于聚類的K-KK影響力最大化算法，實驗結果表明，算法改進后，其計算效率有較大幅度提高。

[1] 宮秀文, 張佩云. 基于PageRank的社交網絡影響最大化傳播模型與算法研究[J]. 計算機科學, 2013, 40(S1): 136-140.

[2] Richardon M, Domingos P. Mining knowledge-sharing sites for viral marketing. Proceedings of the 8thACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada, 2002: 61-70.

[3] Kempe D, Kleinberg J, Tardos E, Influential nodes in a diffusion model for social networks. Cairel L, Italiano G F, Monteiro L, et al, eds. Automata, Languages and Programming. Libson, Portugal, 2005: 1127-1138.

[4] 蔡國永, 裴廣戰(zhàn). 基于LT+模型的社交網絡影響力最大化研究[J]. 計算機科學, 2016, 43(9): 99-102.

[5] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks. Proceedings of the 13thACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose, USA, 2007, 420-429.

[6] Goyal A, Lu W, Lakshmanan L V. CELF++: Optimizing the greedy algorithm for influence maximization in social networks. Proceedings of the 20thInternational Conference Companion on World Wide Web. Hyderabad, India, 2001: 47-48.

[7] Chen W, Wang Y, Yang S. Efficient influence maximization in social networks. Proceeding of the 15thACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 199-208.

[8] Chen W, Yuan Y, Zhang L. Scalable influence maximization in social networks under the linear threshold model[C]. 2010 IEEE 10th International Conference on Data Mining (ICDM). IEEE, 2010: 88-97.

[9] Kimura M, Saito K. Approximate solutions for the influence maximization problem in a social network. Gabrys B, Howlett R J, Jain L C eds. Knowledge-Based Intelligent Information and Engineering Systems. Bournemouth, UK, 2006: 937-944.

[10] Kempe D, Kleinberg J, Tardos E,Maximizing the spread of influence through a Social network[C]. Proceedings of the ninth ACM ISIGKDD international conference on knowledge discovery and data mining .ACM, 2003: 137-146.

[11] 蒙在橋. 在線社交網絡的動態(tài)消息傳播模型研究與應用[D]. 廣東工業(yè)大學, 2014.

[12] 張振華, 劉瑞芳. 微博社交網絡中面向機構的用戶挖掘[J].軟件, 2013, 34(1): 121-124.

[13] 李善濤, 肖波. 基于社交網絡的信息推薦系統(tǒng)[J]. 軟件, 2013, 34(12): 41-45.

[14] 張晨辰, 趙方. 社交網絡服務系統(tǒng)核心功能的設計與實現[J]. 軟件, 2013, 34(12): 92-98.

User Clustering based Social Networks Influence Maximization Propagation Model

ZENG Yan-qing1, CHEN Zhi-de2, LI Xiang-yu3
(1. Fujian Jiangxia University Fujian, Fuzhou 350108; 2. Fujian Normal University Fujian, Fuzhou 350007; 3. Minjiang Normal College Fujian, Fuzhou 350007)

This paper focuses on the problem of influence Maximization in social networks. On the basis of the classical Linear-threshold propagation model, we cluster and analyze the users in social networks. Then, we propose our improved K-LT propagation model. Based on K-LT model we further propose the K-KK influence maximization algorithm. The simulation is carried out by collecting the real social network data. The experimental results show that the improved K-KK algorithm is better than the other one when it is not improved.

Social networks; Propagation model; Influence maximization

TP393.09

A

10.3969/j.issn.1003-6970.2017.05.031

曾燕清，碩士學歷。工作單位：福建江夏學院，電子信息科學學院，主要研究方向：社交網絡，大數據，無線安全與隱私；陳志德，教授，博士學歷，福建師范大學，數學與計算機科學學院。主要研究方向：網絡與信息安全，社交網絡，大數據；李翔宇，碩士學歷，畢業(yè)學校于福建師范大學。主要研究方向：數據挖掘。工作單位：閩江師范高等?？茖W校，計算機系。

本文著錄格式：曾燕清，陳志德，李翔宇. 基于用戶聚類的社交網絡影響力最大化傳播模型[J]. 軟件，2017，38（5）：144-149