Advances in Data Science

8Attributed Networks Partitioning Based on Modularity Optimization

We have proposed I-Louvain, a method for clustering graph nodes, which uses a criterion based on inertia combined with Newman’s modularity: it can detect communities in attributed graphs where real attributes are associated to vertices. In this chapter, we demonstrate that the optimization of this global criterion can be done at the local level, ensuring execution speed. So, like in the famous Louvain algorithm, the global modularity of a new partition can be quickly updated in our I-Louvain algorithm. Our experiments on synthetic datasets show that this method is able to handle reasonably large-sized networks and that combining the relational information with the attributes may allow the detection of communities more efficiently than using only one type of information.

8.1. Introduction

Community detection deals with the unsupervised clustering of graph vertices in social networks. Each vertex represents, for instance, a person, and the graph structure models the social relations between people. There is a link between the two nodes of the graph if the corresponding persons have social interaction. The particular signification of this social interaction depends on the social network: it could be an observed relation (using e.g. proximity sensors or logs of emails) or the users themselves can declare a “friendship” relation between them. The goal is then to partition the vertices of the graph into the so-called ...