ID: 1208.6255

Hierarchy in directed random networks

August 30, 2012

View on ArXiv
Enys Mones
Physics
Condensed Matter
Computer Science
Physics and Society
Statistical Mechanics
Social and Information Netwo...
Data Analysis, Statistics an...

In recent years, the theory and application of complex networks have been quickly developing in a markable way due to the increasing amount of data from real systems and to the fruitful application of powerful methods used in statistical physics. Many important characteristics of social or biological systems can be described by the study of their underlying structure of interactions. Hierarchy is one of these features that can be formulated in the language of networks. In this paper we present some (qualitative) analytic results on the hierarchical properties of random network models with zero correlations and also investigate, mainly numerically, the effects of different type of correlations. The behavior of hierarchy is different in the absence and the presence of the giant components. We show that the hierarchical structure can be drastically different if there are one-point correlations in the network. We also show numerical results suggesting that hierarchy does not change monotonously with the correlations and there is an optimal level of non-zero correlations maximizing the level of hierarchy.

Similar papers 1

Hierarchy Measures in Complex Networks

August 18, 2003

93% Match
Ala Trusina, Sergei Maslov, ... , Sneppen Kim
Soft Condensed Matter
Molecular Networks

Using each node's degree as a proxy for its importance, the topological hierarchy of a complex network is introduced and quantified. We propose a simple dynamical process used to construct networks which are either maximally or minimally hierarchical. Comparison with these extremal cases as well as with random scale-free networks allows us to better understand hierarchical versus modular features in several real-life complex networks. For random scale-free topologies the exte...

Find SimilarView on arXiv

Hierarchical Organization in Complex Networks

June 9, 2002

90% Match
Erzsebet Ravasz, Albert-Laszlo Barabasi
Statistical Mechanics
Soft Condensed Matter

Many real networks in nature and society share two generic properties: they are scale-free and they display a high degree of clustering. We show that these two features are the consequence of a hierarchical organization, implying that small groups of nodes organize in a hierarchical manner into increasingly large groups, while maintaining a scale-free topology. In hierarchical networks the degree of clustering characterizing the different groups follows a strict scaling law, ...

Find SimilarView on arXiv

Interplay Between Hierarchy and Centrality in Complex Networks

March 2, 2021

90% Match
Stephany Rajeh, Marinette Savonnet, ... , Cherifi Hocine
Social and Information Netwo...

Hierarchy and centrality are two popular notions used to characterize the importance of entities in complex systems. Indeed, many complex systems exhibit a natural hierarchical structure, and centrality is a fundamental characteristic allowing to identify key constituents. Several measures based on various aspects of network topology have been proposed in order to quantify these concepts. While numerous studies have investigated whether centrality measures convey redundant in...

Find SimilarView on arXiv

The Dynamics of Hierarchical Evolution of Complex Networks

April 13, 2005

90% Match
Matheus Palhares Viana, Luciano da Fontoura Costa
Statistical Mechanics

Introduced recently, the concept of hierarchical degree allows a more complete characterization of the topological context of a node in a complex network than the traditional node degree. This article presents analytical characterization and studies of the density of hierarchical degrees in random and scale free networks. The obtained results allowed the identification of a hierarchy-dependent power law for the degrees of nodes in random complex networks, with Poisson density...

Find SimilarView on arXiv

Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?

August 31, 2015

90% Match
Dániel Czégel, Gergely Palla
Physics and Society

Signs of hierarchy are prevalent in a wide range of systems in nature and society. One of the key problems is quantifying the importance of hierarchical organisation in the structure of the network representing the interactions or connections between the fundamental units of the studied system. Although a number of notable methods are already available, their vast majority is treating all directed acyclic graphs as already maximally hierarchical. Here we propose a hierarchy m...

Find SimilarView on arXiv

On the Origins of Hierarchy in Complex Networks

March 11, 2013

90% Match
Bernat Corominas-Murtra, Joaquín Goñi, ... , Rodríguez-Caso Carlos
Physics and Society
Statistical Mechanics

Hierarchy seems to pervade complexity in both living and artificial systems. Despite its relevance, no general theory that captures all features of hierarchy and its origins has been proposed yet. Here we present a formal approach resulting from the convergence of theoretical morphology and network theory that allows constructing a 3D morphospace of hierarchies and hence comparing the hierarchical organization of ecological, cellular, technological and social networks. Embedd...

Find SimilarView on arXiv

Hierarchical characterization of complex networks

December 30, 2004

90% Match
Luciano da Fontoura Costa, Filipi Nascimento Silva
Statistical Mechanics
Disordered Systems and Neura...
Computational Physics
Quantitative Methods

While the majority of approaches to the characterization of complex networks has relied on measurements considering only the immediate neighborhood of each network node, valuable information about the network topological properties can be obtained by considering further neighborhoods. The current work discusses on how the concepts of hierarchical node degree and hierarchical clustering coefficient (introduced in cond-mat/0408076), complemented by new hierarchical measurements...

Find SimilarView on arXiv

Hierarchical Cutting of Complex Networks Performed by Random Walks

March 11, 2024

89% Match
Alexandre Benatti, Luciano da F. Costa
Social and Information Netwo...
Physics and Society

Several interesting approaches have been reported in the literature on complex networks, random walks, and hierarchy of graphs. While many of these works perform random walks on stable, fixed networks, in the present work we address the situation in which the connections traversed by each step of a uniformly random walks are progressively removed, yielding a successively less interconnected structure that may break into two components, therefore establishing a respective hier...

Find SimilarView on arXiv

Statistical Complexity of Heterogeneous Geometric Networks

October 31, 2023

89% Match
Keith Malcolm Smith, Jason P. Smith
Social and Information Netwo...

Heterogeneity and geometry are key explanatory components underlying the structure of real-world networks. The relationship between these components and the statistical complexity of networks is not well understood. We introduce a parsimonious normalised measure of statistical complexity for networks -- normalised hierarchical complexity. The measure is trivially 0 in regular graphs and we prove that this measure tends to 0 in Erd\"os-R\'enyi random graphs in the thermodynami...

Find SimilarView on arXiv

Hierarchy measure for complex networks

February 1, 2012

89% Match
Enys Mones, Lilla Vicsek, Tamás Vicsek
Physics and Society
Disordered Systems and Neura...
Statistical Mechanics
Social and Information Netwo...

Nature, technology and society are full of complexity arising from the intricate web of the interactions among the units of the related systems (e.g., proteins, computers, people). Consequently, one of the most successful recent approaches to capturing the fundamental features of the structure and dynamics of complex systems has been the investigation of the networks associated with the above units (nodes) together with their relations (edges). Most complex systems have an in...

Find SimilarView on arXiv