Community detection in complex networks using extremal optimization.

By Jordi Duch, Alex Arenas. Physical review. E, Statistical, nonlinear, and soft matter physics, 2005

1,542 citations recorded by the source corpus.

We propose a method to find the community structure in complex networks based on an extremal optimization of the value of modularity. The method outperforms the optimal modularity found by the existing algorithms in the literature giving a better understanding of the community structure. We present the results of the algorithm for computer-simulated and real networks and compare them with other approaches. The efficiency and accuracy of the method make it feasible to be used for the accurate identification of community structure in large complex networks.

Subfields: Experimental and Cognitive Psychology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/f7b7e9e7f9b5dacc744e8d08c2c32b810533f588

How researchers see this paper

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

In Experimental and Cognitive Psychology

In Statistical and Nonlinear Physics

Citations in the corpus

Robustness of community structure in networks. (2007, methodology): “Perhaps the most widely used technique, however, is the maximization of the benefit function known as modularity [5, 15, 16, 17, 18, 19, 20, 21], which is (to within a multiplicative constant) the difference between the number of edges within communities and the expected number of such edges under a”
Community detection in graphs (2009, methodology): “Interestingly, Arenas et al. found that the structural scales revealed by synchronization correspond to groups of eigenvalues of the Laplacian matrix of the graph, separated by gaps (Fig.”
A smart local moving algorithm for large-scale modularity-based community detection (2013, positive): “…& Moore, 2004; Newman, 2004a), simulated annealing (Guimerà, Sales-Pardo, & Amaral, 2004; Reichardt & Bornholdt, 2006), extremal optimization (Duch & Arenas, 2005), spectral optimization (Newman, 2006a, 2006b), mean field annealing (Lehmann & Hansen, 2007), and conformational space annealing…”
Communities in Networks (2009, methodology): “Other methods— such as spectral partitioning [77,78] (discussed below), refined greedy algorithms [100], simulated annealing [45], extremal optimization [27], and others [84]—provide more sophisticated but slower means to identify high-modularity partitions.”
Modular Brain Networks (2015, methodology): “These methods include divisive algorithms (Girvan & Newman 2002), spectral decomposition (Newman 2004), extremal optimization (Duch & Arenas 2005), greedy algorithms (Blondel et al. 2008, Clauset et al. 2004), and simulated annealing (Guimera & Amaral 2005), among others.”
Toward link predictability of complex networks (2015, background): “We consider the following 10 real-world networks drawn from disparate fields: ( i ) Jazz (37), a collaboration network of jazz musicians consists of 198 nodes and 2742 interactions; ( ii ) Metabolic (38), the metabolic network of Caenorhabditis elegans ; ( iii ) Neural (32), the neural network of C.”
Community Structure in Graphs (2007, methodology): “This technique was used for modularity optimization by Duch and Arenas [53].”
The Ubiquity of Small-World Networks (2011, methodology): “29 Caenorhabditis elegans (metabolic) (Duch and Arenas, 2005) 453 8.”
Comparing community structure identification (2005, methodology): “ high values of Q quickly. In case of large networks it requires less computer memory than the other presented, since it doesn’t need extra data structures. 6.3 Extremal optimisation In this approach [38], an heuristic search procedure based on extremal optimisation [39] is used to ﬁnd the network c”
Modularity and community structure in networks. (2006, methodology): “In this section I describe briefly another method for dividing networks in two by modularity optimization, which is entirely different from the spectral method.”
Detect overlapping and hierarchical community structure in networks (2008, methodology): “Several community detection methods have been proposed by optimizing modularity [11, 14, 15].”
Generalized Louvain method for community detection in large networks (2011, methodology): “Several variants of this strategy have been proposed during the years, such as the fast clustering algorithm provided by Clauset, Newman and Moore [11], that runs in O(n log n) on sparse graphs; the extremal optimization method proposed by Duch and Arenas [12], based on a fast agglomerative approach”
From Louvain to Leiden: guaranteeing well-connected communities (2018, methodology): “Optimising modularity is NP-hard 5 , and consequentially many heuristic algorithms have been proposed, such as hierarchical agglomeration 6 , extremal optimisation 7 , simulated annealing 4,8 and spectral 9 algorithms.”