Community detection in attributed graphs

Christine Largeron, Laboratoire Hubert Curien, Université Jean Monnet, Saint-Etienne
Mardi 25 Avril 2017 à 11h, Salle 24-25/405, Campus Jussieu
A wide variety of applications require data modeled by a graph of interconnected nodes, known as social networks or information networks. When nodes are described by attributes, this is an attributed network. Examples of such networks are citation or collaboration networks or social media. One fundamental property of these networks is that they tend to naturally form communities and, many mining methods have been proposed to identify these communities but these methods are typically based solely on relationships between nodes in the graph. This is notably the case of Louvain, a greedy agglomerative clustering method which optimizes the modularity measure. Introduced by Newman, the modularity allows to estimate the quality of a partition but without taking into account the attributes associated with the nodes. For this reason, we have designed a complementary measure, based on inertia and specially conceived to evaluate the quality of a partition based on real attributes describing the vertices. We have also proposed I-Louvain, a method for community detection in attributed graphs where real attributes are associated with the vertices. Our experiments showed that combining the relational information with the attributes allows to detect the communities more efficiently with poor data.
This entry was posted in Events