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.     

The dichotomy in degree correlation of biological networks

Most complex networks from different areas such as biology, sociology or technology, show a correlation on node degree where the possibility of a link between two nodes depends on their connectivity. It is widely believed that complex networks are either disassortative (links between hubs are systematically suppressed) or assortative (links between hubs are enhanced). In this paper, we analyze a variety of biological networks and find that they generally show a dichotomous degree correlation. We find that many properties of biological networks can be explained by this dichotomy in degree correlation, including the neighborhood connectivity, the sickle-shaped clustering coefficient distribution and the modularity structure. This dichotomy distinguishes biological networks from real disassortative networks or assortative networks such as the Internet and social networks. We suggest that the modular structure of networks accounts for the dichotomy in degree correlation and vice versa, shedding light on the source of modularity in biological networks. We further show that a robust and well connected network necessitates the dichotomy of degree correlation, suggestive of an evolutionary motivation for its existence. Finally, we suggest that a dichotomous degree correlation favors a centrally connected modular network, by which the integrity of network and specificity of modules might be reconciled.     

Recurrence Network Analysis of the Synchronous EEG Time Series in Normal and Epileptic Brains

We sought to analyze the dynamic properties of brain electrical activity from healthy volunteers and epilepsy patients using recurrence networks. Phase-space trajectories of synchronous electroencephalogram signals were obtained through embedding dimension in phase-space reconstruction based on the distance set of space points. The recurrence matrix calculated from phase-space trajectories was identified with the adjacency matrix of a complex network. Then, we applied measures to characterize the complex network to this recurrence network. A detailed analysis revealed the following: (1) The recurrence networks of normal brains exhibited a sparser connectivity and smaller clustering coefficient compared with that of epileptic brains; (2) the small-world property existed in both normal and epileptic brains consistent with the previous empirical studies of structural and functional brain networks; and (3) the assortative property of the recurrence network was found by computing the assortative coefficients; their values increased from normal to epileptic brain which accurately suggested the difference of the states. These universal and non-universal characteristics of recurrence networks might help clearly understand the underlying neurodynamics of the brain and provide an efficient tool for clinical diagnosis.     

Hydrophobic, hydrophilic, and charged amino acid networks within protein

The native three-dimensional structure of a single protein is determined by the physicochemical nature of its constituent amino acids. The 20 different types of amino acids, depending on their physicochemical properties, can be grouped into three major classes: hydrophobic, hydrophilic, and charged. The anatomy of the weighted and unweighted networks of hydrophobic, hydrophilic, and charged residues separately for a large number of proteins were studied. Results showed that the average degree of the hydrophobic networks has a significantly larger value than that of hydrophilic and charged networks. The average degree of the hydrophilic networks is slightly higher than that of the charged networks. The average strength of the nodes of hydrophobic networks is nearly equal to that of the charged network, whereas that of hydrophilic networks has a smaller value than that of hydrophobic and charged networks. The average strength for each of the three types of networks varies with its degree. The average strength of a node in a charged network increases more sharply than that of the hydrophobic and hydrophilic networks. Each of the three types of networks exhibits the "small-world" property. Our results further indicate that the all-amino-acids networks and hydrophobic networks are of assortative type. Although most of the hydrophilic and charged networks are of the assortative type, few others have the characteristics of disassortative mixing of the nodes. We have further observed that all-amino-acids networks and hydrophobic networks bear the signature of hierarchy, whereas the hydrophilic and charged networks do not have any hierarchical signature.     

Weighting,scale dependence and indirect effects in ecological networks: A comparative study

We studied the importance of weighting in ecological interaction networks. Fifty-three weighted interaction networks were analyzed and compared to their unweighted alternatives, based on data taken from two standard databases. We used five network indices, each with weighting and unweighting options, to characterize the positional importance of nodes in these networks. For every network, we ranked the nodes according to their importance values, based on direct and indirect indices and then we compared the rank order of coefficients to reveal potential differences between network types and between indices. We found that (1) weighting affects node ordering very seriously, (2) food webs fundamentally differ from other network types in this respect, (3) direct and indirect indices provide fairly different results but indirect effects are similar if longer than two steps, and (4) the effect of weighting depends on the number of network nodes in case of direct interactions only. We concluded that the importance of interaction weights may depend on the evolutionary stability of interaction types.     

Disease spread in small-size directed networks: Epidemic threshold, correlation between links to and from nodes, and clustering

Network epidemiology has mainly focused on large-scale complex networks. It is unclear whether findings of these investigations also apply to networks of small size. This knowledge gap is of relevance for many biological applications, including meta-communities, plant–pollinator interactions and the spread of the oomycete pathogen Phytophthora ramorum in networks of plant nurseries. Moreover, many small-size biological networks are inherently asymmetrical and thus cannot be realistically modelled with undirected networks. We modelled disease spread and establishment in directed networks of 100 and 500 nodes at four levels of connectance in six network structures (local, small-world, random, one-way, uncorrelated, and two-way scale-free networks). The model was based on the probability of infection persistence in a node and of infection transmission between connected nodes. Regardless of the size of the network, the epidemic threshold did not depend on the starting node of infection but was negatively related to the correlation coefficient between in- and out-degree for all structures, unless networks were sparsely connected. In this case clustering played a significant role. For small-size scale-free directed networks to have a lower epidemic threshold than other network structures, there needs to be a positive correlation between number of links to and from nodes. When this correlation is negative (one-way scale-free networks), the epidemic threshold for small-size networks can be higher than in non-scale-free networks. Clustering does not necessarily have an influence on the epidemic threshold if connectance is kept constant. Analyses of the influence of the clustering on the epidemic threshold in directed networks can also be spurious if they do not consider simultaneously the effect of the correlation coefficient between in- and out-degree.     

Connectivity matrix method for analyses of biological networks and its application to atom-level analysis of a model network of carbohydrate metabolism

An approach for analysis of biological networks is proposed. In this approach, named the connectivity matrix (CM) method, all the connectivities of interest are expressed in a matrix. Then, a variety of analyses are performed on GNU Octave or Matlab. Each node in the network is expressed as a row vector or numeral that carries information defining or characterising the node itself. Information about connectivity itself is also expressed as a row vector or numeral. Thus, connection of node n1 to node n2 through edge e is expressed as [n1, n2, e], a row vector formed by the combination of three row vectors or numerals, where n1, n2 and e indicate two different nodes and one connectivity, respectively. All the connectivities in any given network are expressed as a matrix, CM, each row of which corresponds to one connectivity. Using this CM method, intermetabolite atom-level connectivity is investigated in a model metabolic network composed of the reactions for glycolysis, oxidative decarboxylation of pyruvate, citric acid cycle, pentose phosphate pathway and gluconeogenesis.     

Matching–centrality decomposition and the forecasting of new links in networks

Networks play a prominent role in the study of complex systems of interacting entities in biology, sociology, and economics. Despite this diversity, we demonstrate here that a statistical model decomposing networks into matching and centrality components provides a comprehensive and unifying quantification of their architecture. The matching term quantifies the assortative structure in which node makes links with which other node, whereas the centrality term quantifies the number of links that nodes make. We show, for a diverse set of networks, that this decomposition can provide a tight fit to observed networks. Then we provide three applications. First, we show that the model allows very accurate prediction of missing links in partially known networks. Second, when node characteristics are known, we show how the matching–centrality decomposition can be related to this external information. Consequently, it offers us a simple and versatile tool to explore how node characteristics explain network architecture. Finally, we demonstrate the efficiency and flexibility of the model to forecast the links that a novel node would create if it were to join an existing network.     

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.     

Molecular basis for evolving modularity in the yeast protein interaction network

Scale-free networks are generically defined by a power-law distribution of node connectivities. Vastly different graph topologies fit this law, ranging from the assortative, with frequent similar-degree node connections, to a modular structure. Using a metric to determine the extent of modularity, we examined the yeast protein network and found it to be significantly self-dissimilar. By orthologous node categorization, we established the evolutionary trend in the network, from an “emerging” assortative network to a present-day modular topology. The evolving topology fits a generic connectivity distribution but with a progressive enrichment in intramodule hubs that avoid each other. Primeval tolerance to random node failure is shown to evolve toward resilience to hub failure, thus removing the fragility often ascribed to scale-free networks. This trend is algorithmically reproduced by adopting a connectivity accretion law that disfavors like-degree connections for large-degree nodes. The selective advantage of this trend relates to the need to prevent a failed hub from inducing failure in an adjacent hub. The molecular basis for the evolutionary trend is likely rooted in the high-entropy penalty entailed in the association of two intramodular hubs.     

氨基酸邻域对二级结构的影响程度研究

通过研究神经网络权值矩阵的算法,挖掘蛋白质二级结构与氨基酸序列间的内在规律,提高一级序列预测二级结构的准确度。神经网络方法在特征分类方面具有良好表现,经过学习训练后的神经元连接权值矩阵包含样本的内在特征和规律。研究使用神经网络权值矩阵打分预测;采用错位比对方法寻找敏感的氨基酸邻域;分析测试集在不同加窗长度下的共性表现。实验表明,在滑动窗口长度L=7时,预测性能变化显著;邻域位置P=4的氨基酸残基对预测性能有加强作用。该研究方法为基于局部序列特征的蛋白质二级结构预测提供了新的算法设计。     

林地叶面积指数遥感估算方法适用分析

叶面积指数是与森林冠层能量和CO2交换密切相关的一个重要植被结构参数,为了探讨估算林地叶面积指数LAI的遥感适用方法和提高精度的途径,利用TRAC仪器测定北京城区森林样地的LAI,从Landsat TM遥感图像计算NDVI、SR、RSR、SAVI植被指数,分别建立估算LAI的单植被指数统计模型、多植被指数组合的改进BP神经网络,获取最有效描述LAI与植被指数非线性关系的方法并应用到TM图像估算北京城区LAI。结果表明,单植被指数非线性统计模型估算LAI的精度高于线性统计模型;多植被指数组合神经网络中,以NDVI、RSR、SAVI组合估算LAI的精度最高,估算值与观测值线性回归方程的R2最高,为0.827,而RMSE最低,为0.189,神经网络解决了多植被指数组合统计模型非线性回归方程的系数较多、较难确定的问题,可较为有效的应用于遥感图像林地LAI的估算。     

Ranking Competitors Using Degree-Neutralized Random Walks

Competition is ubiquitous in many complex biological, social, and technological systems, playing an integral role in the evolutionary dynamics of the systems. It is often useful to determine the dominance hierarchy or the rankings of the components of the system that compete for survival and success based on the outcomes of the competitions between them. Here we propose a ranking method based on the random walk on the network representing the competitors as nodes and competitions as directed edges with asymmetric weights. We use the edge weights and node degrees to define the gradient on each edge that guides the random walker towards the weaker (or the stronger) node, which enables us to interpret the steady-state occupancy as the measure of the node''s weakness (or strength) that is free of unwarranted degree-induced bias. We apply our method to two real-world competition networks and explore the issues of ranking stabilization and prediction accuracy, finding that our method outperforms other methods including the baseline win–loss differential method in sparse networks.     

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.     

Computing topological parameters of biological networks

Rapidly increasing amounts of molecular interaction data are being produced by various experimental techniques and computational prediction methods. In order to gain insight into the organization and structure of the resultant large complex networks formed by the interacting molecules, we have developed the versatile Cytoscape plugin NetworkAnalyzer. It computes and displays a comprehensive set of topological parameters, which includes the number of nodes, edges, and connected components, the network diameter, radius, density, centralization, heterogeneity, and clustering coefficient, the characteristic path length, and the distributions of node degrees, neighborhood connectivities, average clustering coefficients, and shortest path lengths. NetworkAnalyzer can be applied to both directed and undirected networks and also contains extra functionality to construct the intersection or union of two networks. It is an interactive and highly customizable application that requires no expert knowledge in graph theory from the user. AVAILABILITY: NetworkAnalyzer can be downloaded via the Cytoscape web site: http://www.cytoscape.org     

HybridFlood: minimizing the effects of redundant messages and maximizing search efficiency of unstructured peer-to-peer networks

Peer-to-peer systems are important Internet applications. A major portion of Internet traffic belongs to such applications. Flooding search is a basic search scheme for unstructured peer-to-peer networks, where a node must send a query message to all its neighbors when seeking a file (in a file sharing situation). Flooding has no knowledge about network topology and files distribution, thus it offers an attractive method for file discovery in dynamic and evolving networks. Although pure flooding can achieve high coverage but it produces exponentially redundant messages in each hop. Consequently, the growth of redundant messages limits system scalability and causes unnecessary traffic in networks. Besides, flooding has no opportunity to get an advantage of node diversity of participating in unstructured P2P networks. To improve this searching scheme and reduce redundant messages, this paper proposes a novel algorithm named HybridFlood. This algorithm is divided into two steps. The first step follows the flooding with a limited number of hops. In the second step, nosey nodes are selected in each searching horizon. The nosey nodes are nodes which have the most links to other nodes. These nodes maintain the data index of all client nodes. We provided analytical studies for flooding and HybridFlood. The analytical results provided the best threshold point of hop for optimum coverage growth rate and redundant messages in flooding. It also proved in HybridFlood broadcasting messages are cut down at least an order of magnitude. Thus, the proposed algorithm extends the search efficiency by reducing redundant messages in each hop. The simulation experiments validated analytical results.     

A novel method of spectral clustering in attributed networks by constructing parameter-free affinity matrix

The most basic and significant issue in complex network analysis is community detection, which is a branch of machine learning. Most current community detection approaches, only consider a network's topology structures, which lose the potential to use node attribute information. In attributed networks, both topological structure and node attributed are important features for community detection. In recent years, the spectral clustering algorithm has received much interest as one of the best performing algorithms in the subcategory of dimensionality reduction. This algorithm applies the eigenvalues of the affinity matrix to map data to low-dimensional space. In the present paper, a new version of the spectral cluster, named Attributed Spectral Clustering (ASC), is applied for attributed graphs that the identified communities have structural cohesiveness and attribute homogeneity. Since the performance of spectral clustering heavily depends on the goodness of the affinity matrix, the ASC algorithm will use the Topological and Attribute Random Walk Affinity Matrix (TARWAM) as a new affinity matrix to calculate the similarity between nodes. TARWAM utilizes the biased random walk to integrate network topology and attribute information. It can improve the similarity degree among the pairs of nodes in the same density region of the attributed network, without the need for parameter tuning. The proposed approach has been compared to other primary and new attributed graph clustering algorithms based on synthetic and real datasets. The experimental results show that the proposed approach is more effective and accurate compared to other state-of-the-art attributed graph clustering techniques.

     

Identification and classification of hubs in brain networks

Brain regions in the mammalian cerebral cortex are linked by a complex network of fiber bundles. These inter-regional networks have previously been analyzed in terms of their node degree, structural motif, path length and clustering coefficient distributions. In this paper we focus on the identification and classification of hub regions, which are thought to play pivotal roles in the coordination of information flow. We identify hubs and characterize their network contributions by examining motif fingerprints and centrality indices for all regions within the cerebral cortices of both the cat and the macaque. Motif fingerprints capture the statistics of local connection patterns, while measures of centrality identify regions that lie on many of the shortest paths between parts of the network. Within both cat and macaque networks, we find that a combination of degree, motif participation, betweenness centrality and closeness centrality allows for reliable identification of hub regions, many of which have previously been functionally classified as polysensory or multimodal. We then classify hubs as either provincial (intra-cluster) hubs or connector (inter-cluster) hubs, and proceed to show that lesioning hubs of each type from the network produces opposite effects on the small-world index. Our study presents an approach to the identification and classification of putative hub regions in brain networks on the basis of multiple network attributes and charts potential links between the structural embedding of such regions and their functional roles.