Patricia Conde Céspedes
Vendredi 22 janvier 2016 à 11h, salle 26-00/332
Although the notion of community does not have a unanimous accepted definition, it is often related to a set of strongly interconnected nodes. Indeed, the density of links plays an important role because it measures the strength of the relationships in the community. The need of these well connected and dense communities has led to the notion of consensus community. An consensus community, is a group of nodes where each member is connected to more than a proportion of the other nodes. An consensus community is maximal if and only if adding a new node to the set breaks the rule. Consequently, an consensus community has a density greater than . Existing methods for mining consensus communities generally assume that the network is entirely known and they try to detect all such consensus communities. Detecting the local community of specific nodes is very important for applications dealing with huge networks, when iterating through all nodes would be impractical. In this paper, we propose an efficient algorithm, called RANK-NUM-NEIGHS (RNN), based on local optimizations to approximate the maximal 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. We also provide an upper bound on the optimal solution. The experiments show that It provides better results than the existing methods.