e-Xploration

Many networks of interest in the sciences, including a variety of social and biological networks, are found to divide naturally into communities or modules. The problem of detecting and characterizing this community structure has attracted considerable recent attention. One of the most sensitive detection methods is optimization of the quality function known as “modularity” over the possible divisions of a network, but direct application of this method using, for instance, simulated annealing is computationally costly. Here we show that the modularity can be reformulated in terms of the eigenvectors of a new characteristic matrix for the network, which we call the modularity matrix, and that this reformulation leads to a spectral algorithm for community detection that returns results of better quality than competing methods in noticeably shorter running times. We demonstrate the algorithm with applications to several network data sets.

Example applications

In practice, the algorithm developed here gives excellent results. For a quantitative comparison between our algorithm and others we follow Duch and Arenas [19] and compare values of the modularity for a variety of
networks drawn from the literature. Results are shown in Table I for six different networks—the exact same six as used by Duch and Arenas. We compare modularity figures against three previously published algorithms: the betweenness-based algorithm of Girvan and Newman [10], which is widely used and has been incorporated into some of the more popular network analysis programs (denoted GN in the table); the fast algorithm of Clauset et al. [26] (CNM), which optimizes modularity using a greedy algorithm; and the extremal optimization algorithm of Duch and Arenas [19] (DA), which is arguably the best previously existing method, by standard
measures, if one discounts methods impractical for large networks, such as exhaustive enumeration of all partitions or simulated annealing.