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

在審

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

本發明實施例提供一種社區發現方法、裝置及設備，該方法包括：根據網絡中每個頂點的重要程度，在所述網絡中確定至少一個核心頂點，每個頂點的重要程度為根據預設算法確定得到的；根據所述至少一個核心頂點確定至少一個子社區；根據所述網絡中每個擴展頂點對對應的第一鄰接頂點的引力和所述至少一個子社區，確定至少一個社區，所述擴展頂點為所述網絡中除所述核心頂點之外的頂點，一個擴展頂點對應的第一鄰接頂點為與該擴展頂點構成三角形的鄰接頂點。提高了發現的社區的精確性。

技術領域

本發明實施例涉及計算機領域，尤其涉及一種社區發現方法、裝置及設備。

背景技術

社區發現是指在網絡中確定不同的社區，其中，一個社區內部的連接關系連接緊密，社區之間的連接關系稀疏。

網絡中包括多個頂點和邊，不同的頂點通過邊連接。在現有技術中，通常采用基于模塊化最大的Fast-Newman算法、廣播-監聽標簽傳遞算法(Speaker-listener LabelPropagation Algorithm，簡稱SLPA)和基于GraphLab的依靠核心點依賴的算法等進行社區發現，上述算法均以邊為社區擴展的最小單元進行社區發現，使得發現的社區內部的連接關系不夠緊密，或者社區之間的連接關系不夠稀疏，導致發現的社區的精確性較差。

發明內容

本發明實施例提供一種社區發現方法、裝置及設備，提高了發現的社區的精確性。

第一方面，本發明實施例提供一種社區發現方法，包括：

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

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

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

在一種可能的實施方式中，所述根據所述網絡中每個擴展頂點對對應的第一鄰接頂點的引力和所述至少一個子社區，確定至少一個社區，包括：

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

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

在另一種可能的實施方式中，針對第一擴展頂點，根據所述第一擴展頂點對對應的第一鄰接頂點的引力，確定所述第一擴展頂點對應的子社區，包括：

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

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

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

在另一種可能的實施方式中，所述根據第一子社區中每個頂點對對應的第二鄰接頂點的引力，確定所述第一擴展頂點加入所述第一子社區之前、所述第一子社區的第一凝聚度，包括：

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