Community discovery method, device, server and computer storage medium

Patent metadata

Field	Value
Publication number	US-10846052-B2
Application number	US-201716310920-A
Country	US
Kind code	B2
Filing date	Oct 12, 2017
Priority date	Oct 27, 2016
Publication date	Nov 24, 2020
Grant date	Nov 24, 2020

Abstract

A community discovery method is provided. The community discover method includes partitioning nodes in a social network into community nodes partitioned into n first communities, each of the n first communities being associated with a corresponding community label, the corresponding label of each of the community nodes initially indicating a first community from among the n first communities to which the community node belongs, and n being an integer greater than or equal to 2; updating the corresponding label of each community node comprised in the n first communities; and partitioning the community nodes into m second communities, each of the community nodes in each of the m second communities having a same label, and m being a positive integer less than n.

First claim

What is claimed is:

1. A community discovery method, the community discovery method being performed by one or more processors, and the community discovery method comprising:
partitioning nodes in a social network into community nodes partitioned into n first communities, each of the n first communities being associated with a corresponding community label, the corresponding label of each of the community nodes initially indicating a first community from among the n first communities to which the community node belongs, and n being an integer greater than or equal to 2;
updating the corresponding label of each community node comprised in the n first communities; and
partitioning the community nodes into m second communities, each of the community nodes in each of the m second communities having a same label, and m being a positive integer less than n,
wherein the updating comprises:
traversing each community node to determine a first quantity for each of the community nodes, the first quantity indicating a quantity of community nodes in the first community to which the corresponding community node belongs;
determining a second quantity for each of the community nodes, the second quantity indicating a quantity of community nodes comprised in a neighboring first community of the corresponding community node with a largest quantity of community nodes;
determining structural similarity based on a first adjacency matrix and a second adjacency matrix, the first node quantity and the second node quantity; and
updating the corresponding label of each community node to a label of the neighboring first community corresponding to the second quantity, based on the second quantity being greater than the first quantity.

2. The community discovery method according to claim 1 , further comprising:
determining whether a total quantity of community nodes whose labels change reaches a quantity threshold, after traversing each community node;
traversing each community node again, based on the total quantity of the community nodes whose labels change reaching the quantity threshold; and
ending traversal, based on the total quantity of the community nodes whose labels change not reaching the quantity threshold.

3. The community discovery method according to claim 2 , further comprising sorting the community nodes based on importance of each community node,
wherein the first quantity of each community node is determined after the sorting.

4. The community discovery method according to claim 3 , wherein the sorting the community nodes based on importance of each community node comprises sorting the community nodes in descending order of clustering coefficients of the community nodes.

5. The community discovery method according to claim 3 , wherein the sorting the community nodes based on importance of each community node comprises sorting the community nodes according to a Pagerank algorithm.

6. The community discovery method according to claim 3 , wherein the sorting the community nodes based on importance of each community node comprises sorting the community nodes in descending order of degrees of the community nodes, and
wherein the degrees of the community nodes represent quantities of the neighboring community nodes that are neighboring the community nodes.

7. A community discovery apparatus comprising:
at least one memory configured to store computer program code; and
at least one processor configured to access the at least one memory and operate according to the computer program code, the computer program code comprising:
partitioning code configured to cause the at least one processor to partition nodes in a social network into community nodes partitioned into n first communities, each of the n first communities being associated with a corresponding community label, the corresponding label of each of the community nodes initially indicating a first community from among the n first communities to which the community node belongs, and n being an integer greater than or equal to 2;
update code configured to cause the at least one processor to update the corresponding label of each community node comprised in the n first communities; and
merging code configured to cause the at least one processor to partition the community nodes into m second communities, each of the community nodes in each of the m second communities having a same label, and m being a positive integer less than n,

wherein the update code is further configured to cause the at least one processor to:
traverse each community node to determine a first quantity for each of the community nodes, the first quantity indicating a quantity of community nodes in the first community to which the corresponding community node belongs;
determine a second quantity for each of the community nodes, the second quantity indicating a quantity of community nodes comprised in a neighboring first community of the corresponding community node with a largest quantity of community nodes;
determine structural similarity based on a first adjacency matrix and a second adjacency matrix, the first node quantity and the second node quantity; and
update the corresponding label of each community node to a label of the neighboring first community corresponding to the second quantity, based on the second quantity being greater than the first quantity.

8. The community discovery apparatus according to claim 7 , wherein the computer code further comprises:
determining code configured to cause the at least one processor to determine whether a total quantity of community nodes whose labels change reaches a quantity threshold, after traversing each community node;
first result code configured to cause the at least one processor to traverse each community node again based on the total quantity of the community nodes whose labels change reaching the quantity threshold; and
second result code configured to cause the at least one processor to end traversal based on the total quantity of the community nodes whose labels change not reaching the quantity threshold.

9. The community discovery apparatus according to claim 8 , wherein the computer code further comprises sorting code configured cause the at least one processor to sort the community nodes based on importance of each community node, and
wherein the first acquiring code is further configured to cause the at least one processor to acquire the first quantity of each community node after the community nodes are sorted.

10. The community discovery apparatus according to claim 9 , wherein the sorting code is further configured to cause the at least one processor to sort the community nodes in descending order of clustering coefficients of the community nodes.

11. The community discovery apparatus according to claim 9 , wherein the sorting code is further configured to cause the at least one processor to sort the community nodes according to a Pagerank algorithm.

12. The community discovery apparatus according to claim 9 , wherein the sorting code is further configured to cause the at least one processor to sort the community nodes in descending order of degrees of the community nodes, and
wherein the degrees of the community nodes represent quantities of the neighboring community nodes that are neighboring to the community nodes.

13. The community discovery apparatus according to claim 7 , wherein the community discovery apparatus comprises a server.

14. A non-transitory computer-readable storage medium storing instructions that cause at least one processor to perform a community discovery method comprising:
partitioning nodes in a social network i

Assignees

• Tencent Tech Shenzhen Co Ltd

Inventors

• Liu Jiahao
• Ling Guohui
• Zheng Zibin
• Chen Chuan

Classifications

• G06Q10/40 Primary

  Business processes related to social networking or social networking services · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06Q50/00

  Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism (healthcare informatics G16H) · CPC title

• G06F16/24578

  using ranking · CPC title

• G06F7/24 Primary

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title