Methods and apparatus for distributed community finding

• US 8,825,654 B2
• Filed: 10/25/2012
• Issued: 09/02/2014
• Est. Priority Date: 05/10/2005
• Status: Active Grant

• Current Assignee: NetSeer, Inc. (Inuvo, Inc.)
• Original Assignee: NetSeer, Inc. (Inuvo, Inc.)
• Inventors: Muntz, Alice Hwei-Yuan Meng, Rezaei, Behnam Attaran
• Primary Examiner(s): Pulliam, Christyann
• Assistant Examiner(s): Mahmood, Rezwanul
• Application Number:
  US13/660,955
• Publication Number:
  US 20130046842A1
• Time in Patent Office: 677 Days
• Field of Search: 707/709, 707/736, 707/959, 707/603, 707/692, 707/732, 707/737, 707/758
• US Class Current: 707/737
• 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

1. A method comprising:

maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and

analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community,

wherein the percolation community finding algorithm comprises;

initiating a percolation message from a source node of the distributed user community, the distributed user community comprising a plurality of nodes and a plurality of edges, each edge connecting at least two of the plurality of nodes, wherein a node is a neighbor if the node is connected to another node in the plurality of nodes by an edge, wherein the percolation message comprises a percolation probability and an identifier of the source node, and wherein initiating a percolation message from the source node comprises transmitting the percolation message to each neighbor of the source node with the percolation probability;

propagating the percolation message through the distributed user community, wherein propagating the percolation message through the distributed user community comprises;

transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message; and

transmitting a response to the source node from each node that receives the percolation message;

collecting each response to the percolation message at the source node; and

storing a list of nodes that transmitted the response at the source node.

2. The method of claim 1, further comprising identifying the email as spam.

3. The method of claim 1, further comprising forwarding the email to the user.

4. The method of claim 3, further comprising modifying the header of the email prior to forwarding the email to the user.

6. The method of claim 1, wherein each edge comprises a link, and further comprising:

specifying a weight for each link; and

determining a weight for each of the plurality of communities.

7. The method of claim 6, further comprising modifying the weight for each link, and determining a modified weight for each of the plurality of communities.

8. The method of claim 1 further comprising:

specifying a weight for each of the plurality of nodes; and

determining a weight for each of the plurality of communities.

9. The method of claim 8, further comprising modifying the weight for each node, and determining a modified weight for each of the plurality of communities.

5. A method comprising:

maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and

analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community,

wherein the percolation community finding algorithm comprises;

initiating a plurality of percolation messages from each of a plurality of source nodes at a plurality of percolation probabilities, wherein the plurality of percolation probabilities are selected from a set of values between 0 and 1;

determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;

aggregating the list of nodes for each of the plurality of source nodes to determine a local neighborhood for each of the plurality of source nodes, wherein each node is weighted based on a number of times each node received the plurality of percolation messages;

plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods in a plot;

locating phase transition points in the plot; and

determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.

10. A non-transitory program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method, the method comprising:

maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and

analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community,

wherein the percolation community finding algorithm comprises;

initiating a percolation message from a source node of the distributed user community, the distributed user community comprising a plurality of nodes and a plurality of edges, each edge connecting at least two of the plurality of nodes, wherein a node is a neighbor if the node is connected to another node in the plurality of nodes by an edge, wherein the percolation message comprises a percolation probability and an identifier of the source node, and wherein initiating a percolation message from the source node comprises transmitting the percolation message to each neighbor of the source node with the percolation probability;

propagating the percolation message through the distributed user community, wherein propagating the percolation message through the distributed user community comprises;

transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message; and

transmitting a response to the source node from each node that receives the percolation message;

collecting each response to the percolation message at the source node; and

storing a list of nodes that transmitted the response at the source node.

11. The program storage device of claim 10, further comprising identifying the email as spam.

12. The program storage device of claim 10, further comprising forwarding the email to the user.

13. The program storage device of claim 12, further comprising modifying the header of the email prior to forwarding the email to the user.

15. The program storage device of claim 10, wherein each edge comprises a link, and further comprising:

specifying a weight for each link; and

determining a weight for each of the plurality of communities.

16. The program storage device of claim 15, further comprising modifying the weight for each link, and determining a modified weight for each of the plurality of communities.

17. The program storage device of claim 10 further comprising:

specifying a weight for each of the plurality of nodes; and

determining a weight for each of the plurality of communities.

18. The program storage device of claim 17, further comprising modifying the weight for each node, and determining a modified weight for each of the plurality of communities.

14. A non-transitory program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method, the method comprising:

maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and

analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community,

wherein the percolation community finding algorithm comprises;

initiating a plurality of percolation messages from each of a plurality of source nodes at a plurality of percolation probabilities, wherein the plurality of percolation probabilities are selected from a set of values between 0 and 1;

determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;

aggregating the list of nodes for each of the plurality of source nodes to determine a local neighborhood for each of the plurality of source nodes, wherein each node is weighted based on a number of times each node received the plurality of percolation messages;

plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods in a plot;

locating phase transition points in the plot; and

determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.

19. An apparatus comprising:

memory;

one or more computers configured to;

maintain a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and

analyze an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community,

wherein the percolation community finding algorithm comprises;

initiating a percolation message from a source node of the distributed user community, the distributed user community comprising a plurality of nodes and a plurality of edges, each edge connecting at least two of the plurality of nodes, wherein a node is a neighbor if the node is connected to another node in the plurality of nodes by an edge, wherein the percolation message comprises a percolation probability and an identifier of the source node, and wherein initiating a percolation message from the source node comprises transmitting the percolation message to each neighbor of the source node with the percolation probability;

propagating the percolation message through the distributed user community, wherein propagating the percolation message through the distributed user community comprises;

transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message; and

transmitting a response to the source node from each node that receives the percolation message;

collecting each response to the percolation message at the source node; and

storing a list of nodes that transmitted the response at the source node.

20. The apparatus of claim 19, wherein the one or more computers are further configured to identify the email as spam.

21. The apparatus of claim 19, wherein the one or more computers are further configured to forward the email to the user.

22. The apparatus of claim 21, wherein the one or more computers are further configured to modify the header of the email prior to forwarding the email to the user.

24. The apparatus of claim 19, wherein each edge comprises a link, and wherein the one or more computers are further configured to:

specify a weight for each link; and

determine a weight for each of the plurality of communities.

25. The apparatus of claim 24, wherein the one or more computers are further configured to modify the weight for each link, and determine a modified weight for each of the plurality of communities.

26. The apparatus of claim 19 wherein the one or more computers are further configured to:

specify a weight for each of the plurality of nodes; and

determine a weight for each of the plurality of communities.

27. The apparatus of claim 26, wherein the one or more computers are further configured to modify the weight for each node, and determine a modified weight for each of the plurality of communities.

23. An apparatus comprising:

memory;

one or more computers configured to;

maintain a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and

analyze an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community,

wherein the percolation community finding algorithm comprises;

initiating a plurality of percolation messages from each of a plurality of source nodes at a plurality of percolation probabilities, wherein the plurality of percolation probabilities are selected from a set of values between 0 and 1;

determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;

aggregating the list of nodes for each of the plurality of source nodes to determine a local neighborhood for each of the plurality of source nodes, wherein each node is weighted based on a number of times each node received the plurality of percolation messages;

plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods in a plot;

locating phase transition points in the plot; and

determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.

28. An apparatus comprising:

means for maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and

means for analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community,

wherein the percolation community finding algorithm comprises;

initiating a percolation message from a source node of the distributed user community, the distributed user community comprising a plurality of nodes and a plurality of edges, each edge connecting at least two of the plurality of nodes, wherein a node is a neighbor if the node is connected to another node in the plurality of nodes by an edge, wherein the percolation message comprises a percolation probability and an identifier of the source node, and wherein initiating a percolation message from the source node comprises transmitting the percolation message to each neighbor of the source node with the percolation probability;

propagating the percolation message through the distributed user community, wherein the means for propagating the percolation message through the distributed user community comprises;

transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message; and

transmitting a response to the source node from each node that receives the percolation message;

collecting each response to the percolation message at the source node; and

storing a list of nodes that transmitted the response at the source node.

29. The apparatus of claim 28, further comprising identifying the email as spam.

30. The apparatus of claim 28, further comprising forwarding the email to the user.

31. The apparatus of claim 30, further comprising modifying the header of the email prior to forwarding the email to the user.

33. The apparatus of claim 28, wherein each edge comprises a link, and further comprising:

means for specifying a weight for each link; and

means for determining a weight for each of the plurality of communities.

34. The apparatus of claim 33, further comprising means for modifying the weight for each link, and means for determining a modified weight for each of the plurality of communities.

35. The method of claim 28 further comprising:

means for specifying a weight for each of the plurality of nodes; and

means for determining a weight for each of the plurality of communities.

36. The apparatus of claim 35, further comprising means for modifying the weight for each node, and means for determining a modified weight for each of the plurality of communities.

32. An apparatus comprising:

means for maintaining a representation of a distributed user community stored in a database, the distributed user community comprising a plurality of overlapping user communities, wherein each user community comprises a contact list and contact addresses corresponding to the contact list; and

means for analyzing an email addressed to a user from a source by applying a percolation community finding algorithm to the distributed user community,

wherein the percolation community finding algorithm comprises;

initiating a plurality of percolation messages from each of a plurality of source nodes at a plurality of percolation probabilities, wherein the plurality of percolation probabilities are selected from a set of values between 0 and 1;

determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;

aggregating the list of nodes for each of the plurality of source nodes to determine a local neighborhood for each of the plurality of source nodes,

wherein each node is weighted based on a number of times each node received the plurality of percolation messages;

plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods in a plot;

locating phase transition points in the plot; and

determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.