基于圖表示學習的社交網絡群體競爭影響力識別

劉鑫哲 方勇 賈鵬 寇蔣恒 范希明 周小涵 潘睿 朱旭

摘 要： 群體競爭影響力識別是社交網絡分析領域的一個必要研究，其任務是識別社交網絡中任意兩群體節點在相互競爭條件下的影響力，在輿情分析等實際場景中具有重要意義. 在過去的幾年里，許多研究集中在沒有競爭對手的群體影響力識別. 然而，競爭普遍存在于真實的社交網絡中，因此研究群體競爭影響力識別任務十分必要. 與非競爭場景下的群體影響力識別相比，群體競爭影響力識別存在競爭數據集的構建和群體對嵌入聚合等挑戰. 圖表示學習（GRL）在社交網絡分析領域取得了巨大的成功，可以將圖結構表示成具有結構信息的低維嵌入，能夠更好的反應節點之間的相互作用，提供比傳統方法更豐富的信息. 本文開創性的使用GRL 來解決競爭場景下的群體影響力識別問題，并提出了一個基于GRL 的框架. 為了解決競爭數據集的構建問題，本文提出了一種基于影響力多樣性的群體對構建方法. 為了解決競爭群體對嵌入聚合問題，本文提出了一種基于求和相減的方法來聚合競爭群體對中節點的嵌入. 本文在7 個真實的社交網絡上進行了大量實驗來分析所提框架的有效性. 實驗結果表明所提框架優于基線方法.

關鍵詞： 群體競爭影響力識別； 社交網絡分析； 深度學習； 圖神經網絡

中圖分類號： TP391. 1 文獻標志碼： A DOI： 10. 19907/j. 0490-6756. 2024. 033006

1 引言

社交網絡通常可以表示為G = （V， E ），其中V 表示社交網絡中的節點，E 表示節點之間的邊.競爭是社交網絡的普遍特征，準確識別社交網絡內群體的影響力意義重大，而這需要同時考慮群體本身及其競爭對手的特征. 假設S 和C 是兩組相互競爭的節點，（S， C ） 稱為群體對，其中S ∈ V，C ∈ V，S ∩ C = ?. 群體競爭影響力識別任務的目標就是識別社交網絡中群體S 在存在競爭群體C時的影響力，這在分析企業傳播策略的有效性、預測投票趨勢和抑制輿論傳播等領域具有實際應用價值. 現有的群體影響力研究主要集中在無競爭場景，主要的方法有3 類：基于路徑分析的方法、基于貪心算法的方法和基于中心性的方法.

基于路徑分析的方法通過分析節點組與其他節點之間的路徑信息計算影響力. 然而，這些方法只能分析一些特定的路徑，無法分析所有節點之間的所有路徑，導致結果精確度不高. 基于貪心算法的方法需要大量的蒙特卡羅模擬，計算成本高昂，所以無法擴展到大型網絡［1］. 基于中心性的方法比基于路徑分析和基于貪心算法的方法更高效. 然而，現有方法通常只考慮一個或幾個特定的結構［2，3］，或者從幾個單獨節點的結構信息分析節點組的影響力，沒有考慮多個節點之間的相互作用，例如影響的重疊，導致結果并不準確.

此外，這些方法都沒有考慮到社交網絡中普遍存在的競爭因素. 因此，在競爭場景下直接使用這些方法來識別群體影響力會產生較大誤差. 如何在考慮競爭因素的情況下準確評估群體的影響力是社交網絡分析領域的挑戰之一.

圖表示（Graph Representation Learning，GRL）是一種針對圖數據的處理方法［4］，可以將節點、邊、子圖或整個圖處理為低維向量表示，以供下游具體任務使用. GRL 在自然語言處理［5］、社交網絡分析［6］、物理建模［7］和藥物設計［8］等許多研究領域有著廣泛應用并取得了巨大成功. 群體的整體分布特征是處理群體級任務的重要信息，但現有的GRL 模型并不能很好的獲取此類信息，所以不能直接用于群體競爭影響力識別任務.

在本文中，我們提出了一個基于GRL 的框架來解決群體競爭影響力識別問題. 我們工作的主要貢獻如下：（1） 我們將群體競爭影響力識別視為群體層面的回歸任務，并提出了一個基于GRL 的框架來解決這一問題. 據我們所知，這是第一個從這樣的角度來處理群體競爭影響力識別任務的工作.（2） 我們提出了一個基于求和-相減的群體對嵌入聚合方法，該方法可以有效捕捉群體之間的競爭關系和同群體內的合作關系，解決群體對嵌入表示的問題. 該方法還通過計算群體內節點的鄰居重疊度來削減重疊影響問題.（3） 針對社交網絡數據分布不平衡問題，我們提出了一個基于影響力多樣性的群體對構建方法.（4） 本文在7 個真實社交網絡數據集上進行了一系列實驗，證明所提框架的性能優勢和所提方法的有效性.

2 相關工作

目前尚無關于社交網絡群體競爭影響力識別的研究，因此我們希望從社交網絡群體影響力識別的現有研究中獲得經驗. 研究人員已經提出了許多方法來評估社交網絡中群體的影響力，這些方法通常可以分為3 類：基于貪心算法的方法、基于路徑分析的方法和基于中心性的方法. 此外，圖表示學習（GRL）作為近期的研究熱點，被越來越多的研究者研究并應用. 因此，本文參考了大量基于貪心算法、基于路徑分析、基于中心性的群體影響力識別方法和GRL 相關文獻.

2. 1 基于貪心算法的方法

該方法主要使用蒙特卡洛模擬來估計群體影響力，并通過構建貪心算法來優化模擬過程. 其中，Leskovec 等人［9］提出了CELF 算法，通過利用影響估計優先級隊列和懶惰轉發策略來提高簡單貪心算法的效率. Goyal 等人［10］基于CELF 提出了CELF++算法，其核心是將貪心算法的兩個連續迭代的影響擴散同時計算. 另外，Zhou 等人［11］提出了UBLF 算法，該算法限制了每個節點的模擬上限，從而減少了第一輪節點選擇的模擬次數.Cheng 等人［12］提出了一種靜態貪心算法，該算法嚴格保證影響力擴散的亞模態性，從而提高組影響力模擬的速度. 而Ohsaka 等人［13］則引入了PrunedBFS 來加速蒙特卡洛模擬的過程. 然而，由于以上基于貪心算法的方法需要大量的蒙特卡洛模擬來估計節點影響力，因此效率較低且難以擴展到大規模社交網絡. 因此，不建議使用這類方法來識別群體競爭影響力.

2. 2 基于路徑分析的方法

該方法通過分析節點之間的路徑結構信息來評估群體影響力. 其中，Chen 等人［14］提出了最大影響路徑（Maximum Influence Path，MIP）的概念，用于表示從一個節點到另一個節點的影響力，并通過合并多個節點的影響路徑來估計群體影響力. Gong 等人［1］提出了一種局部影響估計方法來近似群體影響力. Lu 等人［15］則通過計算節點之間的可達概率，利用遞歸方式估計群體影響力，并提出了3 種策略來提高計算效率. 然而，由于節點之間路徑的復雜性，以上基于路徑分析的方法通常無法考慮完整的路徑信息，導致結果不準確. 考慮到本文要研究的群體競爭影響力識別問題會分析大量節點，且包含大量路徑信息，為了確保結果的準確性，不建議使用以上基于路徑分析的方法.

2. 3 基于中心性的方法

基于中心性的方法根據各種中心性計算節點的重要性，進而識別群體影響力. Kundu 等人［16］將社區結構與中心性結合，通過計算每個節點所屬社區的總體中心性來近似節點的影響力，進而計算群體影響力. Jia 等人［3］在度中心性的基礎上將節點的度重新定義為出度和入度，并提出了一個可調整的參數α 來調整出度與入度之間的相對權重，以適應不同場景的群體影響力識別. Ullah 等人［17］提出了一種局部全局中心性方法，該方法綜合考慮了局部信息和全局信息來評估節點的影響力，從而識別群體影響力. 不同的中心性可以從不同的角度反應節點的影響力，以上基于中心性的方法多從單一中心性角度分析節點影響力后擴展到群體影響力，對節點分析不全面，且沒有考慮影響力重疊問題，所以此類方法也不適用于本文所研究的群體競爭影響力問題.

2. 4 基于圖表示學習的方法

圖嵌入技術可以將高維圖數據如節點、邊、圖等映射為低維向量，為后續的節點級、邊級和圖級任務提供豐富的信息. 社交網絡是一種天然的圖數據，近年來，越來越多的研究人員使用圖嵌入技術進行社交網絡分析. 例如，Zhao 等人［18］提出了InfGCN 模型，該模型結合了節點特征和網絡結構信息來識別社交網絡中有影響力的節點. Huang等人［19］提出的SDGNN 模型則考慮了平衡理論和地位理論，并重新設計了聚合方法和損失函數，能更好地學習符號有向圖的嵌入表示. Cao 等人［20］提出的MuGNN 模型用于實體對齊任務，該模型通過多個通道學習兩個知識圖譜的嵌入，解決了不同網絡結構的異質性問題. Chen 等人［21］提出了一個新的多級圖卷積網絡框架（MGCN），用于社交網絡鏈路預測任務. 該框架同時考慮局部和超圖級的卷積信息來學習網絡嵌入，能捕捉更豐富的網絡信息. Jia 等人［22］提出了SRFA-GRL 框架，通過子圖重建來捕捉群體的分布，并提出了一種新的特征聚合方法來聚合群體特征. Kou 等人［23］引入了一種包含鄰域特征的多頭注意力回歸模型，以提高節點影響識別的準確性。

這些研究都表明，使用GRL 可以有效地解決社交網絡中的具體問題，并且優于傳統方法. 這啟發我們使用GRL 來解決組競爭影響力評估問題.

3 本文方法

3. 1 概述

在本節中，我們提出了一個基于GRL 的框架，用于識別社交網絡中群體的競爭影響力. 所提框架的總體結構如圖1 所示，它包含以下幾個部分.

（1） 準備工作.（a）IC 仿真［25］：我們計算社交網絡中每個節點的IC 值以獲取節點的傳播能力特征；（b）特征提取：我們提取了社交網絡中每個節點的多種特征，詳見4. 2. 1 節.