METHOD 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 presented. Instead of partitioning the graph into separate subgraphs from top to bottom we propose a local algorithm (communities of each vertex) to the top which allows overlapping of communities. The performance of an algorithm on synthetic randomly generated graphs and real-world networks is used to benchmark other methods. A 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.