Patent ID: 7844634

Claim:
A computer-implemented method for discovering a community around a given entity in an interaction graph, wherein nodes in the graph represent entities and edges connecting nodes in the graph represent interactions between connected nodes, the method comprising: partitioning nodes in the interaction graph into different sets of nodes based on interaction information associated with each node to minimize a number of interaction pairs that need to be considered, wherein the different sets comprise at least one of a first set and a second set wherein nodes in the first set are candidates for the community being identified and nodes in the second set are nodes connected to one or more nodes in the first set but are not in the first set; minimizing an objective function based at least in part on a number of edges leaving at least one of the different sets of nodes, wherein the objective function minimizing step comprises determining whether or not to move one or more nodes between the first and second sets based on whether or not a given move minimizes a measure associated with the objective function; and identifying the nodes in the first set as the community around the given entity in the interaction graph when the objective function is minimized; wherein each step of the method is performed by one or more computing systems.