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

在審

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

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

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

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

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

(1.1)初始化僅包含根節點的初始社區樹

(1.2)初始化狀態矩陣s₁＝[0]、距離矩陣Λ₁＝[0]；

步驟二、對于當前社區樹，使用當前社區插入策略π(a_t|s_t)向社區樹中的社區位置a_t下插入新社區c，得到新社區樹

(2.1)將給定的狀態矩陣s_t傳入神經網絡中，計算得到隱藏層h_c，即：

其中，w_h,b_h分別為神經網絡隱藏層的參數矩陣與偏置項；

(2.2)將隱藏層h繼續變換得到預測插入新社區位置的概率分布o_t：

其中，w_o,b_o分別為神經網絡輸出層的參數矩陣與偏置項；

(2.3)從神經網絡輸出的概率分布o_t中采樣得到插入新社區的位置a_t；t＝1,…,T，T針對不同應用場景選為某個特定值；

步驟三、給定社區樹計算距離矩陣Λ_t+1：

(3.1)對兩社區c_i,c_j，在當前社區樹中尋得其最小公共父節點c_k，于是：

Λ(c_i,c_j)＝dist(c_i,c_k)+dist(c_j,c_k)； (3)

其中，dist(·,·)定義為樹中兩節點之間的最短路徑距離；

步驟四、根據社交網絡圖中的連接信息Υ、距離矩陣Λ_t+1，訓練得到用戶、社區的特征向量，并對每個用戶i輸出其屬于每個社區c的概率分布

(4.1)對于每個用戶i和當前社區樹中的每個社區c，根據它們的用戶特征向量e_i和社區特征向量e_c計算其相似度

(4.2)根據用戶與社區之間的相似度，得到用戶i屬于社區c的多項式分布概率ρ_ic：

(4.3)對于每個用戶對(i,j)，根據用戶i,j所屬社區c_i,c_j的概率組合，結合其所屬社區之間的距離Λ(c_i,c_j)，計算得到兩個用戶節點之間的距離d_ij：

其中，ρ_i,ρ_j∈R^t分別是用戶i,j屬于某個社區c的概率ρ_ic的向量化表示，R^t表示大小為t的實數向量；

(4.4)對于節點v_i，根據連接信息Υ中所有與其有連接的節點v_j、沒有連接的節點v_k，統計排序損失l(φ)，并以最小化該損失為優化目標，優化用戶和社區特征向量：

其中，β0是一個常數，φ＝{e_i,e_c}表示用戶特征向量和社區特征向量參數集合；

(4.5)為簡化優化方法，將用戶和社區特征向量重新參數化：

其中，η_i∈R是一個為實數的縮放參數，是維度為R^D的向量，ω(·)是用來獲得非負值的ReLU函數；

(4.6)在訓練收斂后，得到當前最優特征向量，并重新計算ρ_ic；

本發明中，用戶和社區特征向量的維度優選為50；

步驟五、根據社交網絡圖中的連接信息Υ、距離矩陣Λ_t+1、用戶i屬于社區c的概率分布計算當前社區樹的激勵r_t：

其中，y_ij＝1表示用戶i和用戶j之間存在連接關系，y_ik＝0表示用戶i和用戶k之間不存在連接關系；

步驟六、根據社交網絡圖中的連接信息Υ、距離矩陣Λ_t+1、用戶i屬于社區c的概率分布計算當前社區樹的狀態矩陣s_t+1：

(6.1)初始化s_t+1∈R^t×t為零矩陣，R^t×t表示t×t實數矩陣；

(6.2)對社交網絡圖中的每一個用戶節點代表圖中的所有用戶節點集合；初始化其所屬的社區c_i為用戶屬于社區的多項式分布概率ρ_i中最高的社區c：

c_i＝argmax_cρ_ic； (10)

(6.3)對連接信息Υ中的每一條連接y_ij∈Υ，計算對應用戶所屬社區c_i,c_j之間的狀態值s_t+1(c_i,c_j)：

(6.3.1)首先計算中間變量

(6.3.2)若c_i＝c_j，則

(6.3.3)否則，

步驟七、當社區樹收斂后，根據生成樹過程中的狀態變量利用PPO算法更新神經網絡的參數Θ＝{w_h,w_o,w_v,b_h,b_o,b_v}(其中·_h,·_o為神經網絡中的參數，·_v為激勵函數中的參數，具體如下：

(7.1)目標函數為

其中，γ是一個超參數，也被稱為折扣系數；

(7.2)PPO算法用于優化以下損失函數：

其中，ζ₁,ζ₂是正則化系數；是衡量a_t上多項式分布的熵，另有：

其中，是基于s_t估計當前激勵的函數，w_v∈R^t,b_v∈R是該函數的參數向量和偏置項；π_old是最后一輪構建社區樹時所用的策略；使用Adam優化方法對參數Θ進行求解；

步驟八、重復步驟一至步驟七，直至PPO算法收斂，即求得穩定的社區劃分。