Spectral properties of networks with community structure
Physical Review EPublished 24 November 2009
Sanjeev Chauhan, Michelle Girvan, Edward Ott
Citations137
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that in many cases, the spectrum of eigenvalues of the adjacency matrix of a network with community structure gives a clear indication of the number of communities in the network.
Abstract
In this paper, we discuss the eigenspectra of networks with community structure. It is shown that in many cases, the spectrum of eigenvalues of the adjacency matrix of a network with community structure gives a clear indication of the number of communities in the network. In particular, for a network with N nodes and N_(c) communities, there will typically be N_(c) eigenvalues that are significantly larger than the magnitudes of all the other (N-N_(c)) eigenvalues. We discuss this property as well as its use and limitations for determining N_(c) .
Keywords
MathematicsPhysics and Astronomy
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Proceedings of the National Academy of SciencesCommunity structure in social and biological networks
15,656 Citations2002Michelle Girvan, M. E. J. Newman
This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.
Proceedings of the National Academy of SciencesModularity and community structure in networks
12,281 Citations2006M. E. J. Newman
It is shown that the modularity of a network can be expressed in terms of the eigenvectors of a characteristic matrix for the network, which is called modularity matrix, and that this expression leads to a spectral algorithm for community detection that returns results of demonstrably higher quality than competing methods in shorter running times.
NatureFunctional cartography of complex metabolic networks
4,013 Citations2005Roger Guimerà, Luı́s A. Nunes Amaral
A methodology is proposed that can find functional modules in complex networks, and classify nodes into universal roles according to their pattern of intra- and inter-module connections, which yields a ‘cartographic representation’ of complex networks.
Journal of Statistical Mechanics Theory and ExperimentComparing community structure identification
2,877 Citations2005León Danon, Albert Dı́az-Guilera +2 more
It is found that the most accurate methods tend to be more computationally expensive, and that both aspects need to be considered when choosing a method for practical purposes.
Physica A Statistical Mechanics and its ApplicationsMean-field theory for scale-free random networks
2,251 Citations1999Albert-Ĺaszló Barabási, Réka Albert +1 more
A mean-field method is developed to predict the growth dynamics of the individual vertices of the scale-free model, and this is used to calculate analytically the connectivity distribution and the scaling exponents.
The European Physical Journal BDetecting community structure in networks
2,022 Citations2004M. E. J. Newman
A number of more recent algorithms that appear to work well with real-world network data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks are described.
Physical Review ECommunity detection in complex networks using extremal optimization
1,573 Citations2005Jordi Duch, Àlex Arenas
The method outperforms the optimal modularity found by the existing algorithms in the literature and is feasible to be used for the accurate identification of community structure in large complex networks.
Physica A Statistical Mechanics and its ApplicationsScale-free characteristics of random networks: the topology of the world-wide web
1,409 Citations2000Albert-Ĺaszló Barabási, Réka Albert +1 more
This work introduces a model that leads to a scale-free network, capturing in a minimal fashion the self-organization processes governing the world-wide web.
Physical Review LettersCommunity Structure in Directed Networks
1,144 Citations2008E. A. Leicht, M. E. J. Newman
This work describes an explicit algorithm based on spectral optimization of the modularity and shows that it gives demonstrably better results than previous methods on a variety of test networks, both real and computer generated.
The European Physical Journal BOn the properties of small-world network models
889 Citations2000Alain Barrat, Martin Weigt
Physical Review LettersSynchronization Reveals Topological Scales in Complex Networks
854 Citations2006Àlex Arenas, Albert Dı́az-Guilera +1 more
The analysis is based on the full dynamics towards synchronization of a system of coupled oscillators and provides a useful connection between synchronization dynamics, complex networks topology, and spectral graph analysis.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpectra of “real-world” graphs: Beyond the semicircle law
481 Citations2001Illés J. Farkas, Imre Derényi +2 more
Methods to determine the eigenvalues of networks comparable in size to real systems are developed, obtaining several surprising results on the spectra of adjacency matrices corresponding to models of real-world graphs.
Journal of Statistical Mechanics Theory and ExperimentDetecting network communities: a new systematic and efficient algorithm
364 Citations2004Luca Donetti, Miguel A Muñoz
Physica A Statistical Mechanics and its ApplicationsDetecting communities in large networks
331 Citations2005Andrea Capocci, Vito D. P. Servedio +2 more
An algorithm to detect community structure in complex networks based on spectral methods and takes into account weights and link orientation is developed, which proves to be successful both in clustering words, and in uncovering mental association patterns.
Physical Review LettersCharacterizing the Dynamical Importance of Network Nodes and Links
260 Citations2006Juan G. Restrepo, Edward Ott +1 more
It is shown how the characterization of the dynamical importance of nodes can be affected by degree-degree correlations and network community structure, and how this can be used to optimize techniques for controlling certain network dynamical processes.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsSpectra and eigenvectors of scale-free networks
241 Citations2001K.-I. Goh, B. Kahng +1 more
The spectral density shows an exponential decay around the center, followed by power-law long tails at both spectrum edges, and the mass gap scales as N(-0.68) and the component of the normalized eigenfunction at the hub is of order unity.
SIAM ReviewThe Many Proofs and Applications of Perron’s Theorem
201 Citations2000C. R. MacCluer
The many proofs given during the last 93 years are categorized and critiqued (including Perron's original two proofs, and a more natural proof) and this simple-to-understand result of Perron is presented.
Physical Review EApproximating the largest eigenvalue of network adjacency matrices
148 Citations2007Juan G. Restrepo, Edward Ott +1 more
Approximations to the largest eigenvalue of adjacency matrices of a network are developed and the relationships between these approximations are discussed.
Journal of Statistical PhysicsRandom Incidence Matrices: Moments of the Spectral Density
110 Citations2001M. Bauer, O. Golinelli
Two algorithms to compute the moments of the eigenvalue distribution as explicit polynomials in N and p are given and it is shown that the spectrum always contains a discrete component.
New Journal of PhysicsDynamical and spectral properties of complex networks
95 Citations2007Juan A Almendral, Albert Díaz-Guilera
The main dependence of the synchronization time is on the smallest nonzero eigenvalue of the Laplacian matrix, in contrast to other proposals in terms of the spectrum of the adjacency matrix.
Random incidence matrices: moments of the spectral density
93 Citations2001M. Bauer, O. Golinelli