Methods and apparatus for distributed community finding

A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method, the instructions comprising instructions for:

• 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.

A program storage device readable by a machine, embodying a program of instructions executable by the machine to perform a method, the instructions comprising instructions for:

• 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.

An apparatus comprising:

• memory;
• one or more computers coupled to the memory, the one or more computers configured to:
• initiate 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;
• propagate 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;
• collect each response to the percolation message at the source node;
• and
• store a list of nodes that transmitted the response at the source node in the memory.

An apparatus comprising:

• memory;
• one or more computers coupled to the memory, the one or more computers configured to:
• assign a set of nodes as source nodes;
• initiate 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;
• determine a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;
• aggregate 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;
• plot the local neighborhood size versus percolation probabilities for each of the local neighborhoods;
• locate phase transition points in the plot;
• and
• determine nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.

An apparatus comprising:

• memory;
• one or more computers coupled to the memory, the one or more computers configured to:
• select a node in a network as a source node;
• compute a set of local communities for the source node;
• identify a set of nodes in the set of local communities having a weight greater than a threshold;
• generate a strong local community for the source node including only the set of nodes that have a weight greater than the threshold;
• store the strong local community as one of a plurality of communities of the network;
• remove 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;
• select a node in the reduced network as a second source node;
• generate a second strong local community for the second source node, the second strong local community comprising a second set of nodes;
• store the second strong local community as one of the plurality of communities of the network;
• remove the second set of nodes in the second strong local community from the network to generate a second reduced network;
• repeat 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
• label 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.

An apparatus comprising:

• memory;
• one or more computers coupled to the memory, the one or more computers comprising:
• means for 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;
• means for propagating the percolation message through the linked network, wherein propagating the percolation message through the linked network comprises:
• means for transmitting the percolation message from each node that receives the percolation message to each neighbor of each node that receives the percolation message;
• and
• means for transmitting a response to the source node from each node that receives the percolation message;
• means for collecting each response to the percolation message at the source node;
• and
• means for storing a list of nodes that transmitted the response at the source node.

An apparatus comprising:

• memory;
• one or more computers coupled to the memory, the one or more computers comprising:
• means for assigning a set of nodes as source nodes;
• means for 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;
• means for determining a list of nodes that received the plurality of percolation messages for each of the plurality of source nodes;
• means for 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;
• means for plotting the local neighborhood size versus percolation probabilities for each of the local neighborhoods;
• means for locating phase transition points in the plot;
• and
• means for determining nested local communities for the plurality of source nodes by combining the local neighborhoods at the phase transition points.

An apparatus comprising:

• memory;
• one or more computers coupled to the memory, the one or more computers comprising:
• means for selecting a node in a network as a source node;
• means for computing a set of local communities for the source node;
• means for identifying a set of nodes in the set of local communities having a weight greater than a threshold;
• means for generating a strong local community for the source node including only the set of nodes that have a weight greater than the threshold;
• means for storing the strong local community as one of a plurality of communities of the network;
• means for 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;
• means for selecting a node in the reduced network as a second source node;
• means for generating a second strong local community for the second source node, the second strong local community comprising a second set of nodes;
• means for storing the second strong local community as one of the plurality of communities of the network;
• means for removing the second set of nodes in the second strong local community from the network to generate a second reduced network;
• means for 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
• means for 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.