METHOD OF DETECTING OVERLAPPING COMMUNITY IN NETWORK

• US 20140149430A1
• Filed: 06/28/2013
• Published: 05/29/2014
• Est. Priority Date: 11/28/2012
• Status: Abandoned Application

• Current Assignee: Korea Advanced Institute of Science and Technology, Samsung Electronics Co. Ltd.
• Original Assignee: Korea Advanced Institute of Science and Technology, Samsung Electronics Co. Ltd.
• Inventors: RYU, Seungwoo, KWON, Sejeong, LEE, Jae-Gil, LIM, Sungsu
• Application Number:
  US13/930,069
• Publication Number:
  US 20140149430A1
• Time in Patent Office: Days
• US Class Current: 707/749
• CPC Class Codes: G06F 16/24578 using ranking

Abstract

A method of detecting an overlapping community in a network including nodes and links between the nodes, includes calculating a similarity between the links, and generating a line graph of the network. The method further includes detecting one or more cores in the line graph, and growing a cluster for each of the one or more cores. The method further includes converting the cluster into a cluster of nodes of a node graph.

Claims

1. A method of detecting an overlapping community in a network comprising nodes and links between the nodes, comprising:

calculating a similarity between the links;

generating a line graph of the network;

detecting one or more cores in the line graph;

growing a cluster for each of the one or more cores; and

converting the cluster into a cluster of nodes of a node graph.

2. The method of claim 1, wherein each of the one or more cores is a vertex of the line graph that comprises a ratio between a number of neighboring vertices comprising a similarity to the vertex that exceeds a predetermined similarity and a total number of neighboring vertices, that is greater than a predetermined ratio, among vertices of the line graph that correspond to the links.

3. The method of claim 2, further comprising:

fixing the predetermined ratio to a value; and

determining the predetermined similarity based on the predetermined ratio.

4. The method of claim 1, wherein the growing comprises:

assigning a cluster identifier (ID) distinguished for each of the one or more cores to each of the one or more cores; and

assigning the same cluster ID of a core to a neighboring vertex comprising a similarity to the core that is greater than a predetermined similarity, for each of one or more neighboring vertices of each of the one or more cores.

5. The method of claim 4, wherein the converting comprises:

labeling a vertex to which the cluster ID is unassigned as a non-member, among the one or more neighboring vertices.

6. The method of claim 4, wherein the converting comprises:

excluding a vertex to which the cluster ID is unassigned, among the one or more neighboring vertices.

7. The method of claim 1, wherein the calculating comprises:

calculating a similarity of each of pairs of the links.

8. The method of claim 7, wherein the detecting comprises:

detecting the one or more cores in the line graph based on the similarity of each of the pairs of the links.

9. The method of claim 7, wherein the growing comprises:

growing the cluster of the links for each of the one or more cores based on the similarity of each of the pairs of the links.

10. A non-transitory computer-readable storage medium storing a program comprising instructions to cause a computer to perform the method of claim 1.

11. A method of detecting an overlapping community in a network comprising nodes and links between the nodes, comprising:

generating a line graph of the network;

detecting one or more cores in the line graph;

growing a cluster for each of the one or more cores;

calculating a similarity between the links; and

converting the cluster into a cluster of nodes of a node graph.

12. The method of claim 11, wherein each of the one or more cores is a vertex of the line graph that comprises a ratio between a number of neighboring vertices comprising a similarity to the vertex that exceeds a predetermined similarity and a total number of neighboring vertices, that is greater than a predetermined ratio, among vertices of the line graph that correspond to the links.

13. The method of claim 11, wherein the growing comprises:

assigning a cluster identifier (ID) distinguished for each of the one or more cores to each of the one or more cores; and

assigning the same cluster ID of a core to a neighboring vertex comprising a similarity to the core that is greater than a predetermined similarity, for each of one or more neighboring vertices of each of the one or more cores.

14. The method of claim 13, wherein the converting comprises:

labeling a vertex to which the cluster ID is unassigned as a non-member, among the one or more neighboring vertices.

15. The method of claim 13, wherein the converting comprises:

excluding a vertex to which the cluster ID is unassigned, among the one or more neighboring vertices.

16. A non-transitory computer-readable storage medium storing a program comprising instructions to cause a computer to perform the method of claim 11.