社交網絡中對立影響最大化算法

楊書新，梁 文，朱凱麗

（江西理工大學信息工程學院，江西贛州 341000）

（*通信作者電子郵箱jhcpl05@163.com）

0 引言

社交網絡用戶間的關系是多樣化的，或協作配合、或對立排斥或動態博弈，傳統單源信息的影響傳播研究無法描述其復雜性，因此產生了多源信息影響傳播的研究。多源信息影響最大化也稱之為競爭影響最大化。謠言阻礙、捆綁銷售、黨派博弈、病毒營銷、游戲競賽的規則模擬均屬于多源信息影響最大化的研究問題［1-3］。現有工作主要依靠經典獨立級聯（Independent Cascade，IC）模型和線性閾值（Linear Threshold，LT）模型開展研究，部分用于求解競爭影響最大化問題的算法僅適用于特定結構的數據，尚缺乏普適性。針對上述不足，本文擴展熱量傳播模型為多源熱量傳播模型，研究對立影響最大化問題。

1 相關工作

2007 年，Bharathi 等［4］首次給出競爭影響最大化（Competitive Influence Maximization）問題的定義：已知種子集SA分布的情況下，選拔種子集SB，使SB的影響傳播效果最大化，其中SA和SB代表不同信息源。競爭影響最大化的相關研究產生了許多具有代表性的成果，本文圍繞競爭影響傳播模型、競爭影響傳播問題的優化算法兩方面介紹國內外研究現狀。關于競爭傳播模型，已有相關工作主要針對單源信息的獨立級聯（IC）模型和線性閾值（LT）模型加以擴展。基于IC模型，文獻［5-6］提出了基于IC 模型的多實體競爭（Multi-Campaign IC）模型、波擴散（Wave Propagation）模型及基于距離的（Distance-based）多源信息傳播模型。Borodin等［7］率先利用LT 模型研究競爭影響最大化問題，設計了權重競爭閾值（Weight Competitive LT）模型、分隔競爭閾值（Separate Competitive LT）模型。He 等［8］首次定 義了競爭線性 閾值（Competitive LT）模型。

關于競爭影響最大化問題的優化算法，相關工作已取得了積極進展。文獻［4］提出的FPTAS（Fully Polynomial-Time Approximation Scheme）在理論上具有63%的下界保證。針對競爭影響最大化問題，He 等［8］提出了適用于有向無環圖的CLDAG（Competitive Local Directed Acyclic Graph）算法。Zhu等［9］研究了基于位置感知的影響阻礙最大化（Location-aware Influence Blocking Maximization，LIBM）問題，利用位置數據劃分區域，設計了LIBM-H和LIBM-C兩種啟發式算法，實驗表明兩種算法均能有效求解競爭最大化問題。文獻［4，9］的算法僅適用于樹型數據結構。Pham 等［10］研究了回避多余用戶（unwanted users）的競爭影響最大化問題，多余用戶是非預期內被影響的特定群體。文獻［10］基于競爭閾值模型證明了該問題是NP-Complete問題，設計了一種啟發式方法并在真實數據集中驗證了有效性。

本文考慮信息對立式競爭影響傳播的形式。對立影響傳播是指多源信息傳播中，成功影響個體的信息是唯一的。對立信息的影響傳播可以概括許多生活化的場景。例如社交網絡中用戶對輿論事件正面及負面觀點往往是對立的。或是通過社交網絡的廣告影響，用戶確定購買某個品牌商品后，短期內不會考慮再購買同類別其他品牌商品。針對信息的對立競爭形式，本文擴展單源熱量傳播模型為多源熱量傳播模型，設計了預選式貪心算法，并在編程爬取的大規模社會網絡數據集中驗證其有效性。

2 問題及模型的定義

2.1 對立影響最大化問題的定義

給定社交網絡G=（V，E）與信息傳播模型，其中：V表示由網絡節點構成的集合，E表示網絡節點間邊的集。已知種子集SA?V的分布情況，選拔由k個節點構成的種子集SB?V且SB?VSA，使SB的影響收益σ(SB，SA)最大化，其中SA和SB代表對立的信息源。對立影響最大化（Reverse Influence Maximization）問題的形式化表達為：

當SA=?時，傳統單源信息傳播的影響最大化問題即為對立影響最大化問題的特例。σ(SB，SA)是集合V的子模函數，因此仍具有子模特性。以σ(SB，SA)為目標函數，貪心近似（Greedy Approximation）算法經過有限次的迭代計算，可以得到保證下界的近似最優種子集SB，即≥(1-1/e)σ(SB，SA)。

2.2 多源熱量傳播模型的推導

根據物理經驗，熱量總是自高處向低處轉移以達到均衡。社交網絡的信息傳播過程與此相似，向外傳播影響的個體總是最先被激活的種子。同樣，設具有不同標記的熱量與不同的信息是對應的，則單源信息的熱量傳播（Heat Diffusion，HD）模型［11］可被擴展為多源信息熱量傳播（Multi-Source HD，MSHD）模型。該模型可用于模擬對立信息的影響傳播，解決對立影響最大化問題。下面給出MSHD模型的推導過程。

給定有向社交網絡G=（V，E），G中的任意一個節點vi在傳播初始時刻t=0時，其熱量參數記為hi(0)；t≥1時，vi的熱量值記為hi(t)。采用h(ξε，t)記錄G中全部節點在t時刻的熱值，向量長度為節點總數n(n=|V|)，其表達式為：

其中，ξε(ε＞2，ε∈Z+)對應的是ε個信息源的不同激活狀態。熱量總是沿有向邊，自高向低轉移。以節點vi為例，若節點vi與節點vj間存在有向邊，即evj，vi∈E。根據節點有向邊的不同方向，將vj與vi的熱量轉移分兩種情況討論。

考慮情況一，若節點vj指向節點vi，此時節點vi熱值為0，或節點vj和vi的激活態相同且vj熱值高于vi。自t時刻開始，經過一段時間Δt后，熱量從vj向vi轉移的量為(α?hj(t)?Δt)/dj，dj表示節點vi的出度鄰居數量，導熱系數（Thermal Conductivity）α表示信息的傳播能力。在Δt的時間長度內，節點vi收到的總熱量記為Ghi(t，Δt)。

考慮情況二，若節點vi指向節點vj，此時節點vi和vj的激活態相同且vi熱值高于vj。自t時刻開始，經過一段時間Δt后，熱量自vi向vj轉移的量設為Phi(t，Δt)。則節點vi對其前向節點及后繼節點的能量轉移公式為：

仍以節點vi為例，在t+Δt時刻內，節點vi所轉移的熱量為應為hi(t+Δt)-hi(t)，其表達函數為：

式中，φi是熱量輸出的標志位，其值只能為0 或1。當φi為0時，表示熱量無法發生轉移，即節點vi無后繼節點（di=0）或節點vi與其鄰居的熱量標記不同(ξε(i) ≠ξε(j))；當φi值為1時，熱量可以發生轉移，即節點vi存在后繼節點（di＞0）且節點vi與其鄰居的熱量標記相同(ξε(i)=ξε(j))。根據泰勒公式（Taylor series），整理式（5）得到節點在t時刻的熱量表達式為：

其中：e是自然數，H是圖G中節點連接關系的n階矩陣：

同樣，根據節點當前的標記狀態、熱量值的大小加以相應的調整，MSHD 模型也可適用于無向網絡。將MSHD 模型應用至實際問題中，以對立的兩個信息源為例即可。

2.3 打破平局規則的設定

傳播模型和打破平局規則（tie-breaking rule）［12］是對立信息影響傳播機制的核心。打破平局規則用于處理節點被多源對立信息同時影響的狀態響應問題。現實社交網絡中，個體所接收的信息五花八門，而其最終采納的信息源總是唯一的。以市場上存在競爭的筆記本電腦品牌為例，用戶若鎖定某品牌并購買，該用戶在短期內不會購買同類別商品。可以認為不同品牌的商品對普通用戶的影響是對立傳播的。為合理表達上述情境中個體的決策問題，本文設計了一種隨機規則（random rule）。該規則設定激活同一個節點的信息源是唯一的，且被激活的過程不可逆，其具體步驟見圖1。

以圖1（a）的簡單網絡為例，此時節點u同時面對4股對立的熱源，采用隨機規則，節點u的狀態響應的過程如下：列舉由節點u直接鄰居構成的序列，如圖1（b），將圖1（b）的序列亂序排列得到圖1（c）。根據圖1（c）的排列次序，種子以激活概率p（本文設為0.5）依次嘗試激活節點u，首個激活節點u的信息源將作為成功激活節點u的種子。節點u被激活后，不再接受其他狀態種子的影響。

圖1 隨機規則Fig.1 Random rule

2.4 模型的傳播步驟及示例

2.2 和2.3 節完善了MSHD 模型的傳播機制，下面給出該模型的傳播步驟：初始時刻t=0，對立種子集SA已知，部署種子集SB至網絡G中并賦予初始熱量。當t＞0時，集合SA和SB中的初始節點參照熱量傳導公式沿有向邊轉移熱量，當節點預接收的熱量不屬于同個信息源，采用隨機規則處理。重復該過程直至經過有限步長，統計當前熱值高于熱量閾值的節點，并標記為激活節點。以圖2 的簡單網絡為例，給出MSHD模型的仿真計算過程。

圖2 MSHD模型的計算過程Fig.2 Computing process of MSHD model

假定網絡中存在A、B兩種對立信息源，初始節點的熱量值為20，導熱系數為0.15，f（）表示節點當前的熱量值，節點的熱量激活閾值等于0.2。當t=0時，網絡中僅有S1、S2作為初始節點被激活；當t=1時，熱量開始傳導，對立種子S1、S2共同影響節點u1、u2、u3。根據2.3節的隨機規則，考慮節點u1、u3被信息B激活以及節點u2被信息A激活的情況（對應圖2（b）至圖2（d））；當t=2時，節點u4接收節點u1、u3共同傳導的熱量，根據式（6），f（u4）=0.3。傳播結束，根據熱量閾值，信息A對應的激活節點數量為2，信息B對應的激活節點數量為4。

3 預選式貪心近似算法

根據2.2 節，熱量值和激活閾值是多源熱量模型傳播機制的重要組成部分，該部分信息可用于統計個體的傳播收益，本章基于多源熱量模型對個體影響力的評價特性及目標優化函數的子模特性，設計了預選式貪心近似（Pre-Selected Greedy Approximation，PSGA）算法。該算法對網絡中的每個節點賦予0～1 隨機值，將隨機值大于攔截值r、出度值大于平均出度值的節點加入臨時種子集S，且該臨時集的長度不能大于k。在M次的迭代過程中，根據式（6）和隨機規則，統計第m次迭代的臨時種子集Sm中全部個體的影響收益，迭代結束后將其收益值降序排列，取Top-k節點作為種子。

對于有向的社會網絡圖G，選擇節點出度及出度均值作為PSGA 算法關鍵指標的理由如下：在有限的傳播步長內，熱量和影響總是沿有向路徑向外傳遞和擴散，因此節點的出度值可概括其傳播能力。其次，度方法的同一度量值存在若干節點與其對應，眾多具有相同度量值的節點被確定為種子時其順序相對隨機，存在高影響力節點被排除的可能。PSGA算法的隨機策略可避免該缺陷，并減少計算量。算法1 給出了PSGA算法的運行步驟。

在算法1中，u.degree表示節點u出度值，avgD（G）表示圖G中節點的出度均值，I（u）表示節點u的傳播收益，SM表示第M次迭代的臨時種子集，getSize（）函數用于獲取臨時種子集Sm的寬度。其中，第2）～7）行含義為：對于每個節點進行判斷，將滿足條件的節點加入臨時種子集，作為種子候選。

算法1 預選式貪心近似算法。

4 仿真結果及分析

4.1 網絡數據集

表1列舉了仿真實驗所需的四組網絡數據，n表示網絡節點數量，m表示邊的數量，＜c＞表示網絡的平均聚類系數，type表示網絡類型。表1中：p2p-Gnutella08 和CA-HepTH 網絡是SNAP的開源數據集，分別表示分布式協議交互網絡和維基百科的管理員投票網絡。twitter 數據集通過編程爬取自twitter社交平臺，記錄的是用戶間的互粉關系。TecentWeibo 爬取自騰訊微博，該數據記錄的是朋友間的關注關系。

表1 實驗網絡基本特征Tab.2 Basic characteristic of experimental networks

4.2 仿真實驗條件

本節介紹仿真實驗的對比算法、算法特點、實驗參數和評價方法。

仿真實驗采用C++語言編寫，在內存為16 GB 的個人工作站上運行。實驗選取局部中心性（Local Centrality，LC）［13］、SIR（Susceptible Infected Recovered）評價方法、k-shell［14］方法、基于局部集體影響的自適應排序（Local Collective Influence Rank-Adaptive Recalculation，LCIR-AR）算法［15］、局部三角中心性（Local Triangle Centrality，LTC）方法［16］、密度中心性（Density Centrality，DC）方法［17］同PSGA 算法對比。LC、kshell、LCIR-AR 及LTC 均屬于依賴網絡拓撲特性的啟發式算法，SIR 評價屬于模型評價方法。SIR 評價方法利用傳染病模型計算個體的影響值F（t），每個節點的F（t）均為重復運行103次的均值。其中，twitter 和TecentWeibo 網絡數據因節點數量較多，分別重復運行100 次及50 次。SIR 模型設定傳染概率為0.015，傳播步長為10，治愈概率為1/k，k為網絡節點度的均值。傳播步長設定太短會抑制部分節點的傳播能力，導致傳播停止的時刻提前，傳播步長參數對應的值較高，可以反映出節點的真實傳播能力。SIR 模型相關參數的設定是復雜網絡傳播動力學文獻較為常見的設置辦法，該方法也常用于節點重要性的評估領域，例如本文所對比的文獻［13，16］。實驗設定LCIR-AR 算法的控制參數為0.3，度量層級為3，根據對比文獻［15］的描述，此時該參數對應的實驗效果最佳。PSGA算法的攔截值r設為0.85，迭代次數M設為104。

以A、B兩種對立信息為例，設100個由隨機選拔得到的A種子已知。為了滿足實驗的公平性，MSHD 模型的傳播步長同SIR 評價模型的傳播步長均為10。MSHD 模型初始熱量值100，激活閾值0.5，導熱系數0.15。B信息的種子個數自0 至50 以2 為間隔，逐批投放。其中，B種子仿真收益的計算公式等于B種子收益同A種子收益的差。當信息A的種子集SA和信息B的種子集SB存在相同節點，即SA∩SB≠?時，采用拋硬幣式隨機規則處理該沖突。因所采用的沖突處理辦法具有隨機性，最終仿真收益均為重復運行104次的均值。評價對立影響最大化算法的優劣，從運行時長及影響收益兩方面判斷。運行時長短，影響收益高，則算法更優。

4.3 仿真結果及分析

圖3描述的是7種算法在四組網絡數據集的收益表現，其縱坐標影響收益值被歸一化處理，橫坐標表示種子數量。

圖3 7種算法的仿真收益比較Fig.3 Simulated revenue comparison of seven algorithms

根據圖3 仿真結果，PSGA 算法隨著種子投放數量的增加，其影響收益漲幅十分明顯。twitter 數據集種子數量小于8以及TecentWeibo 數據集種子數量小于14時，PSGA 算法的優勢不夠明顯，但整體上PSGA 所獲得的收益最高。尤其是在p2p-Guntella08 和CA-HepTH 數據集中，PSGA 算法表現最優。可以認為，在對立影響最大化問題中，種子投放數量越多，PSGA 算法越能體現出優越性。SIR 模型作為復雜網絡度量單體影響力的評價標準，在解決對立影響最大化問題中的表現遜于PSGA 算法。密度中心性（DC）方法在所對比的啟發式算法中表現最優，但其整體表現仍無法超過PSGA 算法。LC、LTC、LCIR-AR 及k-shell 方法在四組數據集中的收益排名并不穩定，說明在不同規模和不同類型的網絡中，其適用性有限。以k-shell方法對TecentWeibo 網絡數據的度量結果為例，k值為57 的個體有759 個，自759 個節點中選拔50 個作為種子，其次序相對隨機。因此，k-shell方法度量值區分度不高是其影響收益較低的關鍵因素。LTC 方法統計節點所處拓撲結構的三元閉包數量，在有向圖中其表達的含義為節點經有向路徑指向自己的回路數量，在無向圖中，其表達含義為節點與緊鄰個體的緊密程度。可以認為，針對對立影響最大化問題，三元閉包的統計量無法高效地反映節點潛在的博弈和競爭能力。

為直觀表達不同算法的影響收益水平，圖4 給出了各方法的平均收益。根據圖4 的仿真結果，在四組數據集中，PSGA 算法的平均收益最多，DC算法表現次優，其他算法的表現則不夠穩定。

圖5 給出了仿真實驗每運行104次的平均時間。為統計每個節點的F（t）值，SIR 模型在四個數據集上的運行時間均超過3.5×105s（4 d），TecentWeibo 網絡數據的運行時間超過1.8×106s（20 d），其平均時長在圖中沒有標注。根據圖5統計結果，整體上DC 算法的平均運行時間最短，在所對比的啟發式算法中，LC 算法的運行時間較長。根據4.2 節對立影響最大化的兩項評價指標，PSGA 算法同SIR 評價方法相比，影響收益高、運行時長短，具有優越性。同其他啟發式算法相比，PSGA算法雖耗時更久，但平均收益領先于啟發式算法。可以認為，PSGA算法能夠有效求解對立影響最大化問題。

圖4 7種算法的平均收益比較Fig.4 Average revenue comparison of seven algorithms

圖5 7種算法的運行時間比較Fig.5 Running time comparison of seven algorithms

4.4 種子富集性分析

為進一步分析各算法的仿真收益表現，設計了種子富集性實驗，探究各算法所選種子集的特征。種子富集性（richclub）也稱富人俱樂部現象，它描述的是關鍵節點間邊的密集情況。種子節點間連接緊密，則不利于影響力的擴散；種子節點間連接稀疏，則有利于初期快速地擴散影響。以圖6（a）的簡單網絡為例，該網絡中被對立信息A激活的節點已知。當B種子以圖6（b）的方式投放，種子節點相互抱團，處于網絡邊緣的種子無法對傳播起到促進作用。當B種子以圖6（c）的方式投放，則有利于初期的影響傳播。圖6（b）中B信息種子間邊的數目為7，圖6（c）中B種子間邊的數目為0。可以認為種子節點間邊的數量能夠反映出種子集的富集程度。

根據上述分析，本節設計了種子富集性實驗。實驗首先讀取社交網絡圖G=（V，E），輸入某方法選拔出的k個關鍵節點，針對E中每條邊ei，j∈E作如下判斷：若圖G中的邊ei，j所連接的節點均為關鍵節點，則對該條邊添加標記。最后統計該方法的標記數量。其中，CA-HepTH 網絡添加了預處理過程，刪掉了個體指向自身的12 條回環邊。圖7 是種子富集性的實驗結果。

圖6 種子富集性示例Fig.6 Diagram of seed enrichment degree

根據圖7的實驗結果，整體上SIR評價模型的種子富集性最為稀疏，PSGA 算法其次。LC 算法在有向圖中的富集性程度高，即種子間的連接較為緊密，在無向圖中其富集程度較弱，即種子間的連接較為稀疏，DC、k-shell 和LCIR-AR 算法則與之相反。啟發式算法依靠網絡局部拓撲特性，SIR 和PSGA依靠各自模型傳播機制評價節點的重要性，因此在種子富集性方面具有優勢。

圖7 種子富集性實驗結果Fig.7 Experimental results of seed enrichment degree

5 結語

針對信息的對立傳播情形，本文研究對立信息傳播的影響力最大化問題。研究分析了對立信息的傳播機制，設計了多源熱量傳播模型以及用于處理傳播沖突的隨機處理辦法。實驗結果表明，本文所設計的PSGA 算法能夠有效求解對立影響最大化問題，且在種子富集性的指標上占據優勢。然而，PSGA算法存在時間復雜度較高的問題，未來將針對算法運行效率加以改進，使其合理適用于規模較大的社交網絡數據集。