[發明專利]一種社區發現方法、裝置、存儲介質及終端設備

有效

• 申請號: 201910049502.6
• 申請日: 2019-01-18
• 公開（公告）號: CN109859063B
• 公開（公告）日: 2023-05-05
• 發明（設計）人: 顧軍華;武君艷;許馨勻;謝志堅;陳博;佘士耀;張亞娟;張素琪
• 申請（專利權）人: 河北工業大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 孟金喆

1.一種社區發現方法，其特征在于，包括：

基于預設規則確定待分析網絡中預設數量的目標網絡節點，并基于所述目標網絡節點構建約束點集合；

根據所述約束點集合構建約束矩陣；

根據所述約束矩陣對所述待分析網絡進行社區結構劃分；

其中，基于預設規則確定待分析網絡中預設數量的目標網絡節點，包括：

獲取待分析網絡對應的網絡鄰接矩陣；其中，所述網絡鄰接矩陣表示所述待分析網絡的網絡拓撲結構；

根據網絡鄰接矩陣及預先獲取的隨機初始化矩陣構建第一目標函數；

通過最小化所述第一目標函數生成所述隨機初始化矩陣的第一更新規則，并根據所述第一更新規則對所述隨機初始化矩陣進行更新直至所述隨機初始化矩陣收斂；

根據收斂后的隨機初始化矩陣確定所述待分析網絡中預設數量的目標網絡節點。

2.根據權利要求1所述的方法，其特征在于，根據收斂后的隨機初始化矩陣確定所述待分析網絡中預設數量的目標網絡節點，包括：

計算收斂后的隨機初始化矩陣中每行元素之和，并對每行元素之和按照遞減的順序排序；

將各個元素之和中預設數量的最大的元素之和對應的隨機初始化矩陣中的網絡節點，確定為所述待分析網絡中的目標網絡節點。

3.根據權利要求1所述的方法，其特征在于，根據網絡鄰接矩陣及預先獲取的隨機初始化矩陣構建第一目標函數，包括：

根據如下公式構建第一目標函數：

其中，L(B)表示第一目標函數，A表示網絡鄰接矩陣，B表示隨機初始化矩陣，β表示預先設定的正則化系數，||A-AB||_F表示對矩陣A-AB求F范數。

4.根據權利要求3所述的方法，其特征在于，所述第一更新規則如下：

其中，D為對角矩陣，

5.根據權利要求1所述的方法，其特征在于，獲取待分析網絡對應的網絡鄰接矩陣，包括：

讀取待分析網絡對應的數據集文件；

根據所述數據集文件構建所述待分析網絡對應的網絡鄰接矩陣。

6.根據權利要求1所述的方法，其特征在于，根據所述約束點集合構建約束矩陣，包括：

對所述約束點集合中的目標網絡節點進行must-link約束對約束，將所述約束點集合劃分為至少兩個約束點子集合；其中，所述約束點子集合中包括至少兩個約束到相同社區的目標網絡節點；

根據所述約束點子集合及所述待分析網絡中的非約束節點構建目標約束點集合；其中，所述非約束節點包括所述待分析網絡中除所述目標網絡節點外的網絡節點；

根據所述目標約束點集合構建約束矩陣。

7.根據權利要求6所述的方法，其特征在于，根據所述約束點子集合及所述待分析網絡中的非約束節點構建目標約束點集合，包括：

根據如下公式構建目標約束點集合：

相應的，所述約束矩陣如下：

C＝(C_ij)∈R^(q+n-p)*n；

其中，M_i表示第i個目標約束點集合，P_i表示第i個約束點子集合，C表示約束矩陣，C_ij表示約束矩陣C中第i行第j列的元素，q表示約束點子集合的個數，n表示所述待分析網絡中網絡節點的個數，p表示所述約束點集合中包含的目標網絡節點的個數；當待分析網絡中網絡節點j屬于所述第i個目標約束點集合時，C_ij＝1，否則，C_ij＝0。

8.根據權利要求1所述的方法，其特征在于，根據所述約束矩陣對所述待分析網絡進行社區結構劃分，包括：

根據所述約束矩陣及預先設定的輔助矩陣構建第二目標函數；

通過最小化所述第二目標函數生成所述輔助矩陣的第二更新規則，并根據所述第二更新規則對所述輔助矩陣進行更新直至所述輔助矩陣收斂；

計算收斂后的輔助矩陣與所述約束矩陣的乘積，得到所述待分析網絡中社區結構的劃分結果。