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.     

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.     

Fitness consequences of centrality in mutualistic individual-based networks

The relationships among the members of a population can be visualized using individual networks, where each individual is a node connected to each other by means of links describing the interactions. The centrality of a given node captures its importance within the network. We hypothesize that in mutualistic networks, the centrality of a node should benefit its fitness. We test this idea studying eight individual-based networks originated from the interaction between Erysimum mediohispanicum and its flower visitors. In these networks, each plant was considered a node and was connected to conspecifics sharing flower visitors. Centrality indicates how well connected is a given E. mediohispanicum individual with the rest of the co-occurring conspecifics because of sharing flower visitors. The centrality was estimated by three network metrics: betweenness, closeness and degree. The complex relationship between centrality, phenotype and fitness was explored by structural equation modelling. We found that the centrality of a plant was related to its fitness, with plants occupying central positions having higher fitness than those occupying peripheral positions. The structural equation models (SEMs) indicated that the centrality effect on fitness was not merely an effect of the abundance of visits and the species richness of visitors. Centrality has an effect even when simultaneously accounting for these predictors. The SEMs also indicated that the centrality effect on fitness was because of the specific phenotype of each plant, with attractive plants occupying central positions in networks, in relation to the distribution of conspecific phenotypes. This finding suggests that centrality, owing to its dependence on social interactions, may be an appropriate surrogate for the interacting phenotype of individuals.     

Topographic Hub Maps of the Human Structural Neocortical Network

Hubs within the neocortical structural network determined by graph theoretical analysis play a crucial role in brain function. We mapped neocortical hubs topographically, using a sample population of 63 young adults. Subjects were imaged with high resolution structural and diffusion weighted magnetic resonance imaging techniques. Multiple network configurations were then constructed per subject, using random parcellations to define the nodes and using fibre tractography to determine the connectivity between the nodes. The networks were analysed with graph theoretical measures. Our results give reference maps of hub distribution measured with betweenness centrality and node degree. The loci of the hubs correspond with key areas from known overlapping cognitive networks. Several hubs were asymmetrically organized across hemispheres. Furthermore, females have hubs with higher betweenness centrality and males have hubs with higher node degree. Female networks have higher small-world indices.     

A systematic survey of centrality measures for protein-protein interaction networks

Background

Numerous centrality measures have been introduced to identify “central” nodes in large networks. The availability of a wide range of measures for ranking influential nodes leaves the user to decide which measure may best suit the analysis of a given network. The choice of a suitable measure is furthermore complicated by the impact of the network topology on ranking influential nodes by centrality measures. To approach this problem systematically, we examined the centrality profile of nodes of yeast protein-protein interaction networks (PPINs) in order to detect which centrality measure is succeeding in predicting influential proteins. We studied how different topological network features are reflected in a large set of commonly used centrality measures.

Results

We used yeast PPINs to compare 27 common of centrality measures. The measures characterize and assort influential nodes of the networks. We applied principal component analysis (PCA) and hierarchical clustering and found that the most informative measures depend on the network’s topology. Interestingly, some measures had a high level of contribution in comparison to others in all PPINs, namely Latora closeness, Decay, Lin, Freeman closeness, Diffusion, Residual closeness and Average distance centralities.

Conclusions

The choice of a suitable set of centrality measures is crucial for inferring important functional properties of a network. We concluded that undertaking data reduction using unsupervised machine learning methods helps to choose appropriate variables (centrality measures). Hence, we proposed identifying the contribution proportions of the centrality measures with PCA as a prerequisite step of network analysis before inferring functional consequences, e.g., essentiality of a node.

     

Identifying Influential Nodes in Large-Scale Directed Networks: The Role of Clustering

Identifying influential nodes in very large-scale directed networks is a big challenge relevant to disparate applications, such as accelerating information propagation, controlling rumors and diseases, designing search engines, and understanding hierarchical organization of social and biological networks. Known methods range from node centralities, such as degree, closeness and betweenness, to diffusion-based processes, like PageRank and LeaderRank. Some of these methods already take into account the influences of a node’s neighbors but do not directly make use of the interactions among it’s neighbors. Local clustering is known to have negative impacts on the information spreading. We further show empirically that it also plays a negative role in generating local connections. Inspired by these facts, we propose a local ranking algorithm named ClusterRank, which takes into account not only the number of neighbors and the neighbors’ influences, but also the clustering coefficient. Subject to the susceptible-infected-recovered (SIR) spreading model with constant infectivity, experimental results on two directed networks, a social network extracted from delicious.com and a large-scale short-message communication network, demonstrate that the ClusterRank outperforms some benchmark algorithms such as PageRank and LeaderRank. Furthermore, ClusterRank can also be applied to undirected networks where the superiority of ClusterRank is significant compared with degree centrality and k-core decomposition. In addition, ClusterRank, only making use of local information, is much more efficient than global methods: It takes only 191 seconds for a network with about nodes, more than 15 times faster than PageRank.     

Structural vulnerability of the French swine industry trade network to the spread of infectious diseases

The networks generated by live animal movements are the principal vector for the propagation of infectious agents between farms, and their topology strongly affects how fast a disease may spread. The structural characteristics of networks may thus provide indicators of network vulnerability to the spread of infectious disease. This study applied social network analysis methods to describe the French swine trade network. Initial analysis involved calculating several parameters to characterize networks and then identifying high-risk subgroups of holdings for different time scales. Holding-specific centrality measurements (‘degree’, ‘betweenness’ and ‘ingoing infection chain’), which summarize the place and the role of holdings in the network, were compared according to the production type. In addition, network components and communities, areas where connectedness is particularly high and could influence the speed and the extent of a disease, were identified and analysed. Dealer holdings stood out because of their high centrality values suggesting that these holdings may control the flow of animals in part of the network. Herds with growing units had higher values for degree and betweenness centrality, representing central positions for both spreading and receiving disease, whereas herds with finishing units had higher values for in-degree and ingoing infection chain centrality values and appeared more vulnerable with many contacts through live animal movements and thus at potentially higher risk for introduction of contagious diseases. This reflects the dynamics of the swine trade with downward movements along the production chain. But, the significant heterogeneity of farms with several production units did not reveal any particular type of production for targeting disease surveillance or control. Besides, no giant strong connected component was observed, the network being rather organized according to communities of small or medium size (<20% of network size). Because of this fragmentation, the swine trade network appeared less structurally vulnerable than ruminant trade networks. This fragmentation is explained by the hierarchical structure, which thus limits the structural vulnerability of the global trade network. However, inside communities, the hierarchical structure of the swine production system would favour the spread of an infectious agent (especially if introduced in breeding herds).     

Generalized walks-based centrality measures for complex biological networks

A strategy for zooming in and out the topological environment of a node in a complex network is developed. This approach is applied here to generalize the subgraph centrality of nodes in complex networks. In this case the zooming in strategy is based on the use of some known matrix functions which allow focusing locally on the environment of a node. When a zooming out strategy is applied new matrix functions are introduced, which give a more global picture of the topological surrounds of a node. These indices permit a modulation of the scales at which the environment of a node influences its centrality. We apply them to the study of 10 protein-protein interaction (PPI) networks. We illustrate the similarities and differences between the generalized subgraph centrality indices as well as among them and some classical centrality measures. We show here that the use of centrality indices based on the zooming in strategy identifies a larger number of essential proteins in the yeast PPI network than any of the other centrality measures studied.     

Prediction of lethal and synthetically lethal knock-outs in regulatory networks

The complex interactions involved in regulation of a cell’s function are captured by its interaction graph. More often than not, detailed knowledge about enhancing or suppressive regulatory influences and cooperative effects is lacking and merely the presence or absence of directed interactions is known. Here, we investigate to which extent such reduced information allows to forecast the effect of a knock-out or a combination of knock-outs. Specifically, we ask in how far the lethality of eliminating nodes may be predicted by their network centrality, such as degree and betweenness, without knowing the function of the system. The function is taken as the ability to reproduce a fixed point under a discrete Boolean dynamics. We investigate two types of stochastically generated networks: fully random networks and structures grown with a mechanism of node duplication and subsequent divergence of interactions. On all networks we find that the out-degree is a good predictor of the lethality of a single node knock-out. For knock-outs of node pairs, the fraction of successors shared between the two knocked-out nodes (out-overlap) is a good predictor of synthetic lethality. Out-degree and out-overlap are locally defined and computationally simple centrality measures that provide a predictive power close to the optimal predictor.     

Identifying Node Role in Social Network Based on Multiple Indicators

It is a classic topic of social network analysis to evaluate the importance of nodes and identify the node that takes on the role of core or bridge in a network. Because a single indicator is not sufficient to analyze multiple characteristics of a node, it is a natural solution to apply multiple indicators that should be selected carefully. An intuitive idea is to select some indicators with weak correlations to efficiently assess different characteristics of a node. However, this paper shows that it is much better to select the indicators with strong correlations. Because indicator correlation is based on the statistical analysis of a large number of nodes, the particularity of an important node will be outlined if its indicator relationship doesn''t comply with the statistical correlation. Therefore, the paper selects the multiple indicators including degree, ego-betweenness centrality and eigenvector centrality to evaluate the importance and the role of a node. The importance of a node is equal to the normalized sum of its three indicators. A candidate for core or bridge is selected from the great degree nodes or the nodes with great ego-betweenness centrality respectively. Then, the role of a candidate is determined according to the difference between its indicators'' relationship with the statistical correlation of the overall network. Based on 18 real networks and 3 kinds of model networks, the experimental results show that the proposed methods perform quite well in evaluating the importance of nodes and in identifying the node role.     

Motif-Role-Fingerprints: The Building-Blocks of Motifs,Clustering-Coefficients and Transitivities in Directed Networks

Complex networks are frequently characterized by metrics for which particular subgraphs are counted. One statistic from this category, which we refer to as motif-role fingerprints, differs from global subgraph counts in that the number of subgraphs in which each node participates is counted. As with global subgraph counts, it can be important to distinguish between motif-role fingerprints that are ‘structural’ (induced subgraphs) and ‘functional’ (partial subgraphs). Here we show mathematically that a vector of all functional motif-role fingerprints can readily be obtained from an arbitrary directed adjacency matrix, and then converted to structural motif-role fingerprints by multiplying that vector by a specific invertible conversion matrix. This result demonstrates that a unique structural motif-role fingerprint exists for any given functional motif-role fingerprint. We demonstrate a similar result for the cases of functional and structural motif-fingerprints without node roles, and global subgraph counts that form the basis of standard motif analysis. We also explicitly highlight that motif-role fingerprints are elemental to several popular metrics for quantifying the subgraph structure of directed complex networks, including motif distributions, directed clustering coefficient, and transitivity. The relationships between each of these metrics and motif-role fingerprints also suggest new subtypes of directed clustering coefficients and transitivities. Our results have potential utility in analyzing directed synaptic networks constructed from neuronal connectome data, such as in terms of centrality. Other potential applications include anomaly detection in networks, identification of similar networks and identification of similar nodes within networks. Matlab code for calculating all stated metrics following calculation of functional motif-role fingerprints is provided as S1 Matlab File.     

Epidemic threshold and network structure: The interplay of probability of transmission and of persistence in small-size directed networks

A growing number of studies are investigating the effect of contact structure on the dynamics of epidemics in large-scale complex networks. Whether findings thus obtained apply also to networks of small size, and thus to many real-world biological applications, is still an open question. We use numerical simulations of disease spread in directed networks of 100 individual nodes with a constant number of links. We show that, no matter the type of network structure (local, small-world, random and scale-free), there is a linear threshold determined by the probability of infection transmission between connected nodes and the probability of infection persistence in an infected node. The threshold is significantly lower for scale-free networks compared to local, random and small-world ones only if super-connected nodes have a higher number of links both to and from other nodes. The starting point, the node at which the epidemic starts, does not affect the threshold conditions, but has a marked influence on the final size of the epidemic in all kinds of network. There is evidence that contact structure has an influence on the average final size of an epidemic across all starting nodes, with significantly lower values in scale-free networks at equilibrium. Simulations in scale-free networks show a distinctive time-series pattern, which, if found in a real epidemic, can be used to infer the underlying network structure. The findings have relevance also for meta-population ecology and species conservation.     

Identification of essential proteins based on edge clustering coefficient

Identification of essential proteins is key to understanding the minimal requirements for cellular life and important for drug design. The rapid increase of available protein-protein interaction (PPI) data has made it possible to detect protein essentiality on network level. A series of centrality measures have been proposed to discover essential proteins based on network topology. However, most of them tended to focus only on the location of single protein, but ignored the relevance between interactions and protein essentiality. In this paper, a new centrality measure for identifying essential proteins based on edge clustering coefficient, named as NC, is proposed. Different from previous centrality measures, NC considers both the centrality of a node and the relationship between it and its neighbors. For each interaction in the network, we calculate its edge clustering coefficient. A node’s essentiality is determined by the sum of the edge clustering coefficients of interactions connecting it and its neighbors. The new centrality measure NC takes into account the modular nature of protein essentiality. NC is applied to three different types of yeast protein-protein interaction networks, which are obtained from the DIP database, the MIPS database and the BioGRID database, respectively. The experimental results on the three different networks show that the number of essential proteins discovered by NC universally exceeds that discovered by the six other centrality measures: DC, BC, CC, SC, EC, and IC. Moreover, the essential proteins discovered by NC show significant cluster effect.     

Structural Controllability and Controlling Centrality of Temporal Networks

Temporal networks are such networks where nodes and interactions may appear and disappear at various time scales. With the evidence of ubiquity of temporal networks in our economy, nature and society, it''s urgent and significant to focus on its structural controllability as well as the corresponding characteristics, which nowadays is still an untouched topic. We develop graphic tools to study the structural controllability as well as its characteristics, identifying the intrinsic mechanism of the ability of individuals in controlling a dynamic and large-scale temporal network. Classifying temporal trees of a temporal network into different types, we give (both upper and lower) analytical bounds of the controlling centrality, which are verified by numerical simulations of both artificial and empirical temporal networks. We find that the positive relationship between aggregated degree and controlling centrality as well as the scale-free distribution of node''s controlling centrality are virtually independent of the time scale and types of datasets, meaning the inherent robustness and heterogeneity of the controlling centrality of nodes within temporal networks.     

Modularity of trophic network is driven by phylogeny and migration in a steppe ecosystem

Evidence is mounting that the structures of trophic networks are governed by migratory movements of interacting species and also by their phylogenetic relationships. Using the largest available trophic network of a large steppe ecosystem, we tested that steppe trophic networks including migratory species are associated with (i) migratory strategy and (ii) phylogenetic relatedness of interacting species: (1) whole graph-level metrics, estimated as modularity, and (2) species-level network metrics, measured as node degree (number of interacting partners), and centrality metrics. We found that (1) a substantial number of links were established by migrant taxa; (2) the phylogenetic signal in network structure was moderate for both consumer and prey nodes; (3) both consumer and prex phylogenies affected modularity, which was modulated by migration strategy; and (4) all species-level graph properties significantly differed between networks including and excluding migratory taxa. In sum, here we show that the structure of steppe trophic networks is primarily governed by migratory strategies and to a lesser extent, by phylogenetic relatedness, using the largest available food web representative for steppe ecology and migration biology.     

linkcomm: an R package for the generation, visualization, and analysis of link communities in networks of arbitrary size and type

SUMMARY: An essential element when analysing the structure, function, and dynamics of biological networks is the identification of communities of related nodes. An algorithm proposed recently enhances this process by clustering the links between nodes, rather than the nodes themselves, thereby allowing each node to belong to multiple overlapping or nested communities. The R package 'linkcomm' implements this algorithm and extends it in several aspects: (i) the clustering algorithm handles networks that are weighted, directed, or both weighted and directed; (ii) several visualization methods are implemented that facilitate the representation of the link communities and their relationships; (iii) a suite of functions are included for the downstream analysis of the link communities including novel community-based measures of node centrality; (iv) the main algorithm is written in C++ and designed to handle networks of any size; and (v) several clustering methods are available for networks that can be handled in memory, and the number of communities can be adjusted by the user. AVAILABILITY: The program is freely available from the Comprehensive R Archive Network (http://cran.r-project.org/) under the terms of the GNU General Public License (version 2 or later).     

Localized network centrality and essentiality in the yeast–protein interaction network

It has been suggested that a close relationship exists between gene essentiality and network centrality in protein–protein interaction networks. However, recent studies have reported somewhat conflicting results on this relationship. In this study, we investigated whether essential proteins could be inferred from network centrality alone. In addition, we determined which centrality measures describe the essentiality well. For this analysis, we devised new local centrality measures based on several well‐known centrality measures to more precisely describe the connection between network topology and essentiality. We examined two recent yeast protein–protein interaction networks using 40 different centrality measures. We discovered a close relationship between the path‐based localized information centrality and gene essentiality, which suggested underlying topological features that represent essentiality. We propose that two important features of the localized information centrality (proper representation of environmental complexity and the consideration of local sub‐networks) are the key factors that reveal essentiality. In addition, a random forest classifier showed reasonable performance at classifying essential proteins. Finally, the results of clustering analysis using centrality measures indicate that some network clusters are closely related with both particular biological processes and essentiality, suggesting that functionally related proteins tend to share similar network properties.     

Fast computing betweenness centrality with virtual nodes on large sparse networks

Betweenness centrality is an essential index for analysis of complex networks. However, the calculation of betweenness centrality is quite time-consuming and the fastest known algorithm uses O(N(M + N log N)) time and O(N + M) space for weighted networks, where N and M are the number of nodes and edges in the network, respectively. By inserting virtual nodes into the weighted edges and transforming the shortest path problem into a breadth-first search (BFS) problem, we propose an algorithm that can compute the betweenness centrality in O(wDN2) time for integer-weighted networks, where w is the average weight of edges and D is the average degree in the network. Considerable time can be saved with the proposed algorithm when w < log N/D + 1, indicating that it is suitable for lightly weighted large sparse networks. A similar concept of virtual node transformation can be used to calculate other shortest path based indices such as closeness centrality, graph centrality, stress centrality, and so on. Numerical simulations on various randomly generated networks reveal that it is feasible to use the proposed algorithm in large network analysis.