[發明專利]一種基于多標簽傳播的社交網絡重疊社區發現方法及裝置

有效

• 申請號: 202011350850.6
• 申請日: 2020-11-26
• 公開（公告）號: CN112464107B
• 公開（公告）日: 2023-03-31
• 發明（設計）人: 范時平;薛思豪
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 重慶輝騰律師事務所 50215
• 代理人: 王海軍

本發明屬于社交網絡技術領域，涉及一種基于多標簽傳播的社交網絡重疊社區發現方法及裝置；所述方法包括將社交用戶節點的相似度映射到邊的權重，并計算出各個節點的相似度，構建出加權網絡；遍歷加權網絡中的每個節點的標簽，如果目標節點具有與源節點相同的標簽，那么該標簽的權重采用第一更新公式更新，否則采用第二更新公式更新；去除傳播更新后標簽權重小于預設閾值的標簽，取每個節點的前k個標簽作為該節點的新標簽；對每個標簽的節點數進行計數，選擇節點數最多的k個標簽所對應的用戶分別作為最終的重疊社區；本發明把節點的相似性映射到邊的權值，進行多標簽傳播，從而解決了隨機性的問題，有效地提高了社區的識別和劃分的質量。

技術領域

本發明屬于社交網絡技術領域，特別涉及一種基于多標簽傳播的社交網絡重疊社區發現方法及裝置。

背景技術

現實世界中的很多系統都可以抽象為復雜網絡，如社交網絡、技術網絡、生物網絡，這些網絡都具有一種普遍的特性——社區結構。在不同類型的網絡中，社區有著不同的含義，但是所有社區內部節點間的聯系總是比不同社區節點間的聯系密切，準確地發現社區結構是在中觀層面上理解網絡結構進而研究復雜系統的有效途徑。

社區發現的研究歷史可以追溯到1927年，Rice等人基于投票模式的相似性發現小的政治團體中的社區，早期的研究工作大部分都圍繞非重疊社區發現展開，此類算法將復雜網絡劃分成若干個互不相連的社區結構且一個節點只能隸屬于一個社區，然而，現實中網絡社區之間往往是相互重疊的，硬劃分的社區發現算法無法滿足需求。

近年來，學者們相繼提出了大量能夠識別重疊社區的算法。Palla等提出了一種基于最大團的派系過濾算法CPM來分析重疊的社區結構，并以此算法為原理開發了應用軟件CFinder，該算法易受k值影響，且以最大團為種子計算復雜度較高。COPRA算法對基于標簽傳播的非重疊社區發現算法進行改進，在標簽后面附上節點對該標簽的歸屬系數，以便衡量該節點包含多個社區的信息比重，在迭代更新節點標簽的過程中允許一個節點同時擁有多個標簽，以發現網絡中的重疊社區，該算法每次迭代的時間復雜度接近線性但穩定度較差。

中國專利CN103729475A提出了一種社交網絡中多標簽傳播重疊社區發現方法，將社區劃分過程劃分為初步社區發現、節點層級標記以及重疊社區細化三個階段，通過引入節點層級的思想及不同層級節點間的標簽傳播增益來規范標簽在節點間的強度，使得在社區發現過程中，減小高層級的節點收影響的程度，同時低層級節點通常處于多個社區的交叉區域，能夠根據自身的鄰居節點的社區歸屬及層級信息選擇合理的標簽集合。該方法無需社區數目的先驗知識，并對網絡結構自適應，可有效的挖掘社交網絡中的重疊社區結構；但是該方法缺少對標簽權重的更新，導致劃分出的社交網絡重疊區域存在不穩定性和隨機性較強等問題。

發明內容

針對現有技術中社交網絡劃分算法存在劃分結果不穩定，隨機性強，導致算法的準確性低的問題，本發明提出了一種基于多標簽傳播的社交網絡重疊社區發現方法及裝置，用于檢測社交網絡中的重疊社區。本發明首先計算節點之間的相似度，然后根據網絡結構和節點的相似度傳播多個標簽，此外本發明使用修剪策略將每個節點的標簽數保持在適當的范圍內，能夠有效提升本發明的發現效率。

本發明提供以下技術方案以解決上述技術問題：

在本發明的第一方面，本發明提供了一種基于多標簽傳播的社交網絡重疊社區發現方法，所述方法包括以下步驟：

采集社交網絡數據，構造出以社交網絡用戶為節點，用戶關系為邊的社交網絡圖；

將用戶節點的相似度映射到邊的權重，并計算出各個節點的相似度；

基于各個節點的相似度，構建出所述社交網絡圖所對應的加權網絡；

遍歷加權網絡中的每個節點的標簽，當源節點傳播到目標節點時，如果目標節點具有與源節點相同的標簽，那么該標簽的權重采用第一更新公式更新，否則采用第二更新公式更新；