Approximation of the Maximal Alpha -- Consensus Local Community Detection Problem in Complex Networks

The problem of community detection has received great attention by the complex networks researchers in the last decades. Although the notion of community does not actually have a unanimous accepted definition, it is generally admitted that it consists in a set of densely connected nodes. Moreover, density measures the strength of the relationships in the community. The need of these well connected and dense communities has led to the notion of "a -- consensus community. An "a -- consensus community, is a group of nodes where each member is connected to more than a proportion "a of the other nodes. An "a -- consensus community is maximal if and only if adding a new node to the set breaks the rule. Consequently, an "a -- consensus community has a density greater than "a. Existing methods for mining "a -- consensus communities generally assume that the network is entirely known and they try to detect all such consensus communities. In some cases, the network can be so large that each node can only have local information or one can be only interested in the "a -- consensus set of a particular node in the network. In this paper, we propose an efficient algorithm based on local optimizations to approximate the maximal "a -- consensus local community of a given node. The proposed method is evaluated experimentally on real and artificial complex networks in terms of quality, execution time and stability. It provides better results than the existing methods.