用戶互動表示下的影響力最大化算法

張 萌，李維華

（云南大學信息學院，昆明 650504）

0 引言

隨著網絡技術的不斷發展，越來越多的人們在獲得即時信息的同時也因互聯網成為了信息傳播的主體，一些學者利用Instagram、微博、Facebook 和Twitter等社交平臺用戶間信息擴散的優勢，挖掘社交網絡用戶潛在的商業價值。影響力最大化問題作為數據分析下的新興領域，利用“口碑效應”在病毒營銷、廣告發布和政府監管等方面有著良好的應用前景。例如，品牌方有一批新產品待推廣，他們首先要在社交網絡中選擇最佳的用戶群體進行產品投放，通過這些種子用戶的宣傳，讓盡可能多的人們購買和使用該產品，這就是影響力最大化在商業推廣中的巧妙應用。研究影響力最大化對人們了解真實的網絡信息具有非常重要的意義。

影響力最大化問題最早由Domingos等［1］定義為在網絡中尋找t個節點，這些節點利用自身影響力使得信息最終的傳播范圍最廣。隨后，Kempe 等［2］證明了影響力最大化問題是一個NP 難（Non-deterministic Polynomial hard）問題，并提出了兩種經典的擴散模型——線性閾值（Linear Threshold，LT）模型和獨立級聯（Independent Cascade，IC）模型，并在此基礎上結合蒙特卡洛模擬提出了貪婪算法求解影響力最大化問題。后來的研究者們運用不同的方法對影響力最大化算法進行了改進，也得到了不錯的研究結果；但這些方法在計算節點間影響概率時都是依賴于人工處理好的簡化網絡和理想狀態下的公式計算，沒能真正地通過節點間的互動得出影響概率。

近年來，網絡表示學習（Network Representation Learning，NRL）作為學術熱點在社交網絡用戶行為研究中得到了廣泛的運用。其思想是利用一種映射函數將社交網絡中的每個用戶表示為低維向量，這些向量在一個向量空間中具有表示和推理的功能。Preozzi等［3］在2014年提出了基于網絡的表示學習模型DeepWalk，該模型是受到Mikolov 等［4］在2013 年提出的用于自然語言處理的經典模型Word2vec 的啟發，將網絡中的節點看作單詞，將利用隨機游走生成的節點序列看作一個句子，通過SkipGram 模型的學習得到節點的向量表示。在社交網絡中利用這些向量表示可以進行商品個性化推薦、節點分類、節點間鏈路預測和興趣社區發現等。之后，一些學者在DeepWalk 的基礎上提出了Node2vec［5］、LINE［6］和Struc2vec［7］等網絡表示學習模型。圖1 展示了網絡表示學習模型的流程，可以看出網絡表示學習為后續的社交網絡研究開辟了新方向。

圖1 網絡表示學習流程Fig.1 Flowchart of network representation learning

現階段影響力最大化問題的研究面臨著兩個主要的挑戰：1）如何跳出理想狀態下的公式計算，獲得更真實的節點間影響概率；2）現有的大部分工作集中于在簡化網絡中考慮最大化的影響擴散，能否脫離固定的傳播模型，考慮節點間的交互，從交互聯系的角度來進行影響評估。針對上述問題，本文提出一種用戶互動表示下的影響力最大化（Influence Maximization based on User Interactive Representation，IMUIR）算法，主要工作包括：

1）根據社交網絡中用戶的互動痕跡來構造用戶上下文對；

2）利用SkipGram 模型學習用戶表示，得到能表示用戶的特征向量，根據用戶活躍度和交互聯系度，利用貪心策略選擇最佳種子集；

3）在兩個真實的社交網絡上與4 個算法進行對比實驗，驗證了IMUIR算法的有效性。

1 相關研究

國內外的研究學者利用不同類型的方法對影響力最大化問題進行了研究。Chen 等［8］基于IC 模型和節點度的中心性提出了DegreeDiscount 算法；李敏佳等［9］綜合考慮了核心節點和結構洞節點的傳播優勢，提出了基于結構洞和度折扣的最大化算法；Aldawish 等［10］通過對鄰居節點的約束提出一種新的改進的度折扣啟發式方法MDD（Modified Degree-Discount）；Kim 等［11］提出了一種隨機游動排序和秩合并修剪的算法，通過修剪無影響節點來避免無用的影響擴散；張憲立等［12］基于度和PageRank 的思想提出了一種混合啟發式算法來解決大型網絡上的影響力最大化問題；吳安彪等［13］在時序圖上對影響力最大化問題進行了研究，提出了用來計算節點影響力的AIMT（Advanced method for IMTG）和IMIT（Improved method for IMTG）。

此外，一些群集智能算法也被運用到了影響力最大化的研究中。Jiang 等［14］提出一種評估預期影響的函數EDV（Expect Diffusion Value），結合模擬退火算法求解影響力最大化問題，該算法比利用函數子模性改進的貪心算法CELF（Cost-Effective Lazy Forward）快了近3個數量級；Cui等［15］基于一種降階搜索策略，融合遺傳算法提出度數遞減搜索（Degree-Descending Search Evolution，DDSE）；Gong 等［16］利用離散離子群算法與評估節點二階區域內的預期影響函數相結合提出了DPSO（Discrete Paticle Swarm Optimization）算法，能夠較為準確地找出種子節點；Sankar 等［17］受到蜂群擺舞行為的啟發，提出了蜂群算法，在具有主題標簽的Twitter重推網絡中驗證了該算法的有效性；Tang 等［18］提出了離散混合蛙跳算法，該算法基于一種新的編碼機制和離散進化規則尋找種子節點。

盡管上述算法均取得了不錯的效果，也在一定程度上取得了突破，但存在兩個明顯的弊端：一方面是基于理想狀態來計算的節點間影響傳播概率；另一方面是通過擴散模型來計算受一組種子用戶影響的節點數量，而現有的擴散模型依賴于假設會導致結果不可靠，使得影響力最大化的求解面臨著可擴展性［19］。

由于復雜網絡包含數十億的用戶和連接關系，想要從中獲取用戶信息會非常棘手，而網絡表示學習能夠將影響力最大化問題在大規模網絡中進行擴展。Wang 等［20］通過學習低維向量來計算影響概率，并利用啟發式算法DiffusionDiscount來尋找種子集；王正海［21］將社交網絡的節點引入到向量空間后先用K-Means聚類算法找到候選種子集，再利用KD 樹確定最終的種子集。上述算法雖然利用網絡表示學習對節點進行了表示，但僅利用網絡結構來進行研究，沒有考慮用戶間的互動。Feng 等［22］從用戶日志級聯中提取用戶上下文對，通過構建傳播網絡，利用低維表示來描述用戶的社會影響嵌入，由于信息傳播的有向性，每個用戶有兩種嵌入表示——源嵌入和目標嵌入，源嵌入表示對其他用戶的影響，目標嵌入表示受其他用戶的影響。該方法脫離了簡單網絡結構，從用戶級聯中確定影響擴散。Panagopoulos 等［23］利用多任務神經網絡預測種子節點的預期影響和級聯大小，利用預測的級聯大小和CELF 算法的思想來選取種子集。該方法提出利用測試級聯評估種子集的影響范圍，更貼合真實的信息傳播，但在采樣和尋找種子集時沒有考慮到用戶行為特征。由上述研究可知，目前利用網絡表示學習解決影響力最大化問題的研究還較少，且還有許多問題有待研究。

受Feng 等［22］研究的啟發和針對Panagopoulos 研究中的不足，本文利用社交網絡中用戶自身的行為特性和用戶間的互動，提出IMUIR算法。

2 用戶互動表示下的影響力最大化算法

2.1 問題定義

Panagopoulos 等［23］在其研究中提出了利用用戶產生的測試級聯來評估種子集的影響范圍，這樣更貼近真實社交網絡的規律。因此在本文中，給定一個社交網絡圖G=(V，E，Q)，V表示社交網絡中的用戶，E表示用戶關系，Q表示G中用戶在一個時間段T內產生的同類型社交事件，事件的類型包括但不限于發博、評論、點贊和投票等用戶交互行為。按照時間順序將時間T中的事件劃分為訓練級聯Qtrain和測試級聯Qtest，影響力最大化問題就是從G中找到一組大小為K(K≤|V|)的用戶集合U，使得U在Qtest中的影響范圍σ(U)最大，形式化定義如下：

其中U*為最佳用戶集合。

2.2 構建用戶上下文對

利用網絡結構求解影響力最大化問題時存在一個弊端，大多數固定的社交網絡結構均來自用戶的關注列表和粉絲列表，但在社交網絡中通常都會存在“僵尸用戶”，這些“僵尸用戶”的存在對用戶影響力的評估是沒有意義的，甚至會導致評估產生偏差。而事件記錄了一個用戶在過去一段時間T內與網絡中其他用戶的互動行為，利用這些互動行為能較好地捕捉到用戶之間的影響傳播。Panagopoulos 等［23］在其研究中證實了那些在社交網絡中具有較大影響力的用戶多數都是在事件中發起互動的用戶，也就是一個互動級聯的產生者，而不是參與者。同時，根據影響力的傳播動力學研究顯示，由于影響衰減，最近鄰域范圍內的影響評估往往是最可靠的［24］。因此本文在構建用戶上下文對時僅考慮用戶的直接互動，通過事件中的用戶互動級聯進行采樣，并且僅對產生互動級聯的用戶進行采樣，利用該方法相當于對網絡中的用戶進行了初步篩選。

給定一個社交事件Qtrain，Xi為事件Qtrain中的一個用戶互動級聯，在Xi中ui(ui∈V) 為該互動的發起 者，vi={vi1，vi2，…，vik}(vi?V)表示在該級聯下與ui進行互動的k個用戶集合。以ui為源用戶，從集合vi中隨機選取目標用戶構建ui的用戶上下文對context(ui)={(ui，vi1)，(ui，vi2)，…，(ui，vik)}，由于只考慮直接互動，因此事件中的級聯是一對多的關系，一個用戶上下文對中只有兩位用戶，分別是源用戶和目標用戶。根據圖2 的事件描述可給出具體例子，X2是事件Qtrain中的一個用戶互動級聯，在X2中，u2是發布微博的源用戶，v2={v21，v22，v23}是轉發了該條微博的目標用戶，假設從v2中隨機選取兩個用戶v21和v22，那么可構建u2的用戶上下文對context(u2)={(u2，v21)，(u2，v22)}，該集合表示u2直接影響了v21和v22。利用同樣的方法可構建任意一個ui的用戶上下文對。

圖2 事件描述Fig.2 Event description

2.3 SkipGram模型

SkipGram 本質上是一個神經語言模型，在自然語言處理中被廣泛使用，可根據單詞向量表示利用當前的單詞Wi預測其上下文Wi-2，Wi-1，Wi+1，Wi+2出現的概率，它規定了固定長度的“詞窗口”，Wi的上下文僅由“詞窗口”內的單詞組成而非整個句子。將該思想運用到網絡表示學習中就是預測一個當前用戶的上下文概率假設出現在用戶ui上下文中的各個用戶間相互獨立，那么用戶ui上下文的概率如下所示：

SkipGram 模型的目標是最大化用戶上下文的聯合概率，并以此來更新用戶的向量表示，因此目標函數的定義如式（3）所示：

其 中：w∈context(ui) 表示用戶ui的上下文用戶w；(ui，context(ui)) ∈Xi表示ui的上下文對均來自Xi。

要計算目標函數的值ψ，首先需要計算用戶上下文對中ui對w的概率p(|w ui)，這個概率的計算需要通過表示用戶間關系的特征向量來完成；θ為模型訓練過程中需要更新的參數，也就是用戶的特征向量矩陣，d為特征向量的維度，該矩陣可表示為

在本文方法中，將ui這類產生影響的用戶稱作源特征，表示為；將w這些受別人影響的用戶稱作目標特征，表示為Tw；b表示ui的影響偏置；ui對w的影響概率p(|w ui)可以利用學習到的特征向量經softmax函數得出，定義為

2.4 尋找種子集

由于媒體時代信息的快速更新使得用戶信息產生了存活時長，而用戶活躍度和用戶間交互聯系度在一定程度上決定了信息存活時長。在日常的社交網絡平臺的使用中，如果一個源用戶在平臺上的活躍度越高，源用戶和目標用戶間的交互聯系就越頻繁，這樣可以增加源用戶的信息存活時長，那么源用戶的影響力也會越大。本文中的用戶活躍度a是指源用戶在一個事件中產生級聯的次數，產生級聯的次數越多，用戶的活躍度也越高。

交互聯系度f是源用戶ui與網絡中其余用戶的互動聯系的多少。首先利用特征向量根據式（5）計算ui對網絡中其余用戶的影響概率，選出網絡中受ui影響最大的前α個目標用戶（α為用戶在Qtrain中產生的平均級聯長度），因此，ui的交互聯系度就是ui對網絡中其余用戶影響概率降序排列后前α個目標用戶的影響概率總和：

本文根據用戶活躍度和交互聯系度利用貪心策略尋找最佳種子集，具體思想是：1）根據源用戶在Qtrain中出現的次數計算源用戶的活躍度a，選取部分活躍度高的用戶作為候選種子集；2）根據式（6）計算候選種子集中每個源用戶對網絡中其余用戶的影響概率，利用貪心策略選出當前f(ui)最大的源用戶ui加入最佳種子集中，之后將選出的ui和受其影響最大的α個用戶從網絡中刪除；3）重復過程2）直到迭代完成。具體算法描述如下所示：

輸入 種子集大小K，事件Qtrain，源特征，目標特征Tw；

輸出 最佳種子集U*。

2.5 時間復雜度分析

根據用戶采樣、訓練模型和尋找種子集對IMUIR 算法進行時間復雜度分析。設采樣數為I，特征向量的維數為m，Qtrain中的影響傳播用戶數為n，負采樣數為M，種子集大小為K，候選種子集大小為|C|，訓練過程中的收斂次數為D，則IMUIR的時間復雜度為：

3 實驗結果與分析

3.1 實驗數據與對比算法

本文使用Digg和Weibo兩個真實的社交網絡數據進行實驗，數據集除了有真實網絡，還包括用戶的日常互動級聯，根據時間將前80%的級聯作為訓練集，將剩余級聯作為測試集，詳細信息如表1所示。

表1 實驗數據集Tab.1 Datasets used in experiments

經實驗測試，本文提出的IMUIR的參數設置為：采樣率為400%，學習率為0.02，向量維度的設置參考了部分表示學習對于節點向量的人為設定，設定為50。同時為了驗證所提算法IMUIR 的性能，選取下述4 個具有代表性的算法進行對比實驗。

1）Random：該算法從網絡中隨機選擇K個用戶作為種子節點。

2）Average Cascade（AC）：該算法的思想是利用用戶產生的平均級聯大小來決定種子集中的節點，產生的平均級聯越長，就越有可能被選為種子節點。

3）Kcore：根據網絡中用戶的核數來決定種子節點。

4）Imfector：利用多任務神經網絡學習得到用戶的向量表示和用戶可能產生的級聯大小，利用特征向量計算用戶的期望影響用戶的比例Λ，根據Λ與影響擴散概率選取種子節點。在對比時，該算法的向量維度為50，采樣率為120%，學習率為0.1，與其論文中的設置一致［23］。

本文所有算法均使用Python3 編寫，在Windows 10 系統的PC端上運行，硬件配置為2.3 GHz Intel i5-6300HQ處理器，8 GB內存。

3.2 結果分析

評價影響力最大化算法通常使用影響擴散范圍和運行時間這兩個指標。本文的影響擴散范圍是指在測試級聯Qtest中與種子用戶互動的用戶數量，數量越多，種子集影響力越大［23］。運行時間是指算法找到最佳種子集所需要的時間，IMUIR 和Imfector 的時間包含采樣、訓練和尋找種子集三部分。

3.2.1 種子集質量評估

在利用算法找到最佳種子集后，首先需要找到種子用戶出現在測試集中的數量，這主要是根據種子用戶能否在未來的一段時間內產生影響來評估選出的用戶集合的質量。在Digg和Weibo數據集中找到的種子用戶數如表2、3所示，在指定的種子大小下基于用戶級聯的表示學習方法找到的種子用戶比基于網絡結構的方法多，而在表示學習的方法中，IMUIR能找到的種子集數量比Imfector 多。這說明利用表示學習尋找到種子集的方法是可行的，并且IMUIR 能找到的有效節點更多，種子集質量優于其他方法。

表2 Digg中找到的種子用戶數量Tab.2 Number of seed users found in Digg

3.2.2 影響范圍對比

在影響范圍圖中，X軸表示不同大小的種子集，Y軸對應不同種子集下影響的用戶數量。

圖3 展示了5 個算法在兩個數據集和不同種子集大小下的實驗結果，從Digg 數據集可以發現，IMUIR 算法表現最好，當種子集大小為200 時，其影響范圍比Random、AC、Kcore 和Imfector 分別高了13.59%、39.47%、16.10%和5.90%，產生的影響范圍最廣，Imfector其次，而AC表現最差。值得注意的是，結合表2 和圖3（a）可以看到，當種子集大小為80 時，IMUIR 找到的56 個高質量用戶產生的影響范圍是31 144，而Imfector 找到的50 個高質量用戶產生的影響范圍是33 417，Imfector 在高質量種子比IMUIR 少了6 個的情況下影響范圍比IMUIR高了7.29%，產生的原因可能有兩個：一方面是因為IMUIR 找到的這56 個種子在影響傳播時產生了富集性，通常來說就是有一部分用戶可能受到多個種子用戶的影響，出現在了多個種子用戶產生的級聯下，由此產生了影響重疊；另一方面是種子用戶在未來的這段時間內自身產生的影響范圍較小。此外，當種子集大小為200 時，Kcore 與Random 相比影響范圍低了2.2%也是上述原因之一導致的。當種子集大小為20 時，在IMUIR 和Imfector 中均找到15 個能夠產生影響的種子用戶，但IMUIR的影響范圍比Imfector高了4.4%。

圖3 影響范圍對比Fig.3 Comparison of influence scope

在Weibo 數據集中，從整體來看，基于表示學習的IMUIR和Imfector的表現遠優于其余三個算法，但IMUIR依舊表現最好，而Random 表現最差。當種子集大小為2 000時，IMUIR 的影響范圍比Random、AC、Kcore 和Imfector 分別高304.19%、16.53%、18.48%和0.58%。同樣結合表3 和圖3（b）可以看到，AC 與Random、AC 與Kcore 也出現了上述在Digg 數據集中討論過的現象，當種子集大小為200和400時，Random 中能產生影響的種子數量比AC 多，但在傳播范圍上AC 比Random多了174.82%和217.34%。當種子集大小為2 000 時，Kcore中能產生影響的種子數比AC 多了129 個，但影響范圍比AC低了1.64%。

表3 Weibo中找到的種子用戶數量Tab.3 Number of seed users found in Weibo

此外，為了進一步證明IMUIR 的有效性，將Qtest中產生的級聯大小排在前K的源用戶所組成的種子集產生的影響范圍C(k)（k為種子集大小）作為參考基線，并將5個算法與C(k)進行影響范圍對比，獲得在以C(k)為基線的參考下，5個算法影響范圍降低或提高的百分比，如表4 和表5 所示，其中：“+”表示算法的影響范圍與C(k)相比提高的百分比，“-”則表示降低的百分比。

表4 各算法在Digg上與C(k)影響范圍的對比 單位：%Tab.4 Comparison of influence scope of different algorithms on Digg with C(k unit：%

在Digg 數據集中可以看到，當種子集大小為200 時，IMUIR 的影響范圍只比C(200)小22.43%，Imfector次之，相差26.76%，而AC 與之相差44.38%，差距最大。在表5 顯示的Weibo 數據集中，在不同種子集大小下，IMUIR 的影響范圍均超過了C(k)產生的影響范圍，可能的原因是C(k)產生影響時有較多的影響重疊，局限了傳播范圍，而IMUIR尋找到的種子集產生的影響重疊不多，影響范圍更廣，說明利用IMUIR尋找到的種子集質量更高。

表5 各算法在Weibo上與C(k)影響范圍的對比 單位：%Tab.5 Comparison of influence scope of different algorithms on Weibo with C(k unit：%

上述實驗結果表明，本文提出的IMUIR 在兩個數據集上表現都較好也較為穩定，IMUIR 和Imfector之間的比較也說明了在尋找最佳種子時考慮用戶的活躍度和交互聯系度是必要的，而像AC這樣根據平均級聯來選擇種子集的算法對用戶級聯很挑剔，Kcore表現也較為穩定，但總體效果不佳。

3.2.3 運行時間對比

圖4 顯示了Kcore、AC、Imfector、IMUIR 這四個算法在兩個不同數據集上的運行時間對比，這里需要說明的是由于Random 算法的運行時間極短，在Digg 和Weibo 這兩個數據集上的運行時間分別為0.81 s 和1.97 s，因此沒有在圖上進行顯示。雖然Random 運行時間最短，但其算法性能不穩定，效果也不佳。從圖中可以發現，表示學習算法由于要進行采樣和學習，因此運行時間均比其他幾個算法多。Kcore也只需要125.847 7 s 就能從Digg 數據集中找出最佳種子集，但找到的種子集質量不高，傳播的影響范圍也不夠大；AC 相比起Random 和Kcore用時多一些，但算法性能也不穩定，對數據結構很挑剔；IMUIR 在兩個數據集上的用時比Imfector分別多了14.28%和6.53%，但IMUIR 在影響范圍上的優勢可以彌補效率上的不足，說明IMUIR 也是能夠解決影響力最大化問題的一種方法。

圖4 不同數據集上各算法的運行時間對比Fig.4 Running time comparison of different algotirhms on different datasets

4 結語

本文基于用戶互動表示提出IMUIR 算法，主要利用用戶自身活躍度和特征向量捕捉的交互聯系度尋找最優種子集，并驗證了算法的有效性。但利用表示學習求解影響力最大化問題還有充足的改進空間：一方面針對上述算法可以尋求更便捷的方法以縮短時間，在兼顧效果的同時提高效率；另一方面，用戶間不僅僅有行為上的交互，還會涉及情感交互，在有合適數據集的情況下可以將情感交互融合到這種類型的影響力最大化問題的求解中，以探索更真實可靠的用戶影響力。