Methods and apparatus for distributed community finding
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.