Method and apparatus for distributed community finding

• US 20060271564A1
• Filed: 05/10/2005
• Published: 11/30/2006
• Est. Priority Date: 05/10/2005
• Status: Active Grant

• Current Assignee: NetSeer, Inc. (Inuvo, Inc.)
• Original Assignee: Pekua Incorporated
• Inventors: Rezaei, Behnam Attaran, Meng Muntz, Alice Hwei-Yuan
• Granted Patent: US 7,958,120 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: Y10S 707/93 intellectual property analysis
• CPC Class Codes: Y10S 707/937 intellectual property searching
• CPC Class Codes: Y10S 707/959 Network

Abstract

Methods and apparatus for a new approach to the problem of finding communities in complex networks relating to a social definition of communities and percolation are disclosed. Instead of partitioning the graph into separate subgraphs from top to bottom a local algorithm (communities of each vertex) allows overlapping of communities. The performance of an algorithm on synthetic, randomly-generated graphs and real-world networks is used to benchmark this method against others. An heuristic is provided to generate a list of communities for networks using a local community finding algorithm. Unlike diffusion based algorithms, The provided algorithm finds overlapping communities and provides a means to measure confidence in community structure. It features locality and low complexity for exploring the communities for a subset of network nodes, without the need for exploring the whole graph.

Claims

18. Apparatus for grouping linked data into communities comprising computing hardware loaded with software encoding a percolation-based algorithm according to the present invention.

19. Apparatus for grouping linked data into communities comprising firmware encoding a percolation-based algorithm according to the present invention

20. A computer-implemented method for grouping linked nodes into communities comprising the steps of:

specifying a weight for each link;

assigning a weight to each node;

initiating a percolation message from a specified node;

determining the connected component comprising nodes that receive messages repeatedly; and

identifying a community as a set for which the size of the set does not increase as percolation probability is increased;

1. A computer-implemented method for grouping linked data into potentially overlapping communities comprising the steps of determining a local community for a node, and applying said local community to obtain properties of an object.

2. The method according to claim 1 further comprising the steps of generating at least two local communities and merging at least two local communities into a community structure.

3. The method according to claim 1 wherein said determining step comprises of the step of quantifying the strength with which the node belongs to a community.

4. The method according to claim 1 wherein said determining step comprises the step of employing bond percolation from a node whose local communities are being sought.

5. The method according to claim 2 wherein said determining step comprises the step of employing bond percolation from a set of nodes whose local communities are being sought.

6. The method according to claim 5 wherein said employing step comprises the steps of initiating a percolation message from a node, and identifying community as a connected component comprising nodes receiving the sent message for which its size does not increase as percolation probability is increased.

7. The method according to claim 6 wherein said initiating step comprises the step of sending individual percolation messages from a set of nodes, and determining communities as connected components, comprising nodes receiving the sent messages

8. The method according to claim 1 wherein said determining step comprises the step of specifying a weight for each link and determining weighted local communities.

9. The method according to claim 1 wherein said determining step comprises the step of specifying a weight for each node and determining weighted local communities.

10. The method according to claim 8 wherein said weight specifying step comprises the step of specifying weights dependent on user query.

11. The method according to claim 8 wherein said weight specifying step comprises the step of specifying weights independent of a user query.

12. The method according to claim 9 wherein said weight specifying step comprises the step of specifying weights dependent on a user query.

13. The method according to claim 9 wherein said weight specifying step comprises the step of specifying weights independent of a user query.

14. The method according to claim 4 further comprising the step of generating s set of initial nodes from an initial query.

15. The method according to claim 6 further comprising the step of constructing a set of initial nodes from an initial query.

16. The method according to claim 1 further comprising the step of modifying the linked data according to communities found as a result of said determining step.

17. The method according to claim 5 wherein said employing step comprises the steps of initiating bond percolation on the whole graph iteratively and recognizing global communities by a determination of nodes that co-occur in the same connected component over many repetitions of a bond percolation step.

22. The method according to claim 20 wherein said identifying step comprises the step of displaying links and nodes in the identified communities.

determining the connected components comprising nodes that receive messages repeatedly;

and identifying communities as sets for which the size of the set does not increase as percolation probability is increased;

23. The method according to claim 20 wherein said identifying step comprises the step of displaying annotations representing meta-information for a link and nodes in the identified communities.

24. The method according to claim 23 wherein said identified annotated communities are divided into sub-communities by retaining nodes and links with only specified information in their annotations.

25. The method according to claim 20 further comprising the steps of:

changing a weight; and

repeating said initiating, and determining steps.

26. The method according to claim 25 further comprising the step of iterating said changing and repeating steps.

27. The method according to claim 20 further comprising the steps of:

supplying additional linked data;

repeating said initiating and determining steps; and

alerting a user to the result of said repeating step.

28. The method according to claim 20 further comprising the step of obtaining intra-community strengths and displaying the relationship between communities.

29. The method according to claim 20 further comprising the step of repeating said initiating, and determining steps over time and comparing the identified communities.

30. The method according to claim 23 further comprising the step of viewing said identified annotated communities as dynamic objects that have evolved in time by using the time stamp information available in the annotation of nodes and links.

31. The method according to claim 29 wherein said repeating step comprises the step of retaining information present before the repeating step is performed.

21. A computer-implemented method for grouping linked nodes into communities comprising the steps of:

specifying a weight for each link;

assigning a weight to each node;

initiating percolation messages from a specified set of nodes;

determining the connected components comprising nodes that receive messages repeatedly; and

identifying communities as sets for which the size of the set does not increase as percolation probability is increased;

22-1. The method according to claim 20 wherein said identifying step comprises the step of displaying links and nodes in the identified communities.