An O(n2) algorithm for detecting communities of unbalanced sizes in large scale social networks

摘要

In the study of complex networks, a network is said to have community structure if it divides naturally into groups of nodes with dense connections within groups and only sparser connections between them [1]. Community structures are quite common in real networks. Social networks often include community groups based on common location, interests, occupation, etc. One of the most widely used methods for community detection is modularity maximization [2]. Modularity is a function that measures the quality of a particular division of a network into communities. But in [3], it is shown that communities that maximize the modularity are certainly groupings of smaller communities that need to be studied. In this work, we define a new function that qualifies a partition. We also present an algorithm that optimizes this function in order to find, within a reasonable time, the partition with the best measure of quality and which does not ignore small community.