基于改進標簽傳播算法的輿情社交網絡社區發現

摘 要：通過改進的標簽傳播算法研究了輿情社交網絡中的社交主題發現。針對傳統算法容易陷入局部最優的問題，依據節點間相似度選擇標簽傳播時的鄰居節點；針對傳統算法標簽更新時的隨機性問題，通過結合輿論動力學模型HK的觀點交互過程，依據節點影響力的大小更新標簽。實驗結果表明，該方法在最好情況下（k=0.9）相較于原算法，在穩定性和模塊度指標兩方面分別提高了31%和78%，并且優于其他幾種改進算法。由此可見，該算法相較于原算法及其他改進算法在輿情社交網絡的主題社區發現中表現更好。

關鍵詞：標簽傳播算法；輿情社交網絡；HK模型；主題社區發現

中圖分類號：TP391.1"" 文獻標志碼：A"" 文章編號：1001-3695（2025）01-007-0048-08

doi： 10.19734/j.issn.1001-3695.2024.06.0194

Community discovery of public opinion social network based on improved label propagation algorithm

Abstract： This paper studied the discovery of social topics in social networks using an improved label propagation algorithm. To address the problem of traditional algorithms easily falling into local optima， it selected neighbor nodes during label propagation based on the similarity between nodes. To solve the randomness issue in label updates of traditional algorithms， it used the node influence to update labels by incorporating the opinion interaction process from the HK opinion dynamics model. The experimental results show that the proposed method， in the best case （k=0.9）， improves stability by 31% and modularity by 78% compared to the original algorithm and outperforms several other improved algorithms. It demonstrates that the proposed algorithm performs better in discovering topic communities in social opinion networks compared to the original algorithm and other improved algorithms.

Key words：label propagation algorithm; public opinion social network; HK model; topic community discovery

0 引言

隨著計算機科學和信息科學的不斷發展，互聯網已經全面跨入以用戶生成內容為主要特征的時代。在此趨勢下，各種移動社交應用使得人們所發布的信息以極快的速度傳播到社會各個角落，因此社交網絡輿情的發生已經成為了不可忽視的社會事實。以2023年為例，截至12月21日影響力較高的輿論事件包括體育、民生、消費等社會熱點事件38起、時政熱點事件19起、自然災害或突發事故類事件13起、國際事務11起［1］，這些事件的傳播速度和影響范圍之廣，凸顯了社交媒體在現代社會中的重要作用。為了系統地分析輿情，了解當前輿情的形勢，就需要準確獲悉當前社交網絡輿情中存在哪些主要討論的主題。在突發事件或危機發生時，識別出輿情社交網絡中的主題社區，政府和公共安全機構就可以針對當前社交網絡輿情中大家最為關心的問題，進行疏導和解答，這有助于采取預防措施，制定有效的應對策略，減少不良信息的傳播，維護社會秩序。

1 研究綜述

1.1 社交網絡中的社區發現算法

社區發現是社交網絡的一個重要研究內容。所謂社區，就是指一組在網絡中內部連接緊密、外部連接稀疏的節點，它們往往擁有相同的特性或功能。社區發現的概念最早由Girvan等人［2］提出，并基于邊介數提出了著名的GN算法。在此以后，來自各領域的研究學者提出了許多新的思想與算法，并用于解決各學科領域的具體問題。輿情網絡作為一種社交網絡，其具有社交網絡所具有的普遍屬性——社區結構，網絡輿情中的主題就是社交網絡中的社區，要識別社交網絡輿情中的主題，就需要對輿情社交網絡這樣一個大規模的社交網絡進行社區發現。現有的社交網絡社區發現研究方法主要包括以下三類。

1.1.1 基于相似性聚類的社區發現方法

這種方法基于網絡節點間的相似性對節點執行聚類操作。在計算得到節點間的相似性指標之后，便能利用各類聚類技術（如層次聚類、譜聚類等）根據既定的判斷準則，將節點分配到對應的社區中去。Li等人［3］通過構建節點屬性圖，并在此基礎上進行相似性增強隨機游走，以更好地區分和捕捉節點的群落結構。Agrawal等人［4］基于K-medoids框架，使用協同相似性度量檢測社區，該度量采用平衡屬性相似性和距離函數。Wu等人［5］提出了一種有效的層次聚類方法HCNN，該方法利用數據集最近鄰圖中的兩種結構相似性，將相似數據分組為聚類， 將最大相似性視為兩個聚類之間的傳遞和閉合關系，通過應用高級數據結構，可以更有效地合并聚類。Paul等人［6］提出了局部群體同化（LGA）算法，該算法通過鄰域相似性度量比較兩個相鄰節點，并選取最高值對，然后以這樣一種方式組合在一起，以生成各種大小的初始聚類，最后以迭代方式進一步合并，從而最大化它們之間的簇間邊緣密度。劉井蓮等人［7］采用模糊關系來描述兩個節點之間的相似度，然后通過極大連通子圖算法計算節點所屬的社區。Jiang等人［8］為了應對現有基于相似性的社區劃分算法存在的節點區分度低、社區聚合參數選擇復雜、劃分結果具有隨機性等問題，提出了一種基于公共鄰居聚類熵節點相似性的靜態社區劃分算法。Sahu等人［9］提出了一種基于鄰域相似性的社區檢測算法NBCD ，該算法基于兩種新的相似度量，使用相似性參數 α和一組基本規則，該算法是一個兩步過程，即社區檢測和節點移動。

1.1.2 基于模塊度優化的社區發現方法

模塊度函數的概念最初是由Newman等人［10］提出的， 基于模塊度優化的方法旨在最大化模塊度函數Q，以此來實現更優的社區劃分。模塊度函數Q的得分較高，意味著檢測到的社區結構更加接近于實際情況。Sobolevsky等人［11］針對大多數可用的模塊化優化方法都依賴于特定的離散優化啟發式方法，將其構建為連續二次優化，提出了一種循環圖神經網絡算法，通過模塊化優化進行無監督網絡社區檢測。Gibson等人［12］基于模塊化最大化的目標函數與特定度校正種植分區 SBM 的統計推斷之間存在的等價性，將模塊度優化與可接受模塊化分區凸包 （CHAMP）算法相結合，提出了一種新的社區發現算法。Rustamaji等人［13］基于模塊度優化的思想提出了一種反匯編策略的社區發現算法，該算法首先將每個節點初始化為一個社區，然后在每次迭代中通過開發和探索來增加模塊度。在每次迭代中探索和開發的可能性以百分比表示。Shang等人［14］提出了基于模塊化和改進的遺傳的社區劃分算法（MIGA），該算法采用基于模塊度Q優化的遺傳算法，并針對爬坡算法存在的易陷入局部最優解的缺點，使用模擬退火來幫助尋找更優解，盡量跳出局部最優解的局限。

1.1.3 基于標簽傳播的社區發現方法

標簽傳播算法（LPA）［15］是基于傳播的方法，它首先給每個節點標記唯一的標簽，然后以隨機順序遍歷所有節點。當每個節點與其大多數鄰居具有相同的標簽時，LPA停止傳播。劉鑄等人［16］針對消費者網絡的局部性特點，從節點的相似度判斷和標簽傳播距離兩方面對LPA進行了改進，研究了消費者的類別劃分。付立東等人［17］通過刻畫節點局部相似性指標，并用此度量節點間距離和解決標簽的隨機選擇問題，然后通過引入密度峰值聚類算法由中心向外圍節點傳播標簽，最終得到社區劃分結果。Liu等人［18］針對傳統標簽傳播算法中隨機性導致的社區劃分穩定性差、準確率低的問題，提出一種結合種子節點影響力和鄰域相似性的社區發現算法。Douadi等人［19］定義了一種新的基于中心性和共同鄰居的相似性度量指標并基于標簽傳播算法來提取社區結構。高兵等人［20］結合 node2vec模型對節點進行低維向量表示，構建節點之間的權重值矩陣，根據權重值計算標簽歸屬系數，據此選擇標簽，避免了隨機選擇問題，大幅提高了算法的穩定性。

基于相似性的聚類方法依據節點間相似度將它們歸入不同的社區，忽略了節點本身的屬性及其相互影響，而應該借鑒一些用于計算空間物體相互作用的方法。基于模塊度優化的方法通常受到分辨率限制的影響，這意味著在某些情況下，它們可能無法識別小規模的社區。基于模塊度指標，可以有效地將社區發現問題轉換為最優解問題，但當網絡的社區規模較大時，算法中需計算的解空間也十分巨大。基于標簽傳播的社區發現方法僅是基于網絡的拓撲結構信息進行社區結構的劃分，缺乏對于網絡現實場景的考量，但是該方法更適合模擬輿情交互的動態過程。

2 LPA及其改進策略

標簽傳播算法最初由Zhu等人［21］提出，它的主要思路是使用已標注的實例來預測那些未標注的實例，即利用已經標記的節點標簽信息來推斷那些尚未標記節點的標簽。在2007年，Raghavan等人［15］將此算法首次運用于圖數據的社區檢測領域。該算法速度快、邏輯簡單、時間效率高，可用于分析大規模網絡，目前已經成為社交網絡領域主流的社區發現算法。

2.1 LPA及其不足分析

2.1.1 LPA

標簽傳播算法是一種基于圖的半監督學習方法，算法的核心思想是： 每個節點會根據其鄰接節點標簽出現的頻率來更新自己的標簽，即選擇最常見的標簽作為自己的新標簽。

算法1 傳統標簽傳播算法LPA

輸入：社交網絡G=（V，E）。

輸出：社區發現C。

a）每個節點被賦予一個唯一的標簽（通常是一個數字或顏色），這個標簽代表該節點的初始社區歸屬。

b）在每次迭代中，節點會根據其鄰居節點的標簽更新自己的標簽。具體來說，任取一個節點，該節點選擇鄰居標簽中出現次數最高的標簽作為自己的標簽。若鄰居節點使用的標簽一樣多，采用隨機原則。

c）當所有節點的標簽在數次迭代之后保持不變，則算法停止執行。在這個階段，那些擁有同一個標簽的節點被視作構成一個共同的社區。

2.1.2 LPA算法不足分析

1）標簽傳播的節點選擇方式的不足

學界在對輿情社交網絡關系的構建中，一般采用的是以相互關注、博文轉發或相互@的關系數據構建網絡，并由此分析網絡結構與群體屬性，該方法能夠直接呈現結果。但是基于關注或轉發等構建的網絡更多地反映了社交關系和信息傳播的過程，可能無法充分捕捉到語義內容層面的深層次聯系，并不適用于輿情社交網絡中的主題社區發現研究。而基于語義相似度構建的網絡更加關注內容本身的相似性，而非僅僅依賴社交關系，它可以跨越不同的社交群體，識別出跨群體的共同關注點和觀點，即使這些文本的作者之間沒有直接的社交聯系。基于語義相似度構建的網絡又稱為語義社交網絡［22］。

LPA作為一種啟發式算法，僅是依據網絡的拓撲結構特征進行社區發現，節點標簽的傳播對象為所有的鄰居節點。選擇性接觸理論在社會學實踐中指出，人們通常會傾向于依據自身已有的觀點和興趣來選擇接觸大眾信息，這種有目的性地選擇那些與自己信念相符的信息會導致接收到的信息變得片面化，并進一步強化個人先前的觀點。根據該理論，當人們接觸到能增強其原有觀點的信息時，他們會產生積極的情感，然而盡管個體傾向于與觀點相近的個體交互，但社交平臺的開放性和信息的海量性意味著個體還會不可避免地接觸到很多不同的觀點，這種信息的多樣性可能會對個體原有的觀點產生影響，使得個體的觀點發生改變。LPA的標簽傳播方式忽略了現實社交網絡輿情中個體隨機選擇性接觸的影響，使得算法缺乏探索性和適應性，容易陷入局部最優，因此還需要對LPA標簽傳播的節點選擇方式進行改進。

2）標簽更新隨機性的不足

受身份地位的影響不同，不同的實體或個人的影響力很顯然是不同的，如政府、主流媒體、權威專家和當事人的影響力較高，而一般個人觀點的影響力則較低。LPA在標簽傳播過程中隨機確定節點標簽更新的順序，沒有考慮到輿情社交網絡中不同節點的重要性對標簽更新過程的影響，可能會導致“逆流”現象［23］，即不太重要的節點依次影響到一些重要的節點。另外，在輿情社交網絡中，每個節點都會持有對某輿情事件的一個觀點。在傳統的LPA中，節點在標簽更新階段會傾向于選擇其鄰居節點中出現次數最多的標簽作為其更新后的標簽，如果有多個標簽出現次數相同，則節點會隨機選取一個作為新的標簽，這也被稱為標簽傳播算法的“平局”問題［27］。該問題已被確定為不穩定的來源之一，因為隨機更新會導致每次運行時產生不同的結果，甚至可能還會產生“雪崩效應”，即傳播初期一個小的錯誤被不斷放大，最終影響社區發現的質量。因此，在標簽更新時為每個節點提供一個觀點值，標簽需要依據節點的觀點值進行更新，能最大限度地避免隨機更新帶來的影響。

綜上所述，傳統LPA無復雜的目標函數、具有接近線性的復雜度［15］，但LPA標簽傳播的對象為所有的鄰居節點，而在社交網絡輿情的交互過程中節點更愿意與觀點相近的節點接觸，同時受社交平臺的開放性和信息的海量性影響，又不可避免地接觸其他不同的觀點，只有具有接觸的節點間才可能發生標簽的傳播。此外，算法標簽更新時具有隨機性，但在輿情社交網絡中，每個節點不同的影響力和對輿情事件持有的觀點對于標簽的更新，也是一個重要的影響因素。因此，在進行輿情社交網絡的主題社區發現時還需要結合輿情網絡的現實場景，對LPA標簽傳播的節點選擇方式以及標簽更新時的隨機性進行改進。

2.2 改進LPA

2.2.1 標簽傳播的節點選擇方式改進

1）節點選擇方式改進

doc2vec 是由Le等人［24］提出的一種無監督訓練模型，它能夠將不同長度的文本內容映射到一個固定長度的向量空間中。這種方法能有效地提取文本的語義特征，并簡化文本的內容表示，目前它已經在短文本的向量化表示方面得到了廣泛應用。

基于doc2vec模型對文本進行向量化，采用余弦相似度公式計算兩個文本的內容相似度，如下：

其中：X和Y分別表示節點u和節點v的文本；Suv表示節點u和節點v之間的內容相似度。

根據前述隨機選擇性接觸分析可知，在社交網絡輿情交互過程中，每個節點都會持有對輿情事件的一個觀點傾向，受觀點相似程度的影響，節點更愿意與觀點相近的節點接觸，因此標簽傳播的可能性相應較大，同時又不可避免地接觸其他不同的觀點，只有發生接觸的鄰居節點間才可能發生標簽的傳播。假設節點v按照與鄰居節點u的內容相似度的大小進行標簽傳播，節點v選擇鄰居節點ui作為標簽傳播對象的概率表示如下：

其中：Puiv為節點v選擇與鄰居節點ui進行標簽傳播的概率；N（v）表示節點v的鄰居節點集合；Suiv表示節點v和ui的相似度。

同時，設RN（v）表示選擇作為標簽傳播的鄰居節點集，其定義如下：

RN（v）={ui∈N（v）|random（）∈Jui}（3）

其中：random（）是一個隨機函數，它能夠根據節點v的度值產生k（0lt;k≤1）倍鄰居數的節點，該比例參數k表示選擇接觸的隨機性特點。Jui表示每個鄰居節點ui被選擇的區間，Jui的定義如下：

2）標簽傳播方式對傳統LPA社區模塊度的影響分析

傳統LPA將所有鄰居節點作為標簽傳播的對象，這種標簽傳播方式忽略了隨機選擇性接觸的影響。所提出的方法基于節點的內容相似度構建輿情社交網絡，以鄰居節點間文本的內容相似程度作為標簽傳播的節點選擇依據，不同相似程度的節點具有不同的標簽傳播概率，越相似的節點越有可能被選擇作為標簽傳播的對象，符合個體的同質性和選擇性接觸理論。同時，對于相似度高的節點具有較小的可能性不發生交互，而對于相似度較小的鄰居節點依然具有較小的可能性發生交互，符合實際個體觀點交互過程中多方面采集信息的不確定性。該標簽傳播的節點選擇方式更加真實地模擬了社交網絡輿情中標簽傳播的過程，在選擇性接觸時引入了隨機的因素，這樣可以保證即使不是最優的節點也有一定概率被選中， 這種隨機性在一定程度上增加了搜索空間的多樣性，在一定程度上可以避免算法陷入局部最優解，增強了算法的探索性和適應性。

為驗證標簽傳播時節點選擇方式對傳統LPA的影響，這里以模塊度函數Q作為社區發現質量的評價指標，在輿情社交網絡數據集上對應不同的節點選擇比例k運行一百次取平均值。參數k表示選擇用于進行標簽傳播的鄰居節點的比例，其取值位于0～1。統計分析可知輿情社交網絡的節點平均度值為8，表明網絡平均度較小，由于用于進行標簽傳播的鄰居節點個數以整數計，若參數k取值間隔過小，則用于進行標簽傳播的鄰居節點的數量甚至會相同，導致實驗對比不明顯，若間隔過大則可能會遺漏最佳參數值，所以這里參數k的取值間隔取0.05為宜。關于網絡數據集以及模塊度指標的介紹將分別在4.1節和4.2節中詳細闡述，這里分別統計出了平均模塊度Qavg和標準差Qstd的變化，如圖1所示。

由于k值小于0.3時算法或多數無法收斂，故不再對其進行統計分析。由圖1可知，當k值為0.85和0.9時，模塊度平均值Qavg分別為0.476和0.485，比k值為1（傳統LPA采用的節點選擇方式）時的模塊度平均值0.471要高，這說明適當的k值在滿足現實交互情景的同時，在一定程度上可以避免傳統LPA陷入局部最優解，提高社區的劃分質量。由于在此引入了隨機性，為驗證其所帶來的穩定性問題，對應不同的k值統計了一百次實驗的Qstd，實驗發現不同k值所對應的Qstd相較于k值為1時的Qstd接近，說明節點選擇方式對于傳統算法的穩定性并無明顯的影響。同時發現，不同的k值所對應的Qstd較大，可知這種不穩定性更多來源于LPA標簽更新時的隨機性。

2.2.2 標簽更新的隨機性改進

1）節點標簽更新順序的確定

在輿情社交網絡中，個體并不是一個單純的節點，而是擁有許多屬性，比如粉絲數，發表博文的點贊、轉發、評論數。為避免標簽更新過程中“逆流”現象的影響，首先結合節點的屬性特征，節點粉絲數、博文的點贊數、轉發數、評論數四個指標采用層次分析法計算節點的屬性指標權重，最后結合各指標數據計算節點的屬性值m。

根據數據場理論，網絡可以被視為一個眾多節點相互作用的系統，其中每個節點都會對其一定范圍內（拓撲場）的節點施加拓撲勢，這些節點的拓撲勢會隨著與該節點網絡距離的增加而迅速衰減。節點的拓撲勢可以反映該節點在網絡拓撲結構中受到自身以及附近節點影響的大小，根據拓撲勢值可細分復雜網絡中節點的重要程度。給定一個無向網絡G=（V，E），V表示節點集，E表示邊集，節點v的拓撲勢公式如下：

其中：mu≥0，代表節點v影響范圍內的節點u的質量，在此處表示節點的屬性值；duv表示兩個節點u和v之間的最短路徑長度；σ為影響因子，用于控制節點的影響范圍，可根據節點拓撲勢熵進行優選。

有研究表明，最后更新的節點傳播其標簽的概率較小［25］。根據計算出的節點屬性值結合節點的拓撲勢公式計算出節點影響力ω，最后按照影響力大小降序排列作為節點標簽更新的順序。

2）標簽更新的隨機性改進

為貼合社交網絡輿情的現實場景，在對輿情社交網絡進行社區發現研究時，離不開對于網絡中節點觀點演化的研究，輿情的觀點演化和節點的標簽更新具有密不可分的聯系。目前研究者們提出了許多的輿論動力學模型，這類模型關注的核心是在社會環境普遍無序的背景下，探討信息如何傳播以及觀點如何演化，其目標是理解和預測個體在社交互動中觀點如何隨時間變化并最終形成共識或分歧的過程。HK模型作為一種連續型輿論動力學模型，已被廣泛應用于社交網絡輿情的觀點演化研究中。HK模型的表達式如式（6）所示。

其中：Ou（t）表示鄰居u在時間t的觀點；Nv（t）表示節點v可以與之通信的鄰居集合，Nv（t）={u‖Ov（t）－Ou（t）|≤ε，v≠u}，在這種情況下，節點只會考慮那些意見在它自己信任范圍ε內的鄰居。

由該輿論動力學公式可知，節點通過平均鄰居的觀點來更新它的觀點。同時該輿論動力學模型假設節點在下一時刻的觀點與它當前持有的觀點沒有任何關系，從認知角度來看，代表了場依存的認知方式，在這種情況下，場獨立的認知風格就被忽略了，這是對真實社會現象的過分簡化，不符合真實的社會和生活中觀點的影響過程；另外，該模型在交互過程中認為交互節點的影響力相同，節點的觀點總是更新至其信任閾值內的所有觀點的平均值，沒有考慮鄰居節點之間的差異，實際上節點會考慮觀點提供者的可信度，面對各種海量的網絡信息，信任影響的是節點在觀點交互過程中對于其他節點的真實觀點的接受程度。為獲得節點更加真實的觀點值，根據以上描述對HK模型作出適當的優化，社區標簽在更新時將會參照鄰居節點的觀點進行更新。對HK模型優化后的公式如下：

其中：RN（v）表示節點v用作標簽傳播的鄰居節點集合；Wuv表示節點v對u的影響力；λ∈（0，1）表示場獨立系數且服從標準正態分布。同時，在觀點交互過程中考慮到節點傾向于與同一社區結構內的其他節點交互，而不是與社區結構外的節點交互。因此，節點v對u的信任權重Wuv定義如下：

其中：ωu（t）表示節點的影響力；labelv（t）表示在t時刻節點v的標簽；labelu（t）表示在t時刻節點v的鄰居交互節點u的標簽。

基于以上交互過程在得到節點觀點后，節點v的標簽根據標簽傳播節點u∈RN（v）的觀點進行動態更新。每次選擇標簽傳播節點中與其觀點值平均更接近的標簽作為自己的標簽。節點v的標簽更新如下：

3）標簽更新方式對傳統LPA社區模塊度的影響分析在無向網絡中，網絡的拓撲勢熵為

拓撲勢熵的大小與節點位置差異不確定性的程度有關，能夠反映節點在網絡中的拓撲結構特征，當各節點的拓撲勢值均不相等時，節點位置差異具有最小的不確定性，勢熵達到最小；當各節點的拓撲勢值均相等時，節點位置差異具有最大的不確定性，勢熵也達到最大。

該輿情社交網絡中的拓撲勢熵與影響因子的關系如圖2所示。由圖2可知熵值H先減小后增大，存在一個最優的影響因子σ′為0.858 1，使得勢熵達到最小，此時節點拓撲勢分布最不均勻，同時具有最小的不確定性。在得到最優影響因子σ′后，依據節點的屬性值m結合節點的拓撲勢公式可以計算出網絡中各節點之間的影響力。

為了評估標簽更新方式對傳統LPA的影響，這里同樣將LPA在輿情社交網絡數據集上運行一百次，統計出模塊度平均值Qavg和模塊度標準差Qstd，同時給出了使用改進標簽更新方式的LPA的模塊度Q。

表1顯示，傳統LPA的社區模塊度平均值為0.469，改進標簽更新方式的LPA在輿情主題社區發現時模塊度的模塊度為0.602，模塊度值得到了顯著提高，這是由于：首先，此時的改進算法采用的仍是傳統算法的節點選擇方式（k=1），由圖1可知該節點選擇方式僅稍遜于k值為0.85和0.9的情況；其次，該方法結合了節點本身的外部屬性信息和網絡拓撲結構信息衡量節點的影響力，通過影響力確定節點的標簽更新順序，在標簽更新時按照節點影響力大小的先后順序進行更新；最后，改進的標簽更新方式在節點標簽的更新時考慮了鄰居的觀點，節點每次選擇與其觀點最接近的鄰居標簽作為自己的標簽，可以有效避免標簽更新過程中隨機性帶來的誤差放大的問題，同時節點觀點在更新時也考慮了當前時刻節點標簽的影響，標簽的傳播伴隨著群體觀點的演變，兩者相互影響使得標簽的更新更加具有準確性。同時LPA的Qstd為0.045，這也進一步說明了LPA的不穩定性主要是由于標簽更新的隨機性引起的，使用改進的標簽更新方式可以完全避免標簽更新時隨機性帶來的影響。

3 基于改進LPA的輿情社交網絡社區發現算法

該研究首先使用基于情感詞典的SnowNLP對文本進行情感分析。SnowNLP是一個基于Python寫的工具庫，它將給定文本中的單詞與情感詞典中的單詞配對，并計算它們的情感值，情感值位于0～1，權重越接近1表示情緒是積極的，越接近0表示情緒是消極的。鑒于用戶的情緒可以直觀地反映其對輿論事件的立場［26］，故將這些情緒評分作為用戶對事件觀點的數值指標。

3.1 算法步驟

基于改進LPA的輿情社交網絡社區發現過程如下：

輸入：輿情社交網絡G=（V，E）；節點選擇比例k；觀點差距閾值ε。

輸出：社區發現C。

a）為網絡中每個節點賦予一個唯一的標簽和觀點值。

b）根據2.2.2節1）中提出的方法，依據節點的屬性特征和拓撲勢計算各節點的影響力，按照節點的影響力大小確定標簽的更新順序，并按降序存儲到更新列表中。

c）選取標簽更新列表未處理節點中優先級最高的節點，根據2.2.1節1）中提出的方法，依據節點的度值按照與鄰居節點的相似度大小選擇比例為k的鄰居節點作為標簽傳播的對象。

d）依據選擇出的鄰居節點，根據2.2.2節2）中提出的優化后輿論動力學模型HK的式（7）和（8）更新節點的觀點；根據選擇出的鄰居節點的觀點值依據式（9）選擇出距離其觀點平均最接近的節點標簽作為自身的標簽，并將該節點標記為已處理。

e）重復步驟c）d），直至列表中的節點全部被標記為已處理。

f）當所有節點的觀點演化前后觀點差距都小于某個閾值ε，且所有節點的標簽都不在變化時，迭代結束，否則轉步驟c）。

改進的LPA在社區發現中引入了節點觀點交互機制，更加真實地模擬了社交網絡輿情中的個體交互過程，可以同時揭示輿情社交網絡的最終意見模式和社區結構。其流程如圖3所示。

3.2 算法分析

3.2.1 時間復雜度分析

步驟a）中為每個節點賦予一個觀點值和一個標簽，時間復雜度為O（n）。步驟b）中節點影響力的計算時間復雜度主要取決于拓撲勢的計算，最壞情況為O（n2），根據計算出的節點影響力采用快速排序算法進行降序排序，在平均情況下，快速排序的時間復雜度為O（n·log n）。因此，在初始化階段的時間復雜度為O（n+n2+n·log n），總的時間復雜度為O（n2）。步驟c）～f）中，步驟c）和d）每循環一次，時間復雜度為k·d，k表示交互節點選擇的比例，d表示節點的平均度，迭代結束時間復雜度為Lnkd，其中L表示總的迭代次數。因此，算法總的時間復雜度為O（n2+Lnkd）。

3.2.2 收斂性分析

推理1 設數列滿足遞推公式xn+1=f（xn），若f（x）可微分，且存在常數r∈（0，1）使得|f′（x）|≤r，則數列{xn}收斂。

證明 由于f（x）可微，由拉格朗日中值定理可得|f（xn）－f（a）|=|f′（ξ）|·|xn－a|，由于|f′（x）|≤r，故|f′（ξ）|·|xn－a|≤r|xn－a|，由定理1可知數列{xn}收斂。

收斂性證明：根據改進的輿論動力學公式（7）可將其簡化為如下形式：

Ov（t+1）=λOv（t）+b（12）

f（x）=λx+b（13）

對式（12）兩邊取極限可知，存在常數a=b/（1－λ）使得f（a）=a。同時，顯然式（13）是可微的，且f′（x）=λ，由前可知0lt;λlt;1，由推理1可知節點v的觀點序列O收斂。根據標簽更新式（9）可知，節點的標簽在向著相近觀點的節點標簽變化，當任意節點在觀點更新前后的意見差值小于閾值，并且所有節點的標簽都與距離其觀點值最近的鄰居節點的標簽相同時，迭代結束。此時節點相應的標簽即為節點所屬社區，同一社區的節點將會具有相近的觀點值，通過觀察觀點的分布情況也可自然地揭示出主題社區的分布。

4 實證研究

4.1 數據集

目前在社交網絡輿情領域并沒有權威的公開數據集，因此使用Python爬蟲工具從新浪微博平臺獲取實驗數據，對該研究內容進行驗證。2022年6月10日凌晨，中國河北省唐山市一家燒烤店發生一起暴力毆打他人事件，隨后在微博上引發熱議。針對該起事件搜集了從10日至30日共計78 401條相關微博數據。針對該實驗研究，選取了24日至30日輿情發展后期的文本數據共達4 374條，將熱度較高的博文作為輿情社交網絡社區發現的文本集，選擇標準為文本的點贊轉發以及評論數較高的文本，依據該標準最終選取了1 526條文本。

為了方便構建網絡，對式（1）計算出的結果進行標準化：

其中：du，v為網絡中節點u和節點v的距離，如果du，vgt;1， 則記為無窮大，相當于兩點之間不可達；N為文本集合；n為文本數量。生成的網絡拓撲結構如圖4所示。

4.2 評價指標

1）模塊度函數

模塊度函數是在真實社區結構未知的情況下進行社區質量評價的關鍵指標，因此這里采用模塊度函數 Q作為所提算法社區發現結果的評價指標，Q的取值是［0，1］，其定義公式為

其中：M是網絡中邊的數量；A代表網絡構成的鄰接矩陣，當節點vi和vj間存在連接邊時，Aij的值為1，否則其值為0；deg（vi）和deg（vj）分別為節點vi和節點vj的度數；Li和Lj分別表示節點vi和vj所屬的社區標簽；δ（Li，Lj）為Kronecker函數，當節點vi和節點vj位于同一個社區時，δ（Li，Lj）的值為1，否則為0。

2）標準化互信息（NMI）

標準化互信息是一種相似性度量方法，其源于信息論。這種方法認為如果兩個劃分越相似，則需要越少的附加信息來推斷另一個劃分的分配。它的定義如下：

其中：I（X;Y）表示劃分X和Y之間的互信息；H（X）表示X的熵；NMI的取值是0～1。當預測的社區劃分完全獨立于真實的社區劃分時，NMI=0；相反，當預測的社區與真實社區劃分完全匹配時，NMI=1。

3）ARI指標

ARI指標是兩個聚類之間相似性的另一種衡量標準，定義如下：

其中：RI是兩個劃分之間的相似性度量，它考慮了所有樣本對。通過計算分配給預測的社區劃分和真實的社區劃分的相同和不同樣本對的數量來評價社區發現的質量。具體表現形式如下：

4.3 實驗結果分析

4.3.1 改進LPA社區劃分質量對節點選擇比例k的敏感度分析

為研究節點選擇比例參數k對改進算法的社區模塊度的影響，針對不同參數k實驗一百次統計結果如圖5所示，其中，誤差棒表示標準差，同時由于無法獲悉該輿情社交網絡真實的社區結構，這里NMI和ARI指標均以Louvain算法的劃分結果作為真實的社區標準。

由圖5可知，隨著k的增大，模塊度Q、NMI和ARI指標值不斷提高，當達到臨界值0.7左右時，之后的增長變化較為緩慢。這是因為當k較小時，交互節點的數量是影響社區發現的主要因素，較小的節點選擇比例限制了節點之間的交流，導致觀點交互和標簽傳播只發生在較少的節點之間，社區發現質量并不理想，提高節點的選擇比例可以顯著提高社區發現質量，當k逐漸增加到一個臨界值之后，節點之間達到了充分的交互使得模塊度增長緩慢。同時無論k值為多少，改進算法的各指標值的標準差都很接近，這說明節點選擇的隨機性對算法穩定性的影響有限，而且節點的更新順序和基于輿論動力學模型HK的觀點交互機制能夠很大程度上提高算法的穩定性。當k等于0.85和0.9時社區模塊度Q、NMI和ARI指標均高于其他情況，以模塊度指標為例，當k等于0.85和0.9時，模塊度平均值分別達到0.616和0.629均高于其他情況（k等于1時的模塊度值為0.602），這也進一步驗證了適當的節點選擇比例可以提高社區的發現質量，避免了算法陷入局部最優的情形。

4.3.2 改進LPA的社區劃分質量對比分析

由4.3.1節的實驗分析可知，當k值取0.85或者0.9時，三種評價指標均達到最好的效果，因此這里將參數k等于0.85和0.9時提出的算法與傳統LPA和其他三種改進算法ITSLR［27］、WILPAS［28］、TS［29］進行比較，實驗結果如圖6所示。

從圖6中可知，當k取值0.85和0.9時，所提算法的社區發現質量明顯好于傳統的LPA算法以及ITSLR、WILPAS、TS三種改進算法，穩定性和另外三種改進算法一樣顯著優于傳統的LPA算法。所提算法在穩定性方面的提升主要源于標簽更新時確定的節點更新順序和節點的觀點值；社區發現質量方面的提升主要源于適當的節點選擇方式和標簽更新時結合了觀點交互的機制，而傳統算法和ITSLR、WILPAS、TS三種改進算法僅是依據網絡的拓撲結構特征進行社區發現，缺乏輿情網絡現實場景的考量，因此表現并不理想。其中由于ITSLR算法完全排除了算法隨機性的影響，所以算法的模塊度值、NMI和ARI值均不再變化。所提算法與ITSLR算法最主要的區別就在于所提算法在標簽傳播時引入了隨機性，因此算法并不穩定，但是相較于傳統算法標簽傳播方式（k＝1）在社區發現質量上有所提升，避免了算法陷入局部最優，這里從圖5也可以看出。此外，k等于0.9時的社區發現質量要稍好于k等于0.85時的社區發現質量，但穩定性方面要稍遜色于后者。

4.4 社區發現與觀點分布情況分析

為研究改進算法迭代結束時，輿情社交網絡中社區發現結果與節點觀點真實分布情關系，針對每組參數k在相同條件下實驗一百次，統計出實驗結果最頻繁獲得的數據，如圖7所示，其中φ表示社區發現的數量，δ表示觀點一致的社區數量，這里假設若兩個節點之間的觀點值不超過0.01，則認為它們屬于同一社區，誤差棒表示社區數量的標準差。圖7顯示，隨著k的增加，社區在達到穩定狀態后，社區數量呈減少趨勢。當k達到臨界值時，社區數量保持一致。此外，實驗結果還顯示，k值在達到0.8以后社區數量保持一致且不再變化，這表明在社區演化達到穩定后，屬于同一社區的節點持有近乎相同的觀點。

這里選取了k值為0.85和0.9的社區發現結果如圖8（a）和（b）所示。其社區發現個數均為四個，其中，紫色、黃色、藍色、綠色社區（見電子版）分別表示主題①、②、③、④，具體來說：①指責此次暴力打人事件，要求嚴懲；②對警方通報中的受害者“輕傷”認定表示質疑；③黑惡勢力活動頻繁，批評地方“保護傘”的存在；④女性安全成為焦點，討論女性如何能有效地自我保護。以圖8（b）為例，主題①約占網絡規模的29%，其社區觀點值穩定在0.17附近；主題②約占網絡規模的24%，其社區觀點值穩定在0.32附近；主題③約占網絡規模的26%，其社區觀點值穩定在0.21附近；主題④約占網絡規模的21%，其社區觀點值穩定在0.43附近。分析來看，網民主題比較尖銳且觀點呈現消極情緒，急需相關部門下場維護社會和網絡生態環境穩定。針對本算法的實驗分析，進一步給出如下建議：

a）識別關鍵主題，把握輿情發展態勢。圖5實驗分析表明，綜合了適當的節點選擇比例和觀點交互機制的LPA算法相較于傳統算法可以顯著地提高主題社區發現的質量，這有助于準確了解公眾關注的核心問題和觀點。政府和相關機構應密切關注這些關鍵主題，并針對性地制定引導策略。對于積極正面的主題社區，可以通過增加相關信息的傳播力度來強化其影響力，鼓勵公眾參與討論，形成正面的社會氛圍。對于負面情緒較多的主題社區，如指責暴力事件或批評現象，需要通過有效的溝通和引導，將公眾情緒轉換為建設性的意見，促進社會問題的解決。

b）減少信息不對稱，促進形成和諧的社會共識。輿情事件發生后，網民受非理性因素的影響，網絡空間中最初往往充斥著各種言論，通過對不同參數k的觀點分布情況的實驗分析可知，充分的交互是輿論達成共識的關鍵，要控制輿情朝向有利的方向發展就需要在尊重民意和信息自由的基礎上，確保信息的真實性和公正性，避免以訛傳訛。因此，應建立官方核實渠道，通過權威機構對輿論焦點或熱點問題進行及時、準確的信息發布與澄清，減少信息不對稱。例如，針對網民提到的如對警方通報的質疑等負面情緒，相關部門應及時作出回應，提供準確信息，減少誤解和猜疑，維護社會穩定。

5 結束語

通過以上實驗分析可知，本算法能對輿情社交網絡中的主題社區進行有效發現并能夠反映出節點間的觀點分布情況，對于社交網絡輿情的治理能夠提供有力的參考，但還存在以下問題：a）算法無法識別出具有重疊的節點，即對于多個主題均具有討論的節點；b）在解決原算法容易陷入局部最優問題的過程中，為了增強算法的探索性，引入了一定的隨機因素，導致本文算法的不穩定性無法完全避免，但相較于原算法，本文算法的穩定性依然得到了較大的提升，這里從圖6中也可以明顯看到。

參考文獻：

［1］祝華新， 潘宇峰， 廖燦亮. 2023年中國互聯網輿情分析報告 ［M］// 李培林， 陳光金， 王春光， 等. 2024年中國社會形勢分析與預測. 北京： 社會科學文獻出版社， 2023： 262-277. （Zhu Huaxin， Pan Yufeng， Liao Canliang. China Internet public opinion analysis report 2023 ［M］// Li Peilin， Chen Guangjin， Wang Chunguang， et al. Analysis and Forecast of China’s Social Situation in 2024. Beijing： Social Sciences Academic Press， 2023： 262-277.）

［2］Girvan M， Newman M E J. Community structure in social and biological networks ［J］. Proceedings of the National Academy of Sciences， 2002， 99（12）： 7821-7826.

［3］Li Qingqing， Ma Huifang， Li Ju， et al. Attributed multi-query community search via random walk similarity ［J］. Information Sciences， 2023， 631： 91-107.

［4］Agrawal S， Patel A. SAG cluster： an unsupervised graph clustering based on collaborative similarity for community detection in complex networks ［J］. Physica A： Statistical Mechanics and its Applications， 2021， 563： 125459.

［5］Wu Chunrong， Peng Qinglan， Lee Jia， et al. Effective hierarchical clustering based on structural similarities in nearest neighbor graphs ［J］. Knowledge-Based Systems， 2021， 228： 107295.

［6］Paul A， Dutta A. Community detection using local group assimilation ［J］. Expert Systems with Applications， 2022， 206： 117794.

［7］劉井蓮， 王大玲， 馮時， 等. 一種基于模糊相似關系的局部社區發現方法 ［J］. 軟件學報， 2020， 31（11）： 3481-3491. （Liu Jinglian， Wang Daling， Feng Shi， et al. Local community discovery approach based on fuzzy similarity relation ［J］. Journal of Software， 2020， 31（11）： 3481-3491.）

［8］Jiang Wanchang， Zhang Xiaoxi， Zhu Weihua. Community detection using closeness similarity based on common neighbor node clustering entropy ［J］. KSII Trans on Internet amp; Information Systems， 2022， 16（8）：2587-2605.

［9］Sahu S， Rani T S. A neighbour-similarity based community discovery algorithm ［J］. Expert Systems with Applications， 2022， 206： 117822.

［10］Newman M E J， Girvan M. Finding and evaluating community structure in networks ［J］. Physical Review E， 2004， 69（2）： 026113.

［11］Sobolevsky S， Belyi A. Graph neural network inspired algorithm for unsupervised network community detection ［J］. Applied Network Science， 2022， 7（1）：00500.

［12］Gibson R A， Mucha P J. Finite-state parameter space maps for pru-ning partitions in modularity-based community detection ［J］. Scien-tific Reports， 2022， 12（1）： 15928.

［13］Rustamaji H C， Kusuma W A， Nurdiati S， et al. Community detection with greedy modularity disassembly strategy ［J］. Scientific Reports， 2024， 14（1）： 4694.

［14］Shang Ronghua， Bai Jing， Jiao Lichen， et al. Community detection based on modularity and an improved genetic algorithm ［J］. Physica A： Statistical Mechanics and its Applications， 2013， 392（5）： 1215-1231.

［15］Raghavan U N， Albert R， Kumara S. Near linear time algorithm to detect community structures in large-scale networks ［J］. Physical Review E， 2007， 76（3）： 036106.

［16］劉鑄， 錢曉東. 基于改進LPA算法的去中心化電子商務網絡消費者類別劃分算法 ［J］. 數據分析與知識發現， 2023， 7（10）： 25-36. （Liu Zhu， Qian Xiaodong. A decentralized classification algorithm for online consumers based on improved LPA ［J］. Data Analysis and Knowledge Discovery， 2023， 7（10）： 25-36.）

［17］付立東， 劉佳會， 王秋紅. 基于密度峰值的標簽傳播社區發現算法 ［J］. 計算機應用研究， 2023， 40（8）： 2323-2328. （Fu Lidong， Liu Jiahui， Wang Qiuhong. Label propagation community discovery algorithm based on density peak ［J］. Application Research of Computers， 2023， 40（8）： 2323-2328.）

［18］Liu Miaomiao， Yang Jinyun， Guo Jingfeng， et al. A label propagation community discovery algorithm combining seed node influence and neighborhood similarity ［J］. Knowledge and Information Systems， 2024， 66（4）： 2625-2649.

［19］Douadi A， Kamel N， Sais L. Label propagation algorithm for community discovery based on centrality and common neighbours ［J］. The Journal of Supercomputing， 2024，80（8）：11816-11842.

［20］高兵， 宋敏， 鄒啟杰， 等. 基于圖嵌入和多標簽傳播的重疊社區檢測算法 ［J］. 計算機應用研究， 2024， 41（5）： 1428-1433. （Gao Bing， Song Min， Zou Qijie， et al. Overlapping community detection based on graph embedding and multi-label propagation algorithm ［J］. Application Research of Computers， 2024， 41（5）： 1428-1433.）

［21］Zhu Xiaojin， Ghahramani Z. Learning from labeled and unlabeled data with label propagation ［EB/OL］. （2002）. https：//www.semanticscholar.org/paper/Learning-from-labeled-and-unlabeled-data-with-label-Zhu-Ghahramani/2a4ca461fa847e8433bab67e7bfe4620371c1-f77？p2df.

［22］辛宇， 謝志強， 楊靜. 基于話題概率模型的語義社區發現方法研究 ［J］. 自動化學報， 2015， 41（10）： 1693-1710. （Xin Yu， Xie Zhiqiang， Yang Jing. Semantic community detection research based on topic probability models ［J］. Acta Automatica Sinica， 2015， 41（10）： 1693-1710.）

［23］Yan Rong， Yuan Wei， Su Xiangdong， et al. FLPA： a fast label propagation algorithm for detecting overlapping community structure ［J］. Expert Systems with Applications， 2023， 234： 120971.

［24］Le Q， Mikolov T. Distributed representations of sentences and documents ［C］// Proc of International Conference on Machine Learning. 2014： 1188-1196.

［25］ubelj L， Bajec M. Robust network community detection using ba-lanced propagation ［J］. The European Physical Journal B， 2011， 81： 353-362.

［26］蘇辀恒， 張敏， 王錦. 圖書情報領域情感研究現狀述評 ［J］. 圖書情報工作， 2022， 66（6）： 137-147. （Su Zhouheng， Zhang Min， Wang Jin. Review on the current status of emotion research in the field of library and information science ［J］. Library and Information Service， 2022， 66（6）： 137-147.）

［27］Liu Miaomiao， Yang Jinyun， Guo Jingfeng， et al. An improved two-stage label propagation algorithm based on LeaderRank ［J］. PeerJ Computer Science， 2022， 8： 981.

［28］Arab M， Hasheminezhad M. Efficient community detection algorithm with label propagation using node importance and link weight ［J］. International Journal of Advanced Computer Science and Applications， 2018， 9（5）： 090566.

［29］You Xuemei， Ma Yinghong， Liu Zhiyuan. A three-stage algorithm on community detection in social networks ［J］. Knowledge-Based Systems， 2020， 187： 104822.