Size reduction of complex networks preserving modularity

By Alex Arenas, Jordi Duch, Alberto Fernández, Sergio Gómez. arXiv.org, 2007

332 citations recorded by the source corpus.

The ubiquity of modular structure in real-world complex networks is the focus of attention in many trials to understand the interplay between network topology and functionality. The best approaches to the identification of modular structure are based on the optimization of a quality function known as modularity. However this optimization is a hard task provided that the computational complexity of the problem is in the non-deterministic polynomial-time hard (NP-hard) class. Here we propose an exact method for reducing the size of weighted (directed and undirected) complex networks while maintaining their modularity. This size reduction allows use of heuristic algorithms that optimize modularity for a better exploration of the modularity landscape. We compare the modularity obtained in several real complex-networks by using the extremal optimization algorithm, before and after the size reduction, showing the improvement obtained. We speculate that the proposed analytical size reduction could be extended to an exact coarse graining of the network in the scope of real-space renormalization.

Subfields: Computational Theory and Mathematics, Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/99bdacafca008d577079f151e9bb31050fc4c9de

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in Social Media (2012, background): “Extremal optimization (Arenas et al. 2007) O(n2 log n) O(n2 log n) M”
Extending the definition of modularity to directed graphs with overlapping communities (2008, background): “Initially deﬁned for undirect networks, the deﬁnition of modularity has been subsequently extended to capture community structure in directed networks ([9], [1], [12]).”
Community structure in directed networks. (2007, background): “Several previous studies, including our own, have touched on this problem in the context of other analyses of directed network data [6, 7, 8, 9], but they have typically not tackled the community structure problem directly.”
Multilayer networks (2013, background): “[12] that reduces the size of a network by grouping nodes such that the reduced network does not change the optimal partition and the modularity values of all of the partitions of the reduced network are the same as the corresponding partitions in the original network.”
A classification for community discovery methods in complex networks (2011, background): “A number of other optimization strategies have been proposed (size reduction [95], simulated annealing [96]).”
Motif-based communities in complex networks (2007, neutral): “In this work we start from an extension of modularity to weighted directed networks [14], which reduces to the previous one for undirected networks, and which is calculated as follows: where w ij is the weight of the connection from the i th to the j th node, w out i = j w ij and w in j = P i w ij…”
Redrawing the Map of Great Britain from a Network of Human Interactions (2010, background): “Note that it was important to include loop edges (as proposed in [19]) in our analysis as it allowed us to correctly represent the human network from which we started (see Text S2).”
A smart local moving algorithm for large-scale modularity-based community detection (2013, background): “At this point, a reduced network is constructed (Arenas, Duch, Fernández, & Gómez, 2007).”
Community Structure in Graphs (2007, background): “Modularity also allows to assess the stability of partitions [29] and to transform a graph into a smaller one by preserving its community structure [30].”
Community detection in graphs (2009, methodology): “If a graph is both directed and weighted, formulas 35 and 37 can be combined as Qgen = 1 W ∑ ij ( Wij − souti s in j W ) δ(Ci, Cj), (38) which is the most general (available) expression of modularity (Arenas et al., 2007).”
Robustness of community structure in networks. (2007, background): “Communities can also be used as a basis for the reduction or coarse-graining of networks for visualization or other purposes [5, 6].”
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, background): “For instance, although it has been argued [64], [65] that the null configuration model in modularity should become dind T out=2m in order to account for the directionality of the links, this choice and justification of the null model for directed graphs is not unique.”
Clustering and Community Detection in Directed Networks: A Survey (2013, methodology): “In the case of quality measures, typically the directed version of modularity [58, 50] is applied to quantify the significance of a partition, while for benchmarking purposes some very recent benchmarks are reviewed.”
Detecting communities of triangles in complex networks using spectral optimization (2010, background): “The mathematical formulation of modularity was proposed fo r unweighed and undirected networks [5] and generalized later to weighted [6] and direc ted networks [21].”