曾燕清，陳志德，李翔宇

(1. 福建江夏學(xué)院，福建 福州 350108；2. 福建師范大學(xué)，福建 福州 350007) 3. 閩江師范高等專(zhuān)科學(xué)校，福建 福州 350007)

基于用戶(hù)聚類(lèi)的社交網(wǎng)絡(luò)影響力最大化傳播模型

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

(1. 福建江夏學(xué)院，福建 福州 350108；2. 福建師范大學(xué)，福建 福州 350007) 3. 閩江師范高等專(zhuān)科學(xué)校，福建 福州 350007)

本文針對(duì)的是社交網(wǎng)絡(luò)中的影響力最大化問(wèn)題。在經(jīng)典線性閾值傳播模型基礎(chǔ)上，對(duì)社交網(wǎng)絡(luò)中的用戶(hù)進(jìn)行聚類(lèi)分析，并在此基礎(chǔ)上提出改善的K-LT傳播模型。在K-LT傳播模型基礎(chǔ)上，進(jìn)一步提出K-KK影響力最大化算法。通過(guò)采集真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)，進(jìn)行試驗(yàn)仿真。試驗(yàn)結(jié)果表明，改進(jìn)的K-KK影響力最大化算法與未改進(jìn)時(shí)相比，算法性能有較好提升。

社交網(wǎng)絡(luò)；傳播模型；影響力最大化

0 引言

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

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

1 相關(guān)工作

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

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

2 問(wèn)題定義

2.1 傳播模型

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

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

其中，閾值θv表示當(dāng)父節(jié)點(diǎn)u為活躍節(jié)點(diǎn)（該節(jié)點(diǎn)發(fā)表或轉(zhuǎn)發(fā)了某個(gè)信息）時(shí)，其子節(jié)點(diǎn)v成為活躍節(jié)點(diǎn)的潛在傾向性概率。LT模型是一個(gè)與0-1分布有關(guān)的概率模型，節(jié)點(diǎn)的閾值θv在[0,1]范圍內(nèi)選取隨機(jī)值；ω(u，v)表示v節(jié)點(diǎn)的活躍父節(jié)點(diǎn)對(duì)v的影響權(quán)重，同樣是隨機(jī)生成，且∑ω(u，v)≤1。基于以上描述，對(duì)于一個(gè)給定的活躍節(jié)點(diǎn)初始集合A（A∈V），用RS(A)表示社交網(wǎng)絡(luò)中最終活躍節(jié)點(diǎn)的集合，φ(A)＝|RS(A)|表示隨機(jī)激活過(guò)程結(jié)束時(shí)活躍節(jié)點(diǎn)的個(gè)數(shù)，φ(A)是一個(gè)隨機(jī)變量，用δ(A)表示φ(A)的期望值，我們稱(chēng)δ(A)為初始集合A的影響度。

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

2.2 影響力最大化問(wèn)題定義

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

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

3 K-LT及K-KK算法

3.1 用戶(hù)聚類(lèi)分析

在社交網(wǎng)絡(luò)中，依照用戶(hù)在社交網(wǎng)絡(luò)上的轉(zhuǎn)發(fā)數(shù)、出入度和發(fā)帖頻率等屬性，可以將用戶(hù)分為核心用戶(hù)、活躍用戶(hù)、非活躍用戶(hù)和水軍等不同類(lèi)別。對(duì)于不同類(lèi)別的用戶(hù)，其在LT模型中的閾值θ和影響權(quán)重ω都會(huì)有顯著差異，應(yīng)差別處理。故本節(jié)中將對(duì)用戶(hù)進(jìn)行聚類(lèi)分析。

k-means是經(jīng)典的聚類(lèi)劃分算法之一，它把集合D中的對(duì)象劃分為k個(gè)簇，并通過(guò)目標(biāo)函數(shù)評(píng)估簇的質(zhì)量，使簇內(nèi)對(duì)象相似，簇間對(duì)象相異。它的基本算法原理如下表2所示：

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

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

3.2 K-LT線性閾值模型

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

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

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

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

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

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

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

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)獲取及預(yù)處理

我們用具有開(kāi)放性、交流內(nèi)容公開(kāi)和用戶(hù)關(guān)系公開(kāi)等特性的微博平臺(tái)作為實(shí)驗(yàn)對(duì)象，獲取真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集對(duì)算法性能進(jìn)行驗(yàn)證。數(shù)據(jù)集是通過(guò)編寫(xiě)網(wǎng)絡(luò)爬蟲(chóng)在新浪微博上以某個(gè)節(jié)點(diǎn)為初始節(jié)點(diǎn)，按廣度優(yōu)先方式，進(jìn)行數(shù)據(jù)爬取，爬取流程如圖1所示。

圖1 微博用戶(hù)關(guān)系爬取流程Fig.1 Micro-blog user relationship crawling process

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

表5 微博用戶(hù)模型Tab.5 Micro-blog user model

同時(shí)，獲取每個(gè)用戶(hù)的關(guān)注和粉絲信息如表6、表7所示。

除了爬取用戶(hù)基本信息外，對(duì)每個(gè)用戶(hù)，用另一個(gè)爬蟲(chóng)獲取其前5頁(yè)微博數(shù)據(jù)，并獲取點(diǎn)贊數(shù)、轉(zhuǎn)發(fā)數(shù)、評(píng)論數(shù)等信息，存儲(chǔ)的數(shù)據(jù)如表8所示。

表6 關(guān)注關(guān)系Tab.6 Followee relationship

表7 粉絲關(guān)系Tab.7 Followwer relationship

表8 微博數(shù)據(jù)Tab.8 Micro-blog data

基礎(chǔ)數(shù)據(jù)抓取完畢后，對(duì)基礎(chǔ)數(shù)據(jù)進(jìn)行清洗和處理[11]，進(jìn)一步完善用戶(hù)模型，如下表9所示。其中，F(xiàn)ollower_list為粉絲的ID列表，F(xiàn)ollowee_list為關(guān)注的ID列表，Crawl_postnum，Yc_post, Post_forwardnum，Yc_forwardnum由統(tǒng)計(jì)得出。

表9 微博用戶(hù)模型Tab.9 Micro-blog user model

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

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

1. 用戶(hù)聚類(lèi)分析

參照4.1中對(duì)簇特性的定義，對(duì)實(shí)驗(yàn)網(wǎng)絡(luò)的用戶(hù)進(jìn)行聚類(lèi)分析，其聚類(lèi)結(jié)果信息如下表10所示。聚類(lèi)之后，網(wǎng)絡(luò)3個(gè)類(lèi)別節(jié)點(diǎn)情況如下表10所示。

表10 用戶(hù)聚類(lèi)結(jié)果Tab.10 user clustering result

2. 影響力最大化分析

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

5 小 結(jié)

圖2 算法時(shí)間消耗情況對(duì)比Fig.2 Comparison of algorithm time consumption

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

[1] 宮秀文, 張佩云. 基于PageRank的社交網(wǎng)絡(luò)影響最大化傳播模型與算法研究[J]. 計(jì)算機(jī)科學(xué), 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] 蔡國(guó)永, 裴廣戰(zhàn). 基于LT+模型的社交網(wǎng)絡(luò)影響力最大化研究[J]. 計(jì)算機(jī)科學(xué), 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] 蒙在橋. 在線社交網(wǎng)絡(luò)的動(dòng)態(tài)消息傳播模型研究與應(yīng)用[D]. 廣東工業(yè)大學(xué), 2014.

[12] 張振華, 劉瑞芳. 微博社交網(wǎng)絡(luò)中面向機(jī)構(gòu)的用戶(hù)挖掘[J].軟件, 2013, 34(1): 121-124.

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

[14] 張晨辰, 趙方. 社交網(wǎng)絡(luò)服務(wù)系統(tǒng)核心功能的設(shè)計(jì)與實(shí)現(xiàn)[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

曾燕清，碩士學(xué)歷。工作單位：福建江夏學(xué)院，電子信息科學(xué)學(xué)院，主要研究方向：社交網(wǎng)絡(luò)，大數(shù)據(jù)，無(wú)線安全與隱私；陳志德，教授，博士學(xué)歷，福建師范大學(xué)，數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院。主要研究方向：網(wǎng)絡(luò)與信息安全，社交網(wǎng)絡(luò)，大數(shù)據(jù)；李翔宇，碩士學(xué)歷，畢業(yè)學(xué)校于福建師范大學(xué)。主要研究方向：數(shù)據(jù)挖掘。工作單位：閩江師范高等專(zhuān)科學(xué)校，計(jì)算機(jī)系。

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