System and method for discovering communities in networks

• US 20060080422A1
• Filed: 06/02/2004
• Published: 04/13/2006
• Est. Priority Date: 06/02/2004
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Huberman, Bernardo, Wu, Fang
• Granted Patent: US 7,644,146 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

The disclosed embodiments relate to a system and method for discovering communities in networks. The system and method may include selecting a plurality of nodes from a network of nodes to serve as poles, setting weight values for the poles, applying a community-discovering algorithm based on the weight values, and dividing the network into communities based on a result obtained from the community-discovering algorithm.

Claims

1. A method for discovering communities in networks, comprising:

selecting a plurality of nodes from a network of nodes to serve as poles;

setting weight values for the poles;

applying a community-discovering algorithm based on the weight values; and

dividing the network into communities based on a result obtained from the community-discovering algorithm.

2. The method of claim 1, comprising defining the community-discovering algorithm to comprise an electrical analogy algorithm.

3. The method of claim 1, comprising defining the community-discovering analogy algorithm to be a voltage analogy algorithm.

4. The method of claim 1, comprising assigning unit-length vector weights as weight values.

5. The method of claim 1, comprising assigning theoretical voltages to the poles.

6. The method of claim 1, comprising solving modified Kirchhoff equations for vector sums.

7. The method of claim 1, comprising selecting a first node and performing a breadth-first search to find a second node.

8. The method of claim 1, comprising establishing weight values for other nodes in the network.

9. The method of claim 8, comprising:

defining a community size tolerance;

sorting the weight values of the poles and other nodes using a standard linear time sort;

determining a set of near the middle gaps in the sorted weight values based on the community size tolerance; and

selecting a largest gap from the set of near the middle gaps.

10. A method for discovering communities in networks, comprising:

selecting two nodes that are not neighboring nodes;

setting weight values for the two nodes;

applying a community-discovering algorithm to the network to establish node groups; and

using the node groups to determine communities.

11. The method of claim 10, comprising defining the community-discovering algorithm to comprise an electrical analogy algorithm.

12. The method of claim 10, comprising defining the community-discovering algorithm to comprise a voltage analogy algorithm.

13. The method of claim 10, comprising using a majority vote on the node groups to determine the communities.

14. The method of claim 10, comprising assigning unit-length vector weights as weight values.

15. The method of claim 10, comprising assigning theoretical voltages to the two nodes.

16. The method of claim 10, comprising solving modified Kirchhoff equations for vector sums.

17. The method of claim 10, comprising selecting a first node and performing a breadth-first search to find a second node.

18. The method of claim 10, comprising establishing weight values for other nodes in the network.

19. The method of claim 18, comprising:

defining a community size tolerance;

sorting the weight values of the two nodes and other nodes using a standard linear time sort;

determining a set of near-the-middle gaps in the sorted weight values based on the community size tolerance; and

selecting a largest gap from the set of near-the-middle gaps.

20. A system for discovering communities in networks, comprising:

a selection module, the selection module adapted for selecting a plurality of nodes from a network of nodes to serve as poles;

a weight module, the weight module adapted for setting weight values for the poles;

a community-determining module, the community-determining module adapted for applying a community-determining algorithm to the network to obtain results; and

a division module, the division module adapted for dividing the network into communities based on the results.

21. The system of claim 20, wherein the community-determining algorithm comprises an electrical analogy algorithm.

22. The system of claim 21, wherein the electrical analogy algorithm comprises a voltage analogy algorithm.

23. The system of claim 20, comprising a search module, the search module adapted for selecting a first node and performing a breadth-first search to find a second node.

24. A computer program for discovering communities in networks, comprising:

a tangible medium;

a selection module stored on the tangible medium, the selection module adapted for selecting a plurality of nodes from a network of nodes to serve as poles;

a weight module stored on the tangible medium, the weight module adapted for setting weight values for the poles;

an electrical analogy module stored on the tangible medium, the electrical analogy module adapted for applying an electrical analogy algorithm to the poles and the network to obtain results; and

a division module stored on the tangible medium, the division module adapted for dividing the network into communities based on the results.