[發明專利]一種提升社交網絡層次化社區檢測劃分效果的方法

在審

• 申請號: 202111387697.9
• 申請日: 2021-11-22
• 公開（公告）號: CN114090903A
• 公開（公告）日: 2022-02-25
• 發明（設計）人: 楊珉;張謐;丁岱宗
• 申請（專利權）人: 復旦大學
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06N3/08;G06Q50/00
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;陸尤

本發明公開了一種提升社交網絡層次化社區檢測劃分效果的方法。本發明將社區檢測分為兩步完成：首先根據現有社區拓撲結構，給定節點與社區的特征向量，預測社交網絡圖中每個節點的社區從屬關系，并利用社交網絡圖中節點之間的連接關系優化現有的特征向量；而后利用深度學習中的強化學習技術，給定當前社區拓撲結構和社交網絡圖，預測調整現有社區的拓撲結構；重復上述兩步驟直至收斂；給定一張社交網絡圖，能夠預測其節點的社區劃分情況。針對社交網絡中出現的新增節點，繼續重復上述步驟即可將新節點也納入社區劃分中。本發明方法在社區檢測的模塊度和歸一化互信息上都遠高于現有的GEMSEC算法、HCDE算法和ComE算法。

技術領域

本發明屬于人工智能推薦技術領域，具體涉及一種提升社交網絡層次化社區檢測劃分效果的方法。

背景技術

隨著互聯網技術的發展，社區信息在各種互聯網服務中得到了廣泛的應用。如何高效地劃分檢測平臺中的用戶社區逐漸成為了工業界研究中的重點。針對這個問題，大量社區檢測劃分算法被提出。然而，現有技術主要通過啟發式方法實現社區檢測，無法對大型社區結構信息進行準確地建模，從而在社區檢測任務上表現不佳。這一現象的主要原因是傳統層次化社區檢測方法的目標在于將社區中的每個節點劃分到對應社區中，這一步驟具有很高的時間復雜度，使得傳統方法無法很好地應用于大型社交網絡社區劃分問題，且無法自適應地劃分網絡新增節點。另一方面，盡管基于圖的深度學習模型能夠很好地建模具有復雜拓撲結構的圖，但由于深度學習技術通常需要能夠確切表達的輸出結果形式，致使輸出結果為一種拓撲結構的層次化社區檢測任務上很少應用這類技術。

發明內容

本發明針對人工智能技術中的社交網絡層次化社區檢測系統，提出一種提升系統社區檢測劃分效果的方法。

本發明中，社交網絡由一張圖表示，圖中的節點和邊分別代表網絡中的用戶與用戶之間的相互關聯性。在劃分檢測社區的過程中，系統需要根據用戶節點在圖上的邊信息，將用戶劃分到對應的社區中，即給定一個用戶和所有社區的特征，預測該用戶屬于某個社區的概率，從而完成社區檢測。

本發明提出的提升社交網絡層次化社區檢測劃分效果的方法，其中，社交網絡表示為一張圖，圖中的節點和邊分別代表網絡中的用戶與用戶之間的相互關聯性；社交網絡圖劃分一棵合適的社區樹，并將社交網絡中的每個用戶對應劃分至合適的社區中，每個社區和每個用戶的特征由一個特征向量表示；在劃分檢測社區過程中，系統需要向一棵只有根節點的社區樹不斷添加新社區，同時更新用戶和社區特征向量，并以此為依據將用戶劃分至對應社區中，直至得到合適的劃分；即給定一個社交網絡圖，將圖中的用戶劃分至一棵社區樹的每個社區節點中；

與此相對應，系統包括一個用于社區檢測的社區檢測模塊，此外，還部署一特征評估模塊；對于每一位用戶，該特征評估模塊根據用戶節點在社交網絡圖上的連接信息，訓練得到用戶的特征向量，并同時更新社區特征向量；根據用戶和當前社區之間特征向量的相似度將用戶劃分到當前存在的各個社區中；將包含連接邊信息的社交網絡圖和用戶社區劃分情況傳入社區檢測模塊；社區檢測模塊將根據傳入信息計算狀態矩陣，用以表示當前社區劃分效果，即社區劃分是否與社交網絡圖中的連通情況相對匹配；在此狀態矩陣的基礎上，社區檢測模塊還包含一個神經網絡，用以預測用戶節點屬于某個社區的概率；在模型訓練過程中，系統將根據社區劃分的結果和實際社交網絡圖上的用戶連通性評估當前社區劃分的損失和激勵，利用強化學習技術訓練該神經網絡，從而提升系統社區劃分的效果。

本發明提出的提升社交網絡層次化社區檢測劃分效果的方法，首先，根據當前社交網絡中用戶和社區的特征向量計算相似度，將得到的相似度用于預測用戶屬于當前存在的每個社區的概率，以此為依據將用戶劃分至預測所屬的社區中；然后，根據當前社區劃分情況和實際社交網絡圖中的連接信息，計算當前劃分的狀態矩陣；接著，將該狀態矩陣輸入一個神經網絡，就可以預測新社區應當插入在當前社區樹的位置；最后，當該神經網絡的訓練收斂時，系統就得到了穩定的社區拓撲結構，并能將用戶依據特征向量正確地劃分到各個社區中。具體步驟如下：

步驟一、初始化：在系統訓練開始前，初始化系統所需的變量：