[發明專利]一種基于多標簽傳播的半監督重疊社區發現算法

在審

• 申請號: 202110079776.7
• 申請日: 2021-01-21
• 公開（公告）號: CN112417316A
• 公開（公告）日: 2021-02-26
• 發明（設計）人: 楊艾森;史曉春;陳文;鄧三鴻;劉留;李祥睿
• 申請（專利權）人: 南京數聯銘品科技有限公司
• 主分類號: G06F16/9536
• 分類號: G06F16/9536;G06Q50/00
• 代理公司: 武漢聚信匯智知識產權代理有限公司 42258
• 代理人: 馬尚偉

1.一種基于多標簽傳播的半監督重疊社區發現算法，其特征在于，包括以下步驟：

S100，輸入復雜網絡圖：將需要進行社區發現復雜網絡輸入重疊社區發現算法之中；

S200，使用Bron-Kerbosch算法進行初始化：使用Bron-Kerbosch算法對數據進行處理，得到極大團并融合重疊部分的團，為極大團中的節點賦予一致標簽，完成對標簽傳播的初始化，即賦予節點初始標簽；

S300，計算每個節點的PageRank值：根據節點與邊的權重計算每個節點的PageRank值，即值，再依據值對節點行排序；

S400，根據值異步更新標簽：按照步驟S300中得到的排序，使用異步更新的方法，依次對節點標簽進行更新，計算節點的標簽隸屬度，決定是否保留以前的標簽和是否增加新標簽；

S500，對比節點標簽傳播前后狀態：根據步驟S400中得到的節點標簽集合，對比在更新前的節點與其鄰接節點標簽集合，如果相同則進入下一步驟，如果有變化則返回步驟S400再進行一輪標簽更新；

S600，輸出結果：輸出重疊社區發現的結果。

2.根據權利要求1所述的一種基于多標簽傳播的半監督重疊社區發現算法，其特征在于，所述復雜網絡是有節點、邊和邊的權重構成的結構化數據形式，主要數學表達形式為，代表復雜網絡，代表頂點的集合，代表邊的集合。

3.根據權利要求1所述的一種基于多標簽傳播的半監督重疊社區發現算法，其特征在于，所述Bron-Kerbosch算法是用來探尋網絡中極大團的算法，其中極大團是指由復雜網絡中節點的集合構成的最大集合，且集合中任意的兩個節點之間有邊相連。

4.根據權利要求1所述的一種基于多標簽傳播的半監督重疊社區發現算法，其特征在于，所述PageRank值算法根據節點的度計算節點在復雜網絡中的影響力，讓影響力大的節點優先更新，避免影響力小的節點對社區發現算法的干擾，其計算公式為：

其中，是復雜網絡中的一個節點；

是節點的PageRank值；

是復雜網絡中所有節點數量；

是需要預先設定的阻尼系數，且設為0.85；

是的鄰接節點；

是的鄰接節點的集合；

是的度。

5.根據權利要求1所述的一種基于多標簽傳播的半監督重疊社區發現算法，其特征在于，所述標簽隸屬度的計算公式為：

其中，是指在次迭代后節點對于標簽的隸屬度，且。

6.根據權利要求5所述的一種基于多標簽傳播的半監督重疊社區發現算法，其特征在于，一個節點每次迭代中對于所有標簽的隸屬度之和為1，其計算公式為：

其中，代表節點隸屬的標簽的集合；

是集合中的一個節點標簽；

是集合中的一個鄰接節點標簽。