MEP — A robust algorithm for detecting communities in large scale social networks

Social networks can be modeled by graphs whose vertices represent the actors of the social phenomenon and the edges represent the interactions between them. An important element in the automatic analysis of social networks is the discovery of “communities”. A community is simply a group of people strongly connected. The detection of communities in social networks is equivalent to partitioning the graph representing the network. Among the methods to solve this problem, there are those that consist in defining a function that associates a quality index to any partition graph. In this case, the graph partitioning algorithm aims at optimizing this function. In this work, we define a new function that qualifies a partition and we present an algorithm that optimizes this function in order to find, within a reasonable time, the partition with the best measure of quality.