[發明專利]社區發現方法、裝置及設備

在審

• 申請號: 201811285653.3
• 申請日: 2018-10-31
• 公開（公告）號: CN111125481A
• 公開（公告）日: 2020-05-08
• 發明（設計）人: 潘劍飛;戴明洋;石逸軒;羅程亮;姚遠;楊勝文;范斌;周俊;許金泉;陳家偉;王棟;劉少杰;劉康;王楠
• 申請（專利權）人: 百度在線網絡技術（北京）有限公司
• 主分類號: G06F16/951
• 分類號: G06F16/951
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 孫靜;劉芳

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

根據網絡中每個頂點的重要程度，在所述網絡中確定至少一個核心頂點，每個頂點的重要程度為根據預設算法確定得到的；

根據所述至少一個核心頂點確定至少一個子社區；

根據所述網絡中每個擴展頂點對對應的第一鄰接頂點的引力和所述至少一個子社區，確定至少一個社區，所述擴展頂點為所述網絡中除所述核心頂點之外的頂點，一個擴展頂點對應的第一鄰接頂點為與該擴展頂點構成三角形的鄰接頂點。

2.根據權利要求1所述的方法，其特征在于，所述根據所述網絡中每個擴展頂點對對應的第一鄰接頂點的引力和所述至少一個子社區，確定至少一個社區，包括：

根據每個擴展頂點對對應的第一鄰接頂點的引力，確定每個擴展頂點對應的子社區；

將每個擴展頂點添加至對應的子社區，得到所述至少一個社區。

3.根據權利要求2所述的方法，其特征在于，針對第一擴展頂點，根據所述第一擴展頂點對對應的第一鄰接頂點的引力，確定所述第一擴展頂點對應的子社區，包括：

根據第一子社區中每個頂點對對應的第二鄰接頂點的引力，確定所述第一擴展頂點加入所述第一子社區之前、所述第一子社區的第一凝聚度，所述第一子社區為所述至少一個子社區中的任意一個子社區，所述第一子社區中一個頂點對應的第二鄰接頂點為與該頂點構成三角形的鄰接頂點；

根據所述第一擴展頂點對對應的第一鄰接頂點的引力，以及所述第一子社區中每個頂點對對應的第二鄰接頂點的引力，確定所述第一擴展頂點加入所述第一子社區之后、所述第一子社區的第二凝聚度；

若所述第二凝聚度大于所述第一凝聚度，則確定所述第一子社區為所述第一擴展頂點對應的子社區。

4.根據權利要求3所述的方法，其特征在于，所述根據第一子社區中每個頂點對對應的第二鄰接頂點的引力，確定所述第一擴展頂點加入所述第一子社區之前、所述第一子社區的第一凝聚度，包括：

根據所述第一子社區中每個頂點對對應的第二鄰接頂點的引力，確定所述第一子社區中每個頂點在所述第一子社區下的凝聚度，根據所述第一子社區中每個頂點在所述第一子社區下的凝聚度，確定所述第一凝聚度；

所述根據所述第一擴展頂點對對應的第二鄰接頂點的引力，以及所述第一子社區中每個頂點對對應的第二鄰接頂點的引力，確定所述第一擴展頂點加入所述第一子社區之后、所述第一子社區的第二凝聚度，包括：

根據所述第一子社區中每個頂點對對應的第二鄰接頂點的引力，確定所述第一子社區中每個頂點在所述第一子社區下的凝聚度；根據所述第一擴展頂點對對應的第一鄰接頂點的引力，確定所述第一擴展頂點在所述第一子社區下的凝聚度；根據所述第一子社區中每個頂點在所述第一子社區下的凝聚度、以及所述第一擴展頂點在所述第一子社區下的凝聚度，確定所述第二凝聚度。

5.根據權利要求4所述的方法，其特征在于，針對所述第一擴展頂點和所述第一子社區中的頂點中的任意一個第一頂點，根據所述第一頂點對與所述第一頂點構成三角形的鄰接頂點的引力，確定所述第一頂點在所述第一子社區下的凝聚度，包括：

根據如下公式一，確定所述第一頂點在所述第一子社區下的凝聚度：

其中，x為所述第一頂點，所述C為所述第一子社區，所述|C|為所述第一子社區中的頂點個數，所述PT_C(x)為所述第一頂點在所述第一子社區下的凝聚度，所述vt_c(x)為所述第一子社區中與所述第一頂點構成三角形的頂點的個數，所述NT_x為與所述第一頂點形成三角形的頂點集合，所述其中，所述PR(y)為頂點y的PageRank值，所述d_tri(y)為與所述頂點y構成三角形的邊的個數。