Hierarchy in directed random networks

One property of networks that has received comparatively little attention is hierarchy, i.e., the property of having vertices that cluster together in groups, which then join to form groups of groups, and so forth, up through all levels of organization in the network. Here, we give a precise definition of hierarchical structure, give a generic model for generating arbitrary hierarchical structure in a random graph, and describe a statistically principled way to learn the set ...

Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science. Recent studies suggest that networks often exhibit hierarchical organization, where vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases these groups are found to correspond to known functional units, such as ecological niches in food webs, modules in biochemical networks (...

A large number of complex systems, naturally emerging in various domains, are well described by directed networks, resulting in numerous interesting features that are absent from their undirected counterparts. Among these properties is a strong non-normality, inherited by a strong asymmetry that characterizes such systems and guides their underlying hierarchy. In this work, we consider an extensive collection of empirical networks and analyze their structural properties using...

Extracting understanding from the growing ``sea'' of biological and socio-economic data is one of the most pressing scientific challenges facing us. Here, we introduce and validate an unsupervised method that is able to accurately extract 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, incl...

The so-called rich-club phenomenon in a complex network is characterized when nodes of higher degree (hubs) are better connected among themselves than are nodes with smaller degree. The presence of the rich-club phenomenon may be an indicator of several interesting high-level network properties, such as tolerance to hub failures. Here we investigate the existence of the rich-club phenomenon across the hierarchical degrees of a number of real-world networks. Our simulations re...

Combinations of random and preferential growth for both on-growing and stationary networks are studied and a hierarchical topology is observed. Thus for real world scale-free networks which do not exhibit hierarchical features preferential growth is probably not the main ingredient in the growth process. An example of such real world networks includes the protein-protein interaction network in yeast, which exhibits pronounced anti-hierarchical features.

We suggest an approach to study hierarchy, especially hidden one, of complex networks based on the analysis of their vulnerability. Two quantities are proposed as a measure of network hierarchy. The first one is the system vulnerability V. We show that being quite suitable for regular networks this characteristic does not allow one to estimate the hierarchy of large random networks. The second quantity is a relative variance h of the system vulnerability that allows us to cha...

This book is concerned with the various aspects of hierarchical collective behaviour which is manifested by most complex systems in nature. From the many of the possible topics, we plan to present a selection of those that we think are useful from the point of shedding light from very different directions onto our quite general subject. Our intention is to both present the essential contributions by the existing approaches as well as go significantly beyond the results obtain...

In this paper, the class of random irregular block-hierarchical networks is defined and algorithms for generation and calculation of network properties are described. The algorithms presented for this class of networks are more efficient than known algorithms both in computation time and memory usage and can be used to analyze topological properties of such networks. The algorithms are implemented in the system created by the authors for the study of topological and statistic...

Trophic coherence, a measure of a graph's hierarchical organisation, has been shown to be linked to a graph's structural and dynamical aspects such as cyclicity, stability and normality. Trophic levels of vertices can reveal their functional properties and partition and rank the vertices accordingly. Yet trophic levels and hence trophic coherence can only be defined on graphs with basal vertices, vertices with zero in-degree. Consequently, trophic analysis of graphs had been ...