Hierarchy in directed random networks

The presence of hierarchy in many real-world networks is not yet fully explained. Complex interaction networks are often coarse-grain models of vast modular networks, where tightly connected subgraphs are agglomerated into nodes for simplicity of representation and feasibility of analysis. The emergence of hierarchy in growing complex networks may stem from one particular property of these ignored subgraphs: their graph conductance. Being a quantification of the main bottlene...

Real complex systems are not rigidly structured; no clear rules or blueprints exist for their construction. Yet, amidst their apparent randomness, complex structural properties universally emerge. We propose that an important class of complex systems can be modeled as an organization of many embedded levels (potentially infinite in number), all of them following the same universal growth principle known as preferential attachment. We give examples of such hierarchy in real sy...

Complex networks describe a wide range of systems in nature and society, much quoted examples including the cell, a network of chemicals linked by chemical reactions, or the Internet, a network of routers and computers connected by physical links. While traditionally these systems were modeled as random graphs, it is increasingly recognized that the topology and evolution of real networks is governed by robust organizing principles. Here we review the recent advances in the f...

This article addresses the degree distribution of subnetworks, namely the number of links between the nodes in each subnetwork and the remainder of the structure (cond-mat/0408076). The transformation from a subnetwork-partitioned model to a standard weighted network, as well as its inverse, are formalized. Such concepts are then considered in order to obtain scale free subnetworks through design or through a dynamics of node exchange. While the former approach allows the imm...

Network topology is a fundamental aspect of network science that allows us to gather insights into the complicated relational architectures of the world we inhabit. We provide a first specific study of neighbourhood degree sequences in complex networks. We consider how to explicitly characterise important physical concepts such as similarity, heterogeneity and organisation in these sequences, as well as updating the notion of hierarchical complexity to reflect previously unno...

Generative mechanisms which lead to empirically observed structure of networked systems from diverse fields like biology, technology and social sciences form a very important part of study of complex networks. The structure of many networked systems like biological cell, human society and World Wide Web markedly deviate from that of completely random networks indicating the presence of underlying processes. Often the main process involved in their evolution is the addition of...

A short review of the recent results and models of complex networks.

Analyzing and understanding the structure of complex relational data is important in many applications including analysis of the connectivity in the human brain. Such networks can have prominent patterns on different scales, calling for a hierarchically structured model. We propose two non-parametric Bayesian hierarchical network models based on Gibbs fragmentation tree priors, and demonstrate their ability to capture nested patterns in simulated networks. On real networks we...

The Erdos-Renyi classical random graph is characterized by a fixed linking probability for all pairs of vertices. Here, this concept is generalized by drawing the linking probability from a certain distribution. Such a procedure is found to lead to a static complex network with an arbitrary connectivity distribution. In particular, a scale-free network with the hierarchical organization is constructed without assuming any knowledge about the global linking structure, in contr...

We introduce appropriate definitions of dimensions in order to characterize the fractal properties of complex networks. We compute these dimensions in a hierarchically structured network of particular interest. In spite of the nontrivial character of this network that displays scale-free connectivity among other features, it turns out to be approximately one-dimensional. The dimensional characterization is in agreement with the results on statistics of site percolation and ot...