Method and apparatus for distributed community finding
First Claim
1. A computer-implemented method comprising:
- initiating a percolation message from a source node of a linked network, the linked network 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 linked network, wherein propagating the percolation message through the linked network 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.
8 Assignments
0 Petitions
Accused Products
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.
-
Citations
24 Claims
-
1. A computer-implemented method comprising:
-
initiating a percolation message from a source node of a linked network, the linked network 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 linked network, wherein propagating the percolation message through the linked network 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A computer-implemented method comprising:
-
assigning a set of nodes as source nodes; initiating a plurality of percolation messages from each 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; 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. - View Dependent Claims (16, 17, 18)
-
-
19. A computer-implemented method comprising:
-
selecting a node in a network as a source node; computing a set of local communities for the source node; identifying a set of nodes in the set of local communities having a weight greater than a threshold; generating a strong local community for the source node including only the set of nodes that have a weight greater than the threshold; storing the strong local community as one of a plurality of communities of the network; removing the set of nodes in the strong local community and edges connected to the set of nodes from the network to generate a reduced network; selecting a node in the reduced network as a second source node; generating a second strong local community for the second source node, the second strong local community comprising a second set of nodes; storing the second strong local community as one of the plurality of communities of the network; removing the second set of nodes in the second strong local community from the network to generate a second reduced network; repeating the selecting, generating, storing and removing until a reduced network is generated that comprises only nodes with a degree less than a threshold value; and labeling the set of stored strong local communities as one of a disjoint community structure of the network or an overlapping community structure of the network. - View Dependent Claims (20, 21, 22, 23, 24)
-
Specification