Centroid-Based Multiple Local Community Detection

In recent years, the research of local community detection has attracted much attention. Most existing local community detection methods aim to find a single community of closely related nodes for a given query node, but in general, nodes are possible to belong to several communities, and detecting all the potential communities for a given query node is much more challenging. In this work, we propose a novel approach called the centroid-based multiple local community detection (C-MLC) to find all the communities for a query node. Differing from the existing local community detection methods that directly find a community from the query node, we assume that every community contains a "centroid " node, which locates in the core of the community and can be used to identify the community. Then, a query node corresponds to several centroid nodes if the query node belongs to multiple communities. The key ideas of C-MLC are that C-MLC automatically determines the number of communities containing the query node by finding the related centroid nodes and uses each query node together with the centroid node to uncover the corresponding community based on a set of high-quality seeds. Through extensive evaluations on real-world networks and synthetic networks, C-MLC outperforms the state-of-the-art methods significantly, demonstrating that finding the centroid nodes is a better approach to uncover the multiple local communities.