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

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

關(guān)鍵詞： 群體競(jìng)爭(zhēng)影響力識(shí)別； 社交網(wǎng)絡(luò)分析； 深度學(xué)習(xí)； 圖神經(jīng)網(wǎng)絡(luò)

中圖分類號(hào)： TP391. 1 文獻(xiàn)標(biāo)志碼： A DOI： 10. 19907/j. 0490-6756. 2024. 033006

1 引言

社交網(wǎng)絡(luò)通?？梢员硎緸镚 = （V， E ），其中V 表示社交網(wǎng)絡(luò)中的節(jié)點(diǎn)，E 表示節(jié)點(diǎn)之間的邊.競(jìng)爭(zhēng)是社交網(wǎng)絡(luò)的普遍特征，準(zhǔn)確識(shí)別社交網(wǎng)絡(luò)內(nèi)群體的影響力意義重大，而這需要同時(shí)考慮群體本身及其競(jìng)爭(zhēng)對(duì)手的特征. 假設(shè)S 和C 是兩組相互競(jìng)爭(zhēng)的節(jié)點(diǎn)，（S， C ） 稱為群體對(duì)，其中S ∈ V，C ∈ V，S ∩ C = ?. 群體競(jìng)爭(zhēng)影響力識(shí)別任務(wù)的目標(biāo)就是識(shí)別社交網(wǎng)絡(luò)中群體S 在存在競(jìng)爭(zhēng)群體C時(shí)的影響力，這在分析企業(yè)傳播策略的有效性、預(yù)測(cè)投票趨勢(shì)和抑制輿論傳播等領(lǐng)域具有實(shí)際應(yīng)用價(jià)值. 現(xiàn)有的群體影響力研究主要集中在無競(jìng)爭(zhēng)場(chǎng)景，主要的方法有3 類：基于路徑分析的方法、基于貪心算法的方法和基于中心性的方法.

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

此外，這些方法都沒有考慮到社交網(wǎng)絡(luò)中普遍存在的競(jìng)爭(zhēng)因素. 因此，在競(jìng)爭(zhēng)場(chǎng)景下直接使用這些方法來識(shí)別群體影響力會(huì)產(chǎn)生較大誤差. 如何在考慮競(jìng)爭(zhēng)因素的情況下準(zhǔn)確評(píng)估群體的影響力是社交網(wǎng)絡(luò)分析領(lǐng)域的挑戰(zhàn)之一.

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

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

2 相關(guān)工作

目前尚無關(guān)于社交網(wǎng)絡(luò)群體競(jìng)爭(zhēng)影響力識(shí)別的研究，因此我們希望從社交網(wǎng)絡(luò)群體影響力識(shí)別的現(xiàn)有研究中獲得經(jīng)驗(yàn). 研究人員已經(jīng)提出了許多方法來評(píng)估社交網(wǎng)絡(luò)中群體的影響力，這些方法通?？梢苑譃? 類：基于貪心算法的方法、基于路徑分析的方法和基于中心性的方法. 此外，圖表示學(xué)習(xí)（GRL）作為近期的研究熱點(diǎn)，被越來越多的研究者研究并應(yīng)用. 因此，本文參考了大量基于貪心算法、基于路徑分析、基于中心性的群體影響力識(shí)別方法和GRL 相關(guān)文獻(xiàn).

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

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

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

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

2. 3 基于中心性的方法

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

2. 4 基于圖表示學(xué)習(xí)的方法

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

這些研究都表明，使用GRL 可以有效地解決社交網(wǎng)絡(luò)中的具體問題，并且優(yōu)于傳統(tǒng)方法. 這啟發(fā)我們使用GRL 來解決組競(jìng)爭(zhēng)影響力評(píng)估問題.

3 本文方法

3. 1 概述

在本節(jié)中，我們提出了一個(gè)基于GRL 的框架，用于識(shí)別社交網(wǎng)絡(luò)中群體的競(jìng)爭(zhēng)影響力. 所提框架的總體結(jié)構(gòu)如圖1 所示，它包含以下幾個(gè)部分.

（1） 準(zhǔn)備工作.（a）IC 仿真［25］：我們計(jì)算社交網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的IC 值以獲取節(jié)點(diǎn)的傳播能力特征；（b）特征提?。何覀兲崛×松缃痪W(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的多種特征，詳見4. 2. 1 節(jié).