Extracting the hierarchical organization of complex systems

By Marta Sales-Pardo, Roger Guimerà, André A. Moreira, Luís A. Nunes Amaral. Proceedings of the National Academy of Sciences of the United States of America, 2007

572 citations recorded by the source corpus.

Extracting understanding from the growing “sea” of biological and socioeconomic data is one of the most pressing scientific challenges facing us. Here, we introduce and validate an unsupervised method for extracting the hierarchical organization of complex biological, social, and technological networks. We define an ensemble of hierarchically nested random graphs, which we use to validate the method. We then apply our method to real-world networks, including the air-transportation network, an electronic circuit, an e-mail exchange network, and metabolic networks. Our analysis of model and real networks demonstrates that our method extracts an accurate multiscale representation of a complex system.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

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

How researchers see this paper

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

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Inferring gene ontologies from pairwise similarity data (2014, background): “…algorithms which construct hierarchies with overlapping clusters, by creating a first level of overlapping clusters with terminal nodes and then combining these base clusters into higher level clusters (Becker et al ., 2012; Kovacs et al ., 2010; Kumpula et al ., 2008; Sales-Pardo et al ., 2007).”
Age-related changes in modular organization of human brain functional networks (2009, unknown): “Once a maximally modular partition of the network has been identified, it is possible to assign topological roles to each node based on its density of intra- and inter-modular connections (Guimerà et al., 2005; Guimerà and Amaral, 2005a,b; Sales-Pardo et al., 2007).”
Modularity-maximizing graph communities via mathematical programming (2007, background): “Despite multiple recently proposed hierarchical clustering algorithms (e.g., [18, 37, 41]), there is far from general agreement on what objective functions would capture a “good” hierarchical clustering.”
Comparing Community Structure to Characteristics in Online Collegiate Social Networks (2008, background): “Such research has generated numerous important insights on the effects of network topology on individuals’ behavior, including collaborations [41,69], community formation [21,28], and hierarchical and modular organization [88, 92 ].”
Link Prediction in Complex Networks: A Survey (2010, background): “Empirical evidence indicates that many real networks are hierarchically organized, where nodes can be divided into groups, further subdivided into groups of groups, and so forth over multiple scales [21] (e.”
Development of Large-Scale Functional Brain Networks in Children (2009, background): “Hierarchical organization has been discovered in the World Wide Web and several biological networks [40,58,59].”
A Poissonian explanation for heavy tails in e-mail communication (2008, background): “The re may be a common explanation for these apparent power-laws: c omplex systems are inherently hierarchical but the distinct l evels in the hierarchy are difficult to distinguish [41].”
Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems (2010, background): “(10) At the finest levels, nodes rather than submodules are visited and the relative rate of codeword use is P = q y /p ij.”
Redrawing the Map of Great Britain from a Network of Human Interactions (2010, background): “As it has been shown [13,27], a modularity function such as ours is likely to have exponentially many local maxima, and these maxima typically have different clustered structures.”
Uncovering space-independent communities in spatial networks (2010, methodology): “These methods have been shown to produce useful and relevant partitions in a broad class of systems [31], even if modularity suﬀers from limitations such as resolution limit [65] and a possible high degeneracy of its landscape [66, 67].”
Efficient Physical Embedding of Topologically Complex Information Processing Networks in Brains and Computer Circuits (2010, methodology): “Insets The inset panels give a visual depiction of the hierarchical modularity of each system, which has been represented by a coclassification matrix where red/brown colors highlight modules or clusters of nodes with high local interconnectivity and relatively sparse connectivity to nodes in other ”
Kronecker Graphs: An Approach to Modeling Networks (2008, background): “, 2002; Ravasz and Barabási, 2003) and algorithms to extract the network hierarchical structure have also been developed (Sales-Pardo et al., 2007; Clauset et al., 2008).”