Vendredi 22 janvier 2016 à 11h, salle 26-00/332

**Abstract**

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.