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

沈記全，林 帥，李志瑩

（河南理工大學計算機科學與技術學院，河南焦作 454003）

0 概述

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

本文結合三度分隔原理［17］，提出用節點在局部范圍內的影響力近似其在全局范圍內影響力的算法。根據網絡拓撲結構構造生成圖，依據生成圖劃分每個節點對應的局部域，根據節點在對應局部域內的影響力篩選候選種子節點。計算每個節點與種子集合的重疊比因子，并據此決定候選種子節點是否能成為種子節點。通過在真實數據集上的實驗結果以驗證本文算法的正確性和有效性。

1 相關知識

1.1 影響力最大化問題

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

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

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

1.2 影響力傳播模型

線性閾值（Linear Threshold，LT）模型［18-19］可以用來模擬影響力的傳播過程。在LT 模型中，節點只能處于激活狀態或者非激活狀態。激活狀態的節點通過有向邊試圖激活處于非激活狀態的鄰居節點。對于非激活狀態的節點，當所有激活狀態的鄰居節點對其影響力之和大于該節點的激活閾值時，該非激活節點就轉為激活狀態。當網絡中不再有節點被激活（即由非激活狀態轉為激活狀態）時，影響力的傳播過程收斂。

圖1 給出了根據LT 模型模擬影響力傳播的過程，其中，灰色圓表示激活節點，白色圓表示非激活節點，有向邊上數字表示箭尾節點對箭首節點的影響力。節點v1、v2、v5和v6為種子節點，在傳播開始時處于激活狀態；其他節點則處于非激活狀態。整個傳播過程經過3 輪迭代收斂。

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

2 影響力最大化算法

本文針對局部性度量指標構造生成圖，根據影響力傳播的三度分隔原理構建局部影響力度量模型，依據局部影響力度量模型設計基于局部域影響力的種子節點選擇算法。

2.1 權重感知的生成圖構造

邊影響權重根據自環和多邊屬性計算。邊權重反映了節點間的親密程度，影響力的傳播過程又受鄰居間關系疏密的影響。因此，邊影響權重的計算過程中應考慮自環和多邊現象。

自環指的是一種特殊的環結構，這種環狀結構只包含一個節點。社交網絡中用戶可能發起只有自己參與的社交活動，從而在對應的社交網絡圖中形成只有該節點參與的自環。自環多的節點活躍度較高，在信息傳播過程中會主動地影響其他節點。本文引入自環因子度量自環對節點能力的影響。自環因子計算如下：

其中：Rvi表示節點vi的自環因子；ψ（vi）表示節點vi每個自環的權重。在無權網絡中，ψ（vi）默認為1，此時節點自環因子等于節點的自環個數。

多邊指的是社交網絡圖中兩個節點間有多條邊存在。在社交網絡中，兩個節點間的一次互動會在社交網絡圖中對應的節點間產生一條邊。當兩個節點間有多次互動時，它們之間就會有多條邊。然而，隨著邊數的增加，圖的存儲和遍歷成本也會增加。在不影響圖的存儲和計算成本的前提下，本文引入多邊因子，用以度量節點間存在的多邊現象對信息傳播過程的影響。多邊因子隨著兩個節點間邊的增多而增大。多邊因子計算如下：

結合自環因子和多邊因子，本文引入邊影響權重，描述節點間的影響力。

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

根據自環因子、多邊因子和邊影響權重構造生成圖，并且生成圖是有向帶權圖。

2.2 局部域影響力度量

影響力的全局性度量指標往往從拓撲結構的整體出發對節點的影響力進行全面準確的衡量，但是卻存在計算復雜度高的問題。根據影響力傳播遵循的三度分隔原理［17］，即節點的影響力在相距不超過三跳的鄰居節點間傳播時隨著距離的增大而不斷衰減，當傳播距離超過三跳時幾近消失。本文根據三度分隔特性，利用節點的影響力在特定的局部范圍內的傳播過程來近似其在全局范圍內的傳播過程。為了度量節點在特定局部范圍內的影響力，引入最短距離、局部鄰居以及局部域的概念，并結合局部域拓撲結構建立影響力度量模型。

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

定義3給定節點vi，若vj是vi的可達節點且到vi的距離不大于D，則稱vj是vi的局部鄰居。

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

定義5對于給定節點，其局部域影響力為以此節點為中心的局部域拓撲結構所決定的節點傳播信息的能力，記為Cr。（?vi）vi?V，Cr(vi)計 算如下：

以8 節點網絡中節點v1為例說明局部域影響力的計算過程，如圖2 所示，其中圓圈內字母及其數字下標表示節點，有向邊上的數值代表兩節點間的邊影響權重。假設D=3，節點v1的局部域由節點v1與其局部鄰居節點｛v2，v3，v4，v5｝以及它們之間的邊構成。

圖2 計算節點的Cr 值示例Fig.2 Example of computing Cr values of nodes

2.3 影響力重疊檢測

節點之間可能存在影響力重疊現象，導致多個節點的共同影響力小于各節點影響力之和。為了保證影響力的傳播范圍最大，在選擇種子節點時應考慮節點之間可能存在的影響力重疊現象。權衡影響力重疊檢測成本和消除影響力重疊后的收益，本文允許影響力重疊，但是應避免影響力過度重疊，并利用式（7）判定給定節點間是否存在影響力重疊。

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

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

2.4 算法描述

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

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

對列表中的每個候選種子節點按順序挑選，在最壞情況下需要遍歷所有候選種子節點。對于每個遍歷到的候選種子節點，均要根據式（8）檢測是否與某種子節點存在影響力過度重疊。給定種子節點數k，判定某個候選種子節點是否與某個種子節點存在過度重疊的時間復雜度為O(kd)，其中d為節點平均出度。基于以上分析，從節點集合V中選出k個種子節點的時間復雜度在最壞情況下為O(|V|kd)，也可表示為O(|E|k)。除種子集合S外，本文算法對于每個節點還存儲了flag和ωS兩個變量，且最多為列表中所有節點均設置，因此算法的空間復雜度在最壞情況下為O(|V|)。

3 實驗與結果分析

實驗選取5 種對比算法，通過在6 個不同規模的真實數據集上比較算法的影響力傳播范圍、算法運行時間等指標來驗證本文算法的正確性和有效性。

3.1 數據集與實驗環境

表1 給出了選用的數據集信息，其中，|V|表示節點總數，|E|表示邊總數，d為節點平均出度。所有數據集均來自斯坦福大學的大型網絡數據集（http：//snap.stanford.edu/data/）。

表1 數據集設置Table 1 Dataset setting

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

實驗采用的評價指標分別為影響力傳播范圍、算法運行時間和占用的內存空間大小。影響力傳播范圍用激活的節點數表示，該值越大越好，算法運行時間和內存空間占用則越小越好。

3.2 結果分析

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

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

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

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

減少種子節點選擇所消耗的時間是本文算法設計的另一個重要目標。圖4 給出了在6 個數據集上各種算法選取k個種子節點所用的平均運行時間。總體來看，MaxDegree 算法平均運行時間最短，其次是本文算法、IDD1算法、PageRank 算法 和ICGW 算法，Closeness 算法平均運行時間最長。由于IDD1 算法和ICGW 算法的影響力傳播范圍和本文算法最為接近，而其他3 種算法的影響力傳播范圍則遠小于本文算法，失去了比較意義，因此在評價算法的時間和空間性能時只與IDD1 算法和ICGW 算法比較。

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

圖4 6 種算法的運行時間比較Fig.4 Comparison of execution time among six algorithms

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

表2 6 種算法在不同數據集上運行時所占用的內存空間Table 2 Memory space consumed by six algorithms when running on different datasets MB

4 結束語

針對度量用戶影響力的全局性和局部性度量指標各自存在的局限性，本文利用節點在局部域內的影響力近似其在全局范圍內的影響力，提出一種基于局部域的影響力最大化算法。構建以節點為中心的局部域影響力度量模型，依據影響力度量模型篩選候選種子節點集合。利用重疊比因子刻畫候選種子節點與種子節點集合間的重疊程度，并根據重疊比因子決定是否將此候選種子節點選作種子節點。實驗結果驗證了該算法的正確性與有效性。下一步可將本文算法擴展應用于動態社交網絡，利用其能高效準確選取高影響力種子節點的優勢，設計并實現高影響力節點集合的增量式更新方法。