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:
parsing patent data to generate a set of nodes; selecting at least one node of the set of nodes; determining initial links from meta data associated with the patent data for the at least one node; creating links among the set of nodes based on the metadata; identifying a set of seed nodes; determining a community structure for the set of seed nodes, the community structure including a plurality of communities; and assigning concepts to the plurality of communities, wherein determining the community structure comprises: 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; andtransmitting 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.