A Bio-Inspired Methodology of Identifying Influential Nodes in Complex Networks

How to identify influential nodes is a key issue in complex networks. The degree centrality is simple, but is incapable to reflect the global characteristics of networks. Betweenness centrality and closeness centrality do not consider the location of nodes in the networks, and semi-local centrality, leaderRank and pageRank approaches can be only applied in unweighted networks. In this paper, a bio-inspired centrality measure model is proposed, which combines the Physarum centrality with the K-shell index obtained by K-shell decomposition analysis, to identify influential nodes in weighted networks. Then, we use the Susceptible-Infected (SI) model to evaluate the performance. Examples and applications are given to demonstrate the adaptivity and efficiency of the proposed method. In addition, the results are compared with existing methods.     

Identification of Important Nodes in Directed Biological Networks: A Network Motif Approach

Identification of important nodes in complex networks has attracted an increasing attention over the last decade. Various measures have been proposed to characterize the importance of nodes in complex networks, such as the degree, betweenness and PageRank. Different measures consider different aspects of complex networks. Although there are numerous results reported on undirected complex networks, few results have been reported on directed biological networks. Based on network motifs and principal component analysis (PCA), this paper aims at introducing a new measure to characterize node importance in directed biological networks. Investigations on five real-world biological networks indicate that the proposed method can robustly identify actually important nodes in different networks, such as finding command interneurons, global regulators and non-hub but evolutionary conserved actually important nodes in biological networks. Receiver Operating Characteristic (ROC) curves for the five networks indicate remarkable prediction accuracy of the proposed measure. The proposed index provides an alternative complex network metric. Potential implications of the related investigations include identifying network control and regulation targets, biological networks modeling and analysis, as well as networked medicine.     

A Bridge Role Metric Model for Nodes in Software Networks

A bridge role metric model is put forward in this paper. Compared with previous metric models, our solution of a large-scale object-oriented software system as a complex network is inherently more realistic. To acquire nodes and links in an undirected network, a new model that presents the crucial connectivity of a module or the hub instead of only centrality as in previous metric models is presented. Two previous metric models are described for comparison. In addition, it is obvious that the fitting curve between the results and degrees can well be fitted by a power law. The model represents many realistic characteristics of actual software structures, and a hydropower simulation system is taken as an example. This paper makes additional contributions to an accurate understanding of module design of software systems and is expected to be beneficial to software engineering practices.     

PhysarumSpreader: A New Bio-Inspired Methodology for Identifying Influential Spreaders in Complex Networks

Identifying influential spreaders in networks, which contributes to optimizing the use of available resources and efficient spreading of information, is of great theoretical significance and practical value. A random-walk-based algorithm LeaderRank has been shown as an effective and efficient method in recognizing leaders in social network, which even outperforms the well-known PageRank method. As LeaderRank is initially developed for binary directed networks, further extensions should be studied in weighted networks. In this paper, a generalized algorithm PhysarumSpreader is proposed by combining LeaderRank with a positive feedback mechanism inspired from an amoeboid organism called Physarum Polycephalum. By taking edge weights into consideration and adding the positive feedback mechanism, PhysarumSpreader is applicable in both directed and undirected networks with weights. By taking two real networks for examples, the effectiveness of the proposed method is demonstrated by comparing with other standard centrality measures.     

Oscillations in Large-Scale Cortical Networks: Map-Based Model

We develop a new computationally efficient approach for the analysis of complex large-scale neurobiological networks. Its key element is the use of a new phenomenological model of a neuron capable of replicating important spike pattern characteristics and designed in the form of a system of difference equations (a map). We developed a set of map-based models that replicate spiking activity of cortical fast spiking, regular spiking and intrinsically bursting neurons. Interconnected with synaptic currents these model neurons demonstrated responses very similar to those found with Hodgkin-Huxley models and in experiments. We illustrate the efficacy of this approach in simulations of one- and two-dimensional cortical network models consisting of regular spiking neurons and fast spiking interneurons to model sleep and activated states of the thalamocortical system. Our study suggests that map-based models can be widely used for large-scale simulations and that such models are especially useful for tasks where the modeling of specific firing patterns of different cell classes is important.     

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.     

Directed Stem Cell Differentiation: The Role of Physical Forces

Abstract

A number of factors contribute to the control of stem cell fate. In particular, the evidence for how physical forces control the stem cell differentiation program is now accruing. In this review, the authors discuss the types of physical forces: mechanical forces, cell shape, extracellular matrix geometry/properties, and cell-cell contacts and morphogenic factors, which evidence suggests play a role in influencing stem cell fate.     

Degree Correlations in Directed Scale-Free Networks

Scale-free networks, in which the distribution of the degrees obeys a power-law, are ubiquitous in the study of complex systems. One basic network property that relates to the structure of the links found is the degree assortativity, which is a measure of the correlation between the degrees of the nodes at the end of the links. Degree correlations are known to affect both the structure of a network and the dynamics of the processes supported thereon, including the resilience to damage, the spread of information and epidemics, and the efficiency of defence mechanisms. Nonetheless, while many studies focus on undirected scale-free networks, the interactions in real-world systems often have a directionality. Here, we investigate the dependence of the degree correlations on the power-law exponents in directed scale-free networks. To perform our study, we consider the problem of building directed networks with a prescribed degree distribution, providing a method for proper generation of power-law-distributed directed degree sequences. Applying this new method, we perform extensive numerical simulations, generating ensembles of directed scale-free networks with exponents between 2 and 3, and measuring ensemble averages of the Pearson correlation coefficients. Our results show that scale-free networks are on average uncorrelated across directed links for three of the four possible degree-degree correlations, namely in-degree to in-degree, in-degree to out-degree, and out-degree to out-degree. However, they exhibit anticorrelation between the number of outgoing connections and the number of incoming ones. The findings are consistent with an entropic origin for the observed disassortativity in biological and technological networks.     

Development of Large-Scale Functional Brain Networks in Children

The ontogeny of large-scale functional organization of the human brain is not well understood. Here we use network analysis of intrinsic functional connectivity to characterize the organization of brain networks in 23 children (ages 7–9 y) and 22 young-adults (ages 19–22 y). Comparison of network properties, including path-length, clustering-coefficient, hierarchy, and regional connectivity, revealed that although children and young-adults' brains have similar “small-world” organization at the global level, they differ significantly in hierarchical organization and interregional connectivity. We found that subcortical areas were more strongly connected with primary sensory, association, and paralimbic areas in children, whereas young-adults showed stronger cortico-cortical connectivity between paralimbic, limbic, and association areas. Further, combined analysis of functional connectivity with wiring distance measures derived from white-matter fiber tracking revealed that the development of large-scale brain networks is characterized by weakening of short-range functional connectivity and strengthening of long-range functional connectivity. Importantly, our findings show that the dynamic process of over-connectivity followed by pruning, which rewires connectivity at the neuronal level, also operates at the systems level, helping to reconfigure and rebalance subcortical and paralimbic connectivity in the developing brain. Our study demonstrates the usefulness of network analysis of brain connectivity to elucidate key principles underlying functional brain maturation, paving the way for novel studies of disrupted brain connectivity in neurodevelopmental disorders such as autism.     

Chromosome Rearrangement Breakpoint Clustering: The Role of Clonal Selection

Chromosome rearrangements may result in fusion genes that encode chimeric proteins. The break-points of many such rearrangements cluster in definite genomic regions. In addition, many breakpoint clusters contain specific genomic elements, such as topoisomerase II consensus sites, nuclear matrix attachment sites, and various nucleotide sequences capable of assuming noncanonical secondary structure. Studies on breakpoint location are reviewed in terms of the available data on chromatin structure. In addition, the relationship between the location of breakpoints and the domain organization of the respective proteins, which has not been dealt with in published studies, is analyzed. The possible mechanisms of chromosome rearrangements are discussed.__________Translated from Molekulyarnaya Biologiya, Vol. 39, No. 3, 2005, pp. 355–363.Original Russian Text Copyright © 2005 by Umanskaya, Bystritskiy, Razin.     

Identifying Hubs in Protein Interaction Networks

Background

In spite of the scale-free degree distribution that characterizes most protein interaction networks (PINs), it is common to define an ad hoc degree scale that defines “hub” proteins having special topological and functional significance. This raises the concern that some conclusions on the functional significance of proteins based on network properties may not be robust.

Methodology

In this paper we present three objective methods to define hub proteins in PINs: one is a purely topological method and two others are based on gene expression and function. By applying these methods to four distinct PINs, we examine the extent of agreement among these methods and implications of these results on network construction.

Conclusions

We find that the methods agree well for networks that contain a balance between error-free and unbiased interactions, indicating that the hub concept is meaningful for such networks.     

Temporal Effects in Trend Prediction: Identifying the Most Popular Nodes in the Future

Prediction is an important problem in different science domains. In this paper, we focus on trend prediction in complex networks, i.e. to identify the most popular nodes in the future. Due to the preferential attachment mechanism in real systems, nodes’ recent degree and cumulative degree have been successfully applied to design trend prediction methods. Here we took into account more detailed information about the network evolution and proposed a temporal-based predictor (TBP). The TBP predicts the future trend by the node strength in the weighted network with the link weight equal to its exponential aging. Three data sets with time information are used to test the performance of the new method. We find that TBP have high general accuracy in predicting the future most popular nodes. More importantly, it can identify many potential objects with low popularity in the past but high popularity in the future. The effect of the decay speed in the exponential aging on the results is discussed in detail.     

珍稀鹤类巢址的空间聚类识别方法

依据2003年到2005年松嫩平原西部地区珍稀鹤类巢址调查数据,利用三种不同类型的指数进行分析研究:(1)拓扑指数,Voronoi图面积;(2)统计指数,Morishita指数;(3)空间指数,分维数.结果表明珍稀鹤类巢址空间格局具有明显的空间聚类分布,这三个指数使我们对珍稀鹤类巢址的聚类现象有了定量的认识,加深对自然保护区资源保护的重要性.     

Jerarca: Efficient Analysis of Complex Networks Using Hierarchical Clustering

Background

How to extract useful information from complex biological networks is a major goal in many fields, especially in genomics and proteomics. We have shown in several works that iterative hierarchical clustering, as implemented in the UVCluster program, is a powerful tool to analyze many of those networks. However, the amount of computation time required to perform UVCluster analyses imposed significant limitations to its use.

Methodology/Principal Findings

We describe the suite Jerarca, designed to efficiently convert networks of interacting units into dendrograms by means of iterative hierarchical clustering. Jerarca is divided into three main sections. First, weighted distances among units are computed using up to three different approaches: a more efficient version of UVCluster and two new, related algorithms called RCluster and SCluster. Second, Jerarca builds dendrograms based on those distances, using well-known phylogenetic algorithms, such as UPGMA or Neighbor-Joining. Finally, Jerarca provides optimal partitions of the trees using statistical criteria based on the distribution of intra- and intercluster connections. Outputs compatible with the phylogenetic software MEGA and the Cytoscape package are generated, allowing the results to be easily visualized.

Conclusions/Significance

The four main advantages of Jerarca in respect to UVCluster are: 1) Improved speed of a novel UVCluster algorithm; 2) Additional, alternative strategies to perform iterative hierarchical clustering; 3) Automatic evaluation of the hierarchical trees to obtain optimal partitions; and, 4) Outputs compatible with popular software such as MEGA and Cytoscape.