沈記全，林 帥，李志瑩

（河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454003）

0 概述

隨著智能移動(dòng)設(shè)備的普及和5G 網(wǎng)絡(luò)的應(yīng)用，社交網(wǎng)絡(luò)發(fā)展迅速。影響力最大化問題作為社交網(wǎng)絡(luò)分析領(lǐng)域的熱點(diǎn)研究問題，旨在從社交網(wǎng)絡(luò)中尋找k個(gè)最具影響力的節(jié)點(diǎn)，并最大化以這些節(jié)點(diǎn)作為種子節(jié)點(diǎn)的最終信息傳播范圍，被廣泛應(yīng)用于在線廣告［1-2］、病毒營(yíng)銷［3］、專家發(fā)現(xiàn)［4］、個(gè)性化推薦［5］等任務(wù)。用戶影響力度量是影響力最大化問題的核心。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)［6］是影響力度量的重要依據(jù)。與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相關(guān)的影響力度量指標(biāo)可以分為全局性指標(biāo)和局部性指標(biāo)。介數(shù)中心性［7］、接近中心性［8］、離心中心性［9］、流介數(shù)中心性［10］、Katz 中心性［11］、連通介數(shù)中心性［12］等都屬于全局性指標(biāo)。全局性指標(biāo)需要依靠網(wǎng)絡(luò)完整拓?fù)浣Y(jié)構(gòu)，在整個(gè)網(wǎng)絡(luò)范圍內(nèi)計(jì)算節(jié)點(diǎn)影響力，因此時(shí)間復(fù)雜度很高。度中心性［13］、半局部中心性［14］、特征向量中心性［15］等都屬于局部性指標(biāo)。局部性指標(biāo)僅依據(jù)局部范圍的拓?fù)湫畔⒂?jì)算節(jié)點(diǎn)的影響力，與全局性指標(biāo)相比時(shí)間復(fù)雜度較低。然而，影響力傳播具有三度分隔特性，即社交網(wǎng)絡(luò)中相距三度是強(qiáng)連接，強(qiáng)連接可以引發(fā)行為，相距超過三度是弱連接，弱連接只能傳遞信息。節(jié)點(diǎn)有自環(huán)［16］特性，擁有自環(huán)的節(jié)點(diǎn)比沒有自環(huán)的節(jié)點(diǎn)自身活躍度更高，兩個(gè)節(jié)點(diǎn)之間還可能存在多邊，這些因素都與節(jié)點(diǎn)的影響力密切相關(guān)?，F(xiàn)有的局部性指標(biāo)往往忽略這些因素，導(dǎo)致對(duì)影響力的度量不夠全面，從而影響信息的最終傳播范圍。

本文結(jié)合三度分隔原理［17］，提出用節(jié)點(diǎn)在局部范圍內(nèi)的影響力近似其在全局范圍內(nèi)影響力的算法。根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)構(gòu)造生成圖，依據(jù)生成圖劃分每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的局部域，根據(jù)節(jié)點(diǎn)在對(duì)應(yīng)局部域內(nèi)的影響力篩選候選種子節(jié)點(diǎn)。計(jì)算每個(gè)節(jié)點(diǎn)與種子集合的重疊比因子，并據(jù)此決定候選種子節(jié)點(diǎn)是否能成為種子節(jié)點(diǎn)。通過在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果以驗(yàn)證本文算法的正確性和有效性。

1 相關(guān)知識(shí)

1.1 影響力最大化問題

社交網(wǎng)絡(luò)可用有向圖G=(V,E)表示，其中，V是節(jié)點(diǎn)集合且V=｛v1,v2,…，vn｝，E是邊集合且E=｛（vi,v）j|vi,vj?V｝。（?v）ivi?V，（?v）jvj?V，如果vi對(duì)vj產(chǎn)生一次通信行為，則從vi到vj構(gòu)成了一條有向邊

影響力最大化問題是從網(wǎng)絡(luò)G=(V,E)中找到一個(gè)大小為k的節(jié)點(diǎn)集合S，最大化以這k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)開始影響力傳播后影響力的最終傳播范圍（即激活的節(jié)點(diǎn)數(shù)最多）。影響力最大化問題可表示如下：

其中：S*表示節(jié)點(diǎn)集合；f(S*)表示影響力的傳播范圍。

1.2 影響力傳播模型

線性閾值（Linear Threshold，LT）模型［18-19］可以用來模擬影響力的傳播過程。在LT 模型中，節(jié)點(diǎn)只能處于激活狀態(tài)或者非激活狀態(tài)。激活狀態(tài)的節(jié)點(diǎn)通過有向邊試圖激活處于非激活狀態(tài)的鄰居節(jié)點(diǎn)。對(duì)于非激活狀態(tài)的節(jié)點(diǎn)，當(dāng)所有激活狀態(tài)的鄰居節(jié)點(diǎn)對(duì)其影響力之和大于該節(jié)點(diǎn)的激活閾值時(shí)，該非激活節(jié)點(diǎn)就轉(zhuǎn)為激活狀態(tài)。當(dāng)網(wǎng)絡(luò)中不再有節(jié)點(diǎn)被激活（即由非激活狀態(tài)轉(zhuǎn)為激活狀態(tài)）時(shí)，影響力的傳播過程收斂。

圖1 給出了根據(jù)LT 模型模擬影響力傳播的過程，其中，灰色圓表示激活節(jié)點(diǎn)，白色圓表示非激活節(jié)點(diǎn)，有向邊上數(shù)字表示箭尾節(jié)點(diǎn)對(duì)箭首節(jié)點(diǎn)的影響力。節(jié)點(diǎn)v1、v2、v5和v6為種子節(jié)點(diǎn)，在傳播開始時(shí)處于激活狀態(tài)；其他節(jié)點(diǎn)則處于非激活狀態(tài)。整個(gè)傳播過程經(jīng)過3 輪迭代收斂。

圖1 LT 模型上的信息傳播示例Fig.1 Example of information dissemination on LT model

2 影響力最大化算法

本文針對(duì)局部性度量指標(biāo)構(gòu)造生成圖，根據(jù)影響力傳播的三度分隔原理構(gòu)建局部影響力度量模型，依據(jù)局部影響力度量模型設(shè)計(jì)基于局部域影響力的種子節(jié)點(diǎn)選擇算法。

2.1 權(quán)重感知的生成圖構(gòu)造

邊影響權(quán)重根據(jù)自環(huán)和多邊屬性計(jì)算。邊權(quán)重反映了節(jié)點(diǎn)間的親密程度，影響力的傳播過程又受鄰居間關(guān)系疏密的影響。因此，邊影響權(quán)重的計(jì)算過程中應(yīng)考慮自環(huán)和多邊現(xiàn)象。

自環(huán)指的是一種特殊的環(huán)結(jié)構(gòu)，這種環(huán)狀結(jié)構(gòu)只包含一個(gè)節(jié)點(diǎn)。社交網(wǎng)絡(luò)中用戶可能發(fā)起只有自己參與的社交活動(dòng)，從而在對(duì)應(yīng)的社交網(wǎng)絡(luò)圖中形成只有該節(jié)點(diǎn)參與的自環(huán)。自環(huán)多的節(jié)點(diǎn)活躍度較高，在信息傳播過程中會(huì)主動(dòng)地影響其他節(jié)點(diǎn)。本文引入自環(huán)因子度量自環(huán)對(duì)節(jié)點(diǎn)能力的影響。自環(huán)因子計(jì)算如下：

其中：Rvi表示節(jié)點(diǎn)vi的自環(huán)因子；ψ（vi）表示節(jié)點(diǎn)vi每個(gè)自環(huán)的權(quán)重。在無權(quán)網(wǎng)絡(luò)中，ψ（vi）默認(rèn)為1，此時(shí)節(jié)點(diǎn)自環(huán)因子等于節(jié)點(diǎn)的自環(huán)個(gè)數(shù)。

多邊指的是社交網(wǎng)絡(luò)圖中兩個(gè)節(jié)點(diǎn)間有多條邊存在。在社交網(wǎng)絡(luò)中，兩個(gè)節(jié)點(diǎn)間的一次互動(dòng)會(huì)在社交網(wǎng)絡(luò)圖中對(duì)應(yīng)的節(jié)點(diǎn)間產(chǎn)生一條邊。當(dāng)兩個(gè)節(jié)點(diǎn)間有多次互動(dòng)時(shí)，它們之間就會(huì)有多條邊。然而，隨著邊數(shù)的增加，圖的存儲(chǔ)和遍歷成本也會(huì)增加。在不影響圖的存儲(chǔ)和計(jì)算成本的前提下，本文引入多邊因子，用以度量節(jié)點(diǎn)間存在的多邊現(xiàn)象對(duì)信息傳播過程的影響。多邊因子隨著兩個(gè)節(jié)點(diǎn)間邊的增多而增大。多邊因子計(jì)算如下：

結(jié)合自環(huán)因子和多邊因子，本文引入邊影響權(quán)重，描述節(jié)點(diǎn)間的影響力。

定義1給定一條邊（vi,v）j，vi對(duì)vj的影響力即為該邊的邊影響權(quán)重。邊影響權(quán)重計(jì)算如下：

根據(jù)自環(huán)因子、多邊因子和邊影響權(quán)重構(gòu)造生成圖，并且生成圖是有向帶權(quán)圖。

2.2 局部域影響力度量

影響力的全局性度量指標(biāo)往往從拓?fù)浣Y(jié)構(gòu)的整體出發(fā)對(duì)節(jié)點(diǎn)的影響力進(jìn)行全面準(zhǔn)確的衡量，但是卻存在計(jì)算復(fù)雜度高的問題。根據(jù)影響力傳播遵循的三度分隔原理［17］，即節(jié)點(diǎn)的影響力在相距不超過三跳的鄰居節(jié)點(diǎn)間傳播時(shí)隨著距離的增大而不斷衰減，當(dāng)傳播距離超過三跳時(shí)幾近消失。本文根據(jù)三度分隔特性，利用節(jié)點(diǎn)的影響力在特定的局部范圍內(nèi)的傳播過程來近似其在全局范圍內(nèi)的傳播過程。為了度量節(jié)點(diǎn)在特定局部范圍內(nèi)的影響力，引入最短距離、局部鄰居以及局部域的概念，并結(jié)合局部域拓?fù)浣Y(jié)構(gòu)建立影響力度量模型。

定義2節(jié)點(diǎn)間最短路徑的長(zhǎng)度即為節(jié)點(diǎn)間的最短距離。假設(shè)（?v）ivi?V，（?vj）vj?V，若vi到vj的最短路徑為p(vi,vj)且p(vi,vj)=則節(jié)點(diǎn)vi到vj的最短距離

定義3給定節(jié)點(diǎn)vi，若vj是vi的可達(dá)節(jié)點(diǎn)且到vi的距離不大于D，則稱vj是vi的局部鄰居。

定義4給定節(jié)點(diǎn)及其局部鄰居構(gòu)成的節(jié)點(diǎn)集合以及這些節(jié)點(diǎn)間的邊構(gòu)成的邊集合共同組成此節(jié)點(diǎn)的局部域，記為AL。以節(jié)點(diǎn)vi為中心的局部域記為AL(vi)，表示如下：

定義5對(duì)于給定節(jié)點(diǎn)，其局部域影響力為以此節(jié)點(diǎn)為中心的局部域拓?fù)浣Y(jié)構(gòu)所決定的節(jié)點(diǎn)傳播信息的能力，記為Cr。（?vi）vi?V，Cr(vi)計(jì) 算如下：

以8 節(jié)點(diǎn)網(wǎng)絡(luò)中節(jié)點(diǎn)v1為例說明局部域影響力的計(jì)算過程，如圖2 所示，其中圓圈內(nèi)字母及其數(shù)字下標(biāo)表示節(jié)點(diǎn)，有向邊上的數(shù)值代表兩節(jié)點(diǎn)間的邊影響權(quán)重。假設(shè)D=3，節(jié)點(diǎn)v1的局部域由節(jié)點(diǎn)v1與其局部鄰居節(jié)點(diǎn)｛v2，v3，v4，v5｝以及它們之間的邊構(gòu)成。

圖2 計(jì)算節(jié)點(diǎn)的Cr 值示例Fig.2 Example of computing Cr values of nodes

2.3 影響力重疊檢測(cè)

節(jié)點(diǎn)之間可能存在影響力重疊現(xiàn)象，導(dǎo)致多個(gè)節(jié)點(diǎn)的共同影響力小于各節(jié)點(diǎn)影響力之和。為了保證影響力的傳播范圍最大，在選擇種子節(jié)點(diǎn)時(shí)應(yīng)考慮節(jié)點(diǎn)之間可能存在的影響力重疊現(xiàn)象。權(quán)衡影響力重疊檢測(cè)成本和消除影響力重疊后的收益，本文允許影響力重疊，但是應(yīng)避免影響力過度重疊，并利用式（7）判定給定節(jié)點(diǎn)間是否存在影響力重疊。

其中：η表示過度重疊判定閾值分別表示vi和vj的出邊直接連接的節(jié)點(diǎn)構(gòu)成的集合。在式（7）的基礎(chǔ)上，本文定義了重疊比因子，判定一個(gè)集合中節(jié)點(diǎn)間影響力重疊的程度。

定義6重疊比因子為給定集合中影響力過度重疊的節(jié)點(diǎn)在集合中所占的比例，記為ω。給定集合C?V，該集合的重疊比因子計(jì)算如下：

2.4 算法描述

首先根據(jù)Cr 值構(gòu)建候選種子節(jié)點(diǎn)列表，并將該列表中第一個(gè)節(jié)點(diǎn)作為種子加入種子集合。然后依次從候選種子節(jié)點(diǎn)列表中選擇一個(gè)節(jié)點(diǎn)，并計(jì)算該節(jié)點(diǎn)加入種子集合后該種子集合的重疊比因子。若該重疊比因子小于預(yù)定義的重疊比閾值，則將此節(jié)點(diǎn)加入種子節(jié)點(diǎn)集合，否則不能將此節(jié)點(diǎn)加入種子集合。重復(fù)上述過程，直至選出足夠數(shù)量的種子節(jié)點(diǎn)。算法1 給出了基于局部域的影響力最大化算法的偽代碼。

算法1基于局部域的影響力最大化算法

對(duì)列表中的每個(gè)候選種子節(jié)點(diǎn)按順序挑選，在最壞情況下需要遍歷所有候選種子節(jié)點(diǎn)。對(duì)于每個(gè)遍歷到的候選種子節(jié)點(diǎn)，均要根據(jù)式（8）檢測(cè)是否與某種子節(jié)點(diǎn)存在影響力過度重疊。給定種子節(jié)點(diǎn)數(shù)k，判定某個(gè)候選種子節(jié)點(diǎn)是否與某個(gè)種子節(jié)點(diǎn)存在過度重疊的時(shí)間復(fù)雜度為O(kd)，其中d為節(jié)點(diǎn)平均出度?；谝陨戏治?，從節(jié)點(diǎn)集合V中選出k個(gè)種子節(jié)點(diǎn)的時(shí)間復(fù)雜度在最壞情況下為O(|V|kd)，也可表示為O(|E|k)。除種子集合S外，本文算法對(duì)于每個(gè)節(jié)點(diǎn)還存儲(chǔ)了flag和ωS兩個(gè)變量，且最多為列表中所有節(jié)點(diǎn)均設(shè)置，因此算法的空間復(fù)雜度在最壞情況下為O(|V|)。

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

實(shí)驗(yàn)選取5 種對(duì)比算法，通過在6 個(gè)不同規(guī)模的真實(shí)數(shù)據(jù)集上比較算法的影響力傳播范圍、算法運(yùn)行時(shí)間等指標(biāo)來驗(yàn)證本文算法的正確性和有效性。

3.1 數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境

表1 給出了選用的數(shù)據(jù)集信息，其中，|V|表示節(jié)點(diǎn)總數(shù)，|E|表示邊總數(shù)，d為節(jié)點(diǎn)平均出度。所有數(shù)據(jù)集均來自斯坦福大學(xué)的大型網(wǎng)絡(luò)數(shù)據(jù)集（http：//snap.stanford.edu/data/）。

表1 數(shù)據(jù)集設(shè)置Table 1 Dataset setting

實(shí)驗(yàn)選用MaxDegree 算法、PageRank 算法、ICGW算法、Closeness 算法和IDD1 算法5 種對(duì)比算法。這些對(duì)比算法分別采用最大度策略［13］、PageRank 方法［20］、約束貪婪方式下的影響力節(jié)點(diǎn)識(shí)別方法［21］、Closeness方法［8］和改進(jìn)的度折扣啟發(fā)式策略［22］選擇種子節(jié)點(diǎn)。所有算法均用Python 實(shí)現(xiàn)，在相同的Windows 平臺(tái)上運(yùn)行。該平臺(tái)采用Intel Core i5 1.80 GHz 處理器，配置8 GB 內(nèi)存空間。

實(shí)驗(yàn)采用的評(píng)價(jià)指標(biāo)分別為影響力傳播范圍、算法運(yùn)行時(shí)間和占用的內(nèi)存空間大小。影響力傳播范圍用激活的節(jié)點(diǎn)數(shù)表示，該值越大越好，算法運(yùn)行時(shí)間和內(nèi)存空間占用則越小越好。

3.2 結(jié)果分析

在本文算法中，參數(shù)η、θ和D分別表示過度重疊判定閾值、線性閾值模型下的激活閾值和局部域范圍。在本次實(shí)驗(yàn)中，取值分別為0.2、0.4 和3。該部分給出的所有結(jié)果都是相關(guān)算法獨(dú)立運(yùn)行1 000 次計(jì)算的平均結(jié)果。

圖3 給出了各算法的影響力傳播范圍，其中k表示種子節(jié)點(diǎn)數(shù)。由圖3 可知：本文算法在所有數(shù)據(jù)集上的種子節(jié)點(diǎn)的影響力平均傳播范圍最大，其次是IDD1 算法和ICGW 算法；本文算法相比 于MaxDegree算法、PageRank算法和Closeness算法所選種子節(jié)點(diǎn)的影響力平均傳播范圍較??；本文算法在Cora 數(shù)據(jù)集上表現(xiàn)最好，所選種子節(jié)點(diǎn)影響力平均傳播范圍分別是IDD1 算法和ICGW 算法的1.77 倍和1.47 倍；本文算法在Escorts-Dynamic 數(shù)據(jù)集上表現(xiàn)最差，但影響力傳播范圍仍是IDD1 算法和ICGW 算法的1.04 倍和1.03 倍。

圖3 6 種算法的影響力傳播范圍比較Fig.3 Comparison of influence dissemination range among six algorithms

在種子節(jié)點(diǎn)數(shù)相同的情況下，本文算法的傳播結(jié)果始終優(yōu)于IDD1 算法和ICGW 算法。這是由于本文算法具備影響力重疊控制能力，因此在選擇相同的種子時(shí)，它對(duì)節(jié)點(diǎn)的組合影響力更加敏感。在所有數(shù)據(jù)集上，本文算法的影響力傳播范圍在種子節(jié)點(diǎn)數(shù)從10 到50 階段幾乎都呈線性增長(zhǎng)，這表明了本文算法識(shí)別高影響力節(jié)點(diǎn)群體的能力更強(qiáng)。

減少種子節(jié)點(diǎn)選擇所消耗的時(shí)間是本文算法設(shè)計(jì)的另一個(gè)重要目標(biāo)。圖4 給出了在6 個(gè)數(shù)據(jù)集上各種算法選取k個(gè)種子節(jié)點(diǎn)所用的平均運(yùn)行時(shí)間?？傮w來看，MaxDegree 算法平均運(yùn)行時(shí)間最短，其次是本文算法、IDD1算法、PageRank 算法 和ICGW 算法，Closeness 算法平均運(yùn)行時(shí)間最長(zhǎng)。由于IDD1 算法和ICGW 算法的影響力傳播范圍和本文算法最為接近，而其他3 種算法的影響力傳播范圍則遠(yuǎn)小于本文算法，失去了比較意義，因此在評(píng)價(jià)算法的時(shí)間和空間性能時(shí)只與IDD1 算法和ICGW 算法比較。

由圖4 可知：本文算法在P2p-Gnutella04 數(shù)據(jù)集上表現(xiàn)最好，運(yùn)行時(shí)間分別是IDD1 算法和ICGW 算法的7% 和8%；本文算法在Cora 數(shù)據(jù)集上表現(xiàn)最差，但運(yùn)行時(shí)間仍僅是ICGW 算法的17%；本文算法在Wiki-Vote 數(shù)據(jù)集和Cora 數(shù)據(jù)集上的運(yùn)行時(shí)間多于IDD1 算法，但在其他數(shù)據(jù)集上的運(yùn)行時(shí)間都少于IDD1 算法。因此，從所有數(shù)據(jù)集來看，本文算法要略優(yōu)于IDD1 算法。

圖4 6 種算法的運(yùn)行時(shí)間比較Fig.4 Comparison of execution time among six algorithms

通過實(shí)驗(yàn)評(píng)估本文算法的空間復(fù)雜度。算法在執(zhí)行過程中占用的內(nèi)存空間越多，其空間復(fù)雜度越高，反之亦然。在實(shí)驗(yàn)過程中，隨機(jī)選擇k=50 的運(yùn)行過程，比較各算法的內(nèi)存占用情況。表2 給出了在k=50 時(shí)各算法在不同數(shù)據(jù)集上運(yùn)行時(shí)占用的內(nèi)存空間。由表2 可知：在所有數(shù)據(jù)集上運(yùn)行時(shí)，本文算法所占用的內(nèi)存空間均小于ICGW 算法；除了Fb-Forum 數(shù)據(jù)集和P2p-Gnutella04 數(shù)據(jù)集之外，本文算法的內(nèi)存空間占用都低于IDD1 算法。從整體來看，本文算法的內(nèi)存空間占用情況要優(yōu)于IDD1算法。

表2 6 種算法在不同數(shù)據(jù)集上運(yùn)行時(shí)所占用的內(nèi)存空間Table 2 Memory space consumed by six algorithms when running on different datasets MB

4 結(jié)束語(yǔ)

針對(duì)度量用戶影響力的全局性和局部性度量指標(biāo)各自存在的局限性，本文利用節(jié)點(diǎn)在局部域內(nèi)的影響力近似其在全局范圍內(nèi)的影響力，提出一種基于局部域的影響力最大化算法。構(gòu)建以節(jié)點(diǎn)為中心的局部域影響力度量模型，依據(jù)影響力度量模型篩選候選種子節(jié)點(diǎn)集合。利用重疊比因子刻畫候選種子節(jié)點(diǎn)與種子節(jié)點(diǎn)集合間的重疊程度，并根據(jù)重疊比因子決定是否將此候選種子節(jié)點(diǎn)選作種子節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的正確性與有效性。下一步可將本文算法擴(kuò)展應(yīng)用于動(dòng)態(tài)社交網(wǎng)絡(luò)，利用其能高效準(zhǔn)確選取高影響力種子節(jié)點(diǎn)的優(yōu)勢(shì)，設(shè)計(jì)并實(shí)現(xiàn)高影響力節(jié)點(diǎn)集合的增量式更新方法。