Hierarchy measure for complex networks

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 inherently hierarchical organization and, correspondingly, the networks behind them also exhibit hierarchical features. Indeed, several papers have been devoted to describing this essential aspect of networks, however, without resulting in a widely accepted, converging concept concerning the quantitative characterization of the level of their hierarchy. Here we develop an approach and propose a quantity (measure) which is simple enough to be widely applicable, reveals a number of universal features of the organization of real-world networks and, as we demonstrate, is capable of capturing the essential features of the structure and the degree of hierarchy in a complex network. The measure we introduce is based on a generalization of the m-reach centrality, which we first extend to directed/partially directed graphs. Then, we define the global reaching centrality (GRC), which is the difference between the maximum and the average value of the generalized reach centralities over the network. We investigate the behavior of the GRC considering both a synthetic model with an adjustable level of hierarchy and real networks. Results for real networks show that our hierarchy measure is related to the controllability of the given system. We also propose a visualization procedure for large complex networks that can be used to obtain an overall qualitative picture about the nature of their hierarchical structure.     

The complex structure of hunter-gatherer social networks

In nature, many different types of complex system form hierarchical, self-similar or fractal-like structures that have evolved to maximize internal efficiency. In this paper, we ask whether hunter-gatherer societies show similar structural properties. We use fractal network theory to analyse the statistical structure of 1189 social groups in 339 hunter-gatherer societies from a published compilation of ethnographies. We show that population structure is indeed self-similar or fractal-like with the number of individuals or groups belonging to each successively higher level of organization exhibiting a constant ratio close to 4. Further, despite the wide ecological, cultural and historical diversity of hunter-gatherer societies, this remarkable self-similarity holds both within and across cultures and continents. We show that the branching ratio is related to density-dependent reproduction in complex environments and hypothesize that the general pattern of hierarchical organization reflects the self-similar properties of the networks and the underlying cohesive and disruptive forces that govern the flow of material resources, genes and non-genetic information within and between social groups. Our results offer insight into the energetics of human sociality and suggest that human social networks self-organize in response to similar optimization principles found behind the formation of many complex systems in nature.     

Multilayer network analyses as a toolkit for measuring social structure

The formalization of multilayer networks allows for new ways to measure sociality in complex social systems,including groups of animals.The same mathematical representation and methods are widely applicable across fields and study systems,and a network can represent drastically different types of data.As such,in order to apply analyses and interpret the results in a meaningful way the researcher must have a deep understanding of what their network is representing and what parts of it are being measured by a given analysis.Multilayer social networks can represent social structure with more detail than is often present in single layer networks,including multiple"types"of individuals,interactions,or relationships,and the extent to which these types are interdependent.Multilayer networks can also encompass a wider range of social scales,which can help overcome complications that are inherent to measuring sociality.In this paper,I dissect multilayer networks into the parts that correspond to different components of social structures.I then discuss common pitfalls to avoid across different stages of multilayer network analyses-some novel and some that always exist in social network analysis but are magnified in multi-layer representations.This paper serves as a primer for building a customized toolkit of multilayer network analyses,to probe components of social structure in animal social systems.     

Emergence of complex social networks from spatial structure and rules of thumb: a modelling approach

Individual-based computer models show that simple heuristic governing individuals’ behavior may suffice to generate complex patterns of social behavior at the group level such as those observed in animal societies. ‘GrooFiWorld’ is an example of such kind of computer models. In this model, self-organization and simple behavioral rules generate complex patterns of social behavior like those described in tolerant and intolerant societies of macaques. Social complexity results from the socio-spatial structure of the group, the nature of which is, in turn, a side-effect of intensity of aggression. The model suggests that a similar mechanism may give rise to complex social structures in macaques. It is, however, unknown if the spatial structure of the model and that of macaques are indeed similar. Here we used social networks analysis as a proxy for spatial structure of the group. Our findings show that the social networks of the model share similar qualitative features with those of macaques. As group size increases, the density and the average individual eigenvector centrality decrease and the modularity and centralization of the network increase. In social networks emerging from simulations resembling intolerant societies the density is lower, the modularity and centralization are higher, and the individuals ranking higher in the dominance hierarchy are more central than in the social networks emerging from simulations resembling egalitarian societies. Given the qualitative similarity between the social networks of the model and that of empirical data, our results suggest that the spatial structure of macaques is similar to that of the model. It seems thus plausible that, as in the model, the spatial structure combined with simple behavioral rules plays a role in the emergence of complex social networks and complex social behavior in macaques.     

De Novo Evolution of Complex, Global and Hierarchical Gene Regulatory Mechanisms

Gene regulatory networks exhibit complex, hierarchical features such as global regulation and network motifs. There is much debate about whether the evolutionary origins of such features are the results of adaptation, or the by-products of non-adaptive processes of DNA replication. The lack of availability of gene regulatory networks of ancestor species on evolutionary timescales makes this a particularly difficult problem to resolve. Digital organisms, however, can be used to provide a complete evolutionary record of lineages. We use a biologically realistic evolutionary model that includes gene expression, regulation, metabolism and biosynthesis, to investigate the evolution of complex function in gene regulatory networks. We discover that: (i) network architecture and complexity evolve in response to environmental complexity, (ii) global gene regulation is selected for in complex environments, (iii) complex, inter-connected, hierarchical structures evolve in stages, with energy regulation preceding stress responses, and stress responses preceding growth rate adaptations and (iv) robustness of evolved models to mutations depends on hierarchical level: energy regulation and stress responses tend not to be robust to mutations, whereas growth rate adaptations are more robust and non-lethal when mutated. These results highlight the adaptive and incremental evolution of complex biological networks, and the value and potential of studying realistic in silico evolutionary systems as a way of understanding living systems.     

Offspring social network structure predicts fitness in families

Social structures such as families emerge as outcomes of behavioural interactions among individuals, and can evolve over time if families with particular types of social structures tend to leave more individuals in subsequent generations. The social behaviour of interacting individuals is typically analysed as a series of multiple dyadic (pair-wise) interactions, rather than a network of interactions among multiple individuals. However, in species where parents feed dependant young, interactions within families nearly always involve more than two individuals simultaneously. Such social networks of interactions at least partly reflect conflicts of interest over the provision of costly parental investment. Consequently, variation in family network structure reflects variation in how conflicts of interest are resolved among family members. Despite its importance in understanding the evolution of emergent properties of social organization such as family life and cooperation, nothing is currently known about how selection acts on the structure of social networks. Here, we show that the social network structure of broods of begging nestling great tits Parus major predicts fitness in families. Although selection at the level of the individual favours large nestlings, selection at the level of the kin-group primarily favours families that resolve conflicts most effectively.     

HiNO: an approach for inferring hierarchical organization from regulatory networks

Background

Gene expression as governed by the interplay of the components of regulatory networks is indeed one of the most complex fundamental processes in biological systems. Although several methods have been published to unravel the hierarchical structure of regulatory networks, weaknesses such as the incorrect or inconsistent assignment of elements to their hierarchical levels, the incapability to cope with cyclic dependencies within the networks or the need for a manual curation to retrieve non-overlapping levels remain unsolved.

Methodology/Results

We developed HiNO as a significant improvement of the so-called breadth-first-search (BFS) method. While BFS is capable of determining the overall hierarchical structures from gene regulatory networks, it especially has problems solving feed-forward type of loops leading to conflicts within the level assignments. We resolved these problems by adding a recursive correction approach consisting of two steps. First each vertex is placed on the lowest level that this vertex and its regulating vertices are assigned to (downgrade procedure). Second, vertices are assigned to the next higher level (upgrade procedure) if they have successors with the same level assignment and have themselves no regulators. We evaluated HiNO by comparing it with the BFS method by applying them to the regulatory networks from Saccharomyces cerevisiae and Escherichia coli, respectively. The comparison shows clearly how conflicts in level assignment are resolved in HiNO in order to produce correct hierarchical structures even on the local levels in an automated fashion.

Conclusions

We showed that the resolution of conflicting assignments clearly improves the BFS-method. While we restricted our analysis to gene regulatory networks, our approach is suitable to deal with any directed hierarchical networks structure such as the interaction of microRNAs or the action of non-coding RNAs in general. Furthermore we provide a user-friendly web-interface for HiNO that enables the extraction of the hierarchical structure of any directed regulatory network.

Availability

HiNO is freely accessible at http://mips.helmholtz-muenchen.de/hino/.     

Organization of excitable dynamics in hierarchical biological networks

This study investigates the contributions of network topology features to the dynamic behavior of hierarchically organized excitable networks. Representatives of different types of hierarchical networks as well as two biological neural networks are explored with a three-state model of node activation for systematically varying levels of random background network stimulation. The results demonstrate that two principal topological aspects of hierarchical networks, node centrality and network modularity, correlate with the network activity patterns at different levels of spontaneous network activation. The approach also shows that the dynamic behavior of the cerebral cortical systems network in the cat is dominated by the network's modular organization, while the activation behavior of the cellular neuronal network of Caenorhabditis elegans is strongly influenced by hub nodes. These findings indicate the interaction of multiple topological features and dynamic states in the function of complex biological networks.     

An Adaptive Complex Network Model for Brain Functional Networks

Brain functional networks are graph representations of activity in the brain, where the vertices represent anatomical regions and the edges their functional connectivity. These networks present a robust small world topological structure, characterized by highly integrated modules connected sparsely by long range links. Recent studies showed that other topological properties such as the degree distribution and the presence (or absence) of a hierarchical structure are not robust, and show different intriguing behaviors. In order to understand the basic ingredients necessary for the emergence of these complex network structures we present an adaptive complex network model for human brain functional networks. The microscopic units of the model are dynamical nodes that represent active regions of the brain, whose interaction gives rise to complex network structures. The links between the nodes are chosen following an adaptive algorithm that establishes connections between dynamical elements with similar internal states. We show that the model is able to describe topological characteristics of human brain networks obtained from functional magnetic resonance imaging studies. In particular, when the dynamical rules of the model allow for integrated processing over the entire network scale-free non-hierarchical networks with well defined communities emerge. On the other hand, when the dynamical rules restrict the information to a local neighborhood, communities cluster together into larger ones, giving rise to a hierarchical structure, with a truncated power law degree distribution.     

Living in the branches: population dynamics and ecological processes in dendritic networks

Spatial structure regulates and modifies processes at several levels of ecological organization (e.g. individual/genetic, population and community) and is thus a key component of complex systems, where knowledge at a small scale can be insufficient for understanding system behaviour at a larger scale. Recent syntheses outline potential applications of network theory to ecological systems, but do not address the implications of physical structure for network dynamics. There is a specific need to examine how dendritic habitat structure, such as that found in stream, hedgerow and cave networks, influences ecological processes. Although dendritic networks are one type of ecological network, they are distinguished by two fundamental characteristics: (1) both the branches and the nodes serve as habitat, and (2) the specific spatial arrangement and hierarchical organization of these elements interacts with a species' movement behaviour to alter patterns of population distribution and abundance, and community interactions. Here, we summarize existing theory relating to ecological dynamics in dendritic networks, review empirical studies examining the population- and community-level consequences of these networks, and suggest future research integrating spatial pattern and processes in dendritic systems.     

Evolution of Cooperation on Stochastic Dynamical Networks

Cooperative behavior that increases the fitness of others at a cost to oneself can be promoted by natural selection only in the presence of an additional mechanism. One such mechanism is based on population structure, which can lead to clustering of cooperating agents. Recently, the focus has turned to complex dynamical population structures such as social networks, where the nodes represent individuals and links represent social relationships. We investigate how the dynamics of a social network can change the level of cooperation in the network. Individuals either update their strategies by imitating their partners or adjust their social ties. For the dynamics of the network structure, a random link is selected and breaks with a probability determined by the adjacent individuals. Once it is broken, a new one is established. This linking dynamics can be conveniently characterized by a Markov chain in the configuration space of an ever-changing network of interacting agents. Our model can be analytically solved provided the dynamics of links proceeds much faster than the dynamics of strategies. This leads to a simple rule for the evolution of cooperation: The more fragile links between cooperating players and non-cooperating players are (or the more robust links between cooperators are), the more likely cooperation prevails. Our approach may pave the way for analytically investigating coevolution of strategy and structure.     

Statecharts for Gene Network Modeling

State diagrams (stategraphs) are suitable for describing the behavior of dynamic systems. However, when they are used to model large and complex systems, determining the states and transitions among them can be overwhelming, due to their flat, unstratified structure. In this article, we present the use of statecharts as a novel way of modeling complex gene networks. Statecharts extend conventional state diagrams with features such as nested hierarchy, recursion, and concurrency. These features are commonly utilized in engineering for designing complex systems and can enable us to model complex gene networks in an efficient and systematic way. We modeled five key gene network motifs, simple regulation, autoregulation, feed-forward loop, single-input module, and dense overlapping regulon, using statecharts. Specifically, utilizing nested hierarchy and recursion, we were able to model a complex interlocked feed-forward loop network in a highly structured way, demonstrating the potential of our approach for modeling large and complex gene networks.     

Modes of Interaction between Individuals Dominate the Topologies of Real World Networks

We find that the topologies of real world networks, such as those formed within human societies, by the Internet, or among cellular proteins, are dominated by the mode of the interactions considered among the individuals. Specifically, a major dichotomy in previously studied networks arises from modeling networks in terms of pairwise versus group tasks. The former often intrinsically give rise to scale-free, disassortative, hierarchical networks, whereas the latter often give rise to single- or broad-scale, assortative, nonhierarchical networks. These dependencies explain contrasting observations among previous topological analyses of real world complex systems. We also observe this trend in systems with natural hierarchies, in which alternate representations of the same networks, but which capture different levels of the hierarchy, manifest these signature topological differences. For example, in both the Internet and cellular proteomes, networks of lower-level system components (routers within domains or proteins within biological processes) are assortative and nonhierarchical, whereas networks of upper-level system components (internet domains or biological processes) are disassortative and hierarchical. Our results demonstrate that network topologies of complex systems must be interpreted in light of their hierarchical natures and interaction types.     

Social traits,social networks and evolutionary biology

The social environment is both an important agent of selection for most organisms, and an emergent property of their interactions. As an aggregation of interactions among members of a population, the social environment is a product of many sets of relationships and so can be represented as a network or matrix. Social network analysis in animals has focused on why these networks possess the structure they do, and whether individuals’ network traits, representing some aspect of their social phenotype, relate to their fitness. Meanwhile, quantitative geneticists have demonstrated that traits expressed in a social context can depend on the phenotypes and genotypes of interacting partners, leading to influences of the social environment on the traits and fitness of individuals and the evolutionary trajectories of populations. Therefore, both fields are investigating similar topics, yet have arrived at these points relatively independently. We review how these approaches are diverged, and yet how they retain clear parallelism and so strong potential for complementarity. This demonstrates that, despite separate bodies of theory, advances in one might inform the other. Techniques in network analysis for quantifying social phenotypes, and for identifying community structure, should be useful for those studying the relationship between individual behaviour and group‐level phenotypes. Entering social association matrices into quantitative genetic models may also reduce bias in heritability estimates, and allow the estimation of the influence of social connectedness on trait expression. Current methods for measuring natural selection in a social context explicitly account for the fact that a trait is not necessarily the property of a single individual, something the network approaches have not yet considered when relating network metrics to individual fitness. Harnessing evolutionary models that consider traits affected by genes in other individuals (i.e. indirect genetic effects) provides the potential to understand how entire networks of social interactions in populations influence phenotypes and predict how these traits may evolve. By theoretical integration of social network analysis and quantitative genetics, we hope to identify areas of compatibility and incompatibility and to direct research efforts towards the most promising areas. Continuing this synthesis could provide important insights into the evolution of traits expressed in a social context and the evolutionary consequences of complex and nuanced social phenotypes.     

The Evolutionary Origins of Hierarchy

Hierarchical organization—the recursive composition of sub-modules—is ubiquitous in biological networks, including neural, metabolic, ecological, and genetic regulatory networks, and in human-made systems, such as large organizations and the Internet. To date, most research on hierarchy in networks has been limited to quantifying this property. However, an open, important question in evolutionary biology is why hierarchical organization evolves in the first place. It has recently been shown that modularity evolves because of the presence of a cost for network connections. Here we investigate whether such connection costs also tend to cause a hierarchical organization of such modules. In computational simulations, we find that networks without a connection cost do not evolve to be hierarchical, even when the task has a hierarchical structure. However, with a connection cost, networks evolve to be both modular and hierarchical, and these networks exhibit higher overall performance and evolvability (i.e. faster adaptation to new environments). Additional analyses confirm that hierarchy independently improves adaptability after controlling for modularity. Overall, our results suggest that the same force–the cost of connections–promotes the evolution of both hierarchy and modularity, and that these properties are important drivers of network performance and adaptability. In addition to shedding light on the emergence of hierarchy across the many domains in which it appears, these findings will also accelerate future research into evolving more complex, intelligent computational brains in the fields of artificial intelligence and robotics.     

Complex cooperative networks from evolutionary preferential attachment

In spite of its relevance to the origin of complex networks, the interplay between form and function and its role during network formation remains largely unexplored. While recent studies introduce dynamics by considering rewiring processes of a pre-existent network, we study network growth and formation by proposing an evolutionary preferential attachment model, its main feature being that the capacity of a node to attract new links depends on a dynamical variable governed in turn by the node interactions. As a specific example, we focus on the problem of the emergence of cooperation by analyzing the formation of a social network with interactions given by the Prisoner's Dilemma. The resulting networks show many features of real systems, such as scale-free degree distributions, cooperative behavior and hierarchical clustering. Interestingly, results such as the cooperators being located mostly on nodes of intermediate degree are very different from the observations of cooperative behavior on static networks. The evolutionary preferential attachment mechanism points to an evolutionary origin of scale-free networks and may help understand similar feedback problems in the dynamics of complex networks by appropriately choosing the game describing the interaction of nodes.     

Exploring local structural organization of metabolic networks using subgraph patterns

Metabolic networks of many cellular organisms share global statistical features. Their connectivity distributions follow the long-tailed power law and show the small-world property. In addition, their modular structures are organized in a hierarchical manner. Although the global topological organization of metabolic networks is well understood, their local structural organization is still not clear. Investigating local properties of metabolic networks is necessary to understand the nature of metabolism in living organisms. To identify the local structural organization of metabolic networks, we analysed the subgraphs of metabolic networks of 43 organisms from three domains of life. We first identified the network motifs of metabolic networks and identified the statistically significant subgraph patterns. We then compared metabolic networks from different domains and found that they have similar local structures and that the local structure of each metabolic network has its own taxonomical meaning. Organisms closer in taxonomy showed similar local structures. In addition, the common substrates of 43 metabolic networks were not randomly distributed, but were more likely to be constituents of cohesive subgraph patterns.     

RedeR: R/Bioconductor package for representing modular structures, nested networks and multiple levels of hierarchical associations

Visualization and analysis of molecular networks are both central to systems biology. However, there still exists a large technological gap between them, especially when assessing multiple network levels or hierarchies. Here we present RedeR, an R/Bioconductor package combined with a Java core engine for representing modular networks. The functionality of RedeR is demonstrated in two different scenarios: hierarchical and modular organization in gene co-expression networks and nested structures in time-course gene expression subnetworks. Our results demonstrate RedeR as a new framework to deal with the multiple network levels that are inherent to complex biological systems. RedeR is available from http://bioconductor.org/packages/release/bioc/html/RedeR.html.     

Contact networks and transmission of an intestinal pathogen in bumble bee (Bombus impatiens) colonies

In socially living animals, individuals interact through complex networks of contact that may influence the spread of disease. Whereas traditional epidemiological models typically assume no social structure, network theory suggests that an individual’s location in the network determines its risk of infection. Empirical, especially experimental, studies of disease spread on networks are lacking, however, largely due to a shortage of amenable study systems. We used automated video-tracking to quantify networks of physical contact among individuals within colonies of the social bumble bee Bombus impatiens. We explored the effects of network structure on pathogen transmission in naturally and artificially infected hives. We show for the first time that contact network structure determines the spread of a contagious pathogen (Crithidia bombi) in social insect colonies. Differences in rates of infection among colonies resulted largely from differences in network density among hives. Within colonies, a bee’s rate of contact with infected nestmates emerged as the only significant predictor of infection risk. The activity of bees, in terms of their movement rates and division of labour (e.g., brood care, nest care, foraging), did not influence risk of infection. Our results suggest that contact networks may have an important influence on the transmission of pathogens in social insects and, possibly, other social animals.