Complex Network Theory Applied to the Growth of Kuala Lumpur’s Public Urban Rail Transit Network

Recently, the number of studies involving complex network applications in transportation has increased steadily as scholars from various fields analyze traffic networks. Nonetheless, research on rail network growth is relatively rare. This research examines the evolution of the Public Urban Rail Transit Networks of Kuala Lumpur (PURTNoKL) based on complex network theory and covers both the topological structure of the rail system and future trends in network growth. In addition, network performance when facing different attack strategies is also assessed. Three topological network characteristics are considered: connections, clustering and centrality. In PURTNoKL, we found that the total number of nodes and edges exhibit a linear relationship and that the average degree stays within the interval [2.0488, 2.6774] with heavy-tailed distributions. The evolutionary process shows that the cumulative probability distribution (CPD) of degree and the average shortest path length show good fit with exponential distribution and normal distribution, respectively. Moreover, PURTNoKL exhibits clear cluster characteristics; most of the nodes have a 2-core value, and the CPDs of the centrality’s closeness and betweenness follow a normal distribution function and an exponential distribution, respectively. Finally, we discuss four different types of network growth styles and the line extension process, which reveal that the rail network’s growth is likely based on the nodes with the biggest lengths of the shortest path and that network protection should emphasize those nodes with the largest degrees and the highest betweenness values. This research may enhance the networkability of the rail system and better shape the future growth of public rail networks.     

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     

TopNet: a tool for comparing biological sub-networks, correlating protein properties with topological statistics

Biological networks are a topic of great current interest, particularly with the publication of a number of large genome-wide interaction datasets. They are globally characterized by a variety of graph-theoretic statistics, such as the degree distribution, clustering coefficient, characteristic path length and diameter. Moreover, real protein networks are quite complex and can often be divided into many sub-networks through systematic selection of different nodes and edges. For instance, proteins can be sub-divided by expression level, length, amino-acid composition, solubility, secondary structure and function. A challenging research question is to compare the topologies of sub- networks, looking for global differences associated with different types of proteins. TopNet is an automated web tool designed to address this question, calculating and comparing topological characteristics for different sub-networks derived from any given protein network. It provides reasonable solutions to the calculation of network statistics for sub-networks embedded within a larger network and gives simplified views of a sub-network of interest, allowing one to navigate through it. After constructing TopNet, we applied it to the interaction networks and protein classes currently available for yeast. We were able to find a number of potential biological correlations. In particular, we found that soluble proteins had more interactions than membrane proteins. Moreover, amongst soluble proteins, those that were highly expressed, had many polar amino acids, and had many alpha helices, tended to have the most interaction partners. Interestingly, TopNet also turned up some systematic biases in the current yeast interaction network: on average, proteins with a known functional classification had many more interaction partners than those without. This phenomenon may reflect the incompleteness of the experimentally determined yeast interaction network.     

Investigations into the relationship between feedback loops and functional importance of a signal transduction network based on Boolean network modeling

Background  

A number of studies on biological networks have been carried out to unravel the topological characteristics that can explain the functional importance of network nodes. For instance, connectivity, clustering coefficient, and shortest path length were previously proposed for this purpose. However, there is still a pressing need to investigate another topological measure that can better describe the functional importance of network nodes. In this respect, we considered a feedback loop which is ubiquitously found in various biological networks.     

生态工业园共生网络的脆弱性

工业生态系统的稳定可持续运行是生态工业园区实现环境效益、经济效益和社会效益的重要保障,对生态工业共生网络脆弱性分析是工业生态学领域值得探讨的重要问题。运用复杂网络理论,从网络拓扑结构出发,论证该工业园具有小世界性和无标度性,为网络脆弱性分析奠定基础;通过攻击负载最大节点,利用网络效率和最大连通子图对网络的脆弱性进行分析,从而衡量节点失效对整个网络造成的破坏性。指出复杂网络在生态工业园共生网络中进一步研究的方向。     

Discriminating Different Classes of Biological Networks by Analyzing the Graphs Spectra Distribution

The brain''s structural and functional systems, protein-protein interaction, and gene networks are examples of biological systems that share some features of complex networks, such as highly connected nodes, modularity, and small-world topology. Recent studies indicate that some pathologies present topological network alterations relative to norms seen in the general population. Therefore, methods to discriminate the processes that generate the different classes of networks (e.g., normal and disease) might be crucial for the diagnosis, prognosis, and treatment of the disease. It is known that several topological properties of a network (graph) can be described by the distribution of the spectrum of its adjacency matrix. Moreover, large networks generated by the same random process have the same spectrum distribution, allowing us to use it as a “fingerprint”. Based on this relationship, we introduce and propose the entropy of a graph spectrum to measure the “uncertainty” of a random graph and the Kullback-Leibler and Jensen-Shannon divergences between graph spectra to compare networks. We also introduce general methods for model selection and network model parameter estimation, as well as a statistical procedure to test the nullity of divergence between two classes of complex networks. Finally, we demonstrate the usefulness of the proposed methods by applying them to (1) protein-protein interaction networks of different species and (2) on networks derived from children diagnosed with Attention Deficit Hyperactivity Disorder (ADHD) and typically developing children. We conclude that scale-free networks best describe all the protein-protein interactions. Also, we show that our proposed measures succeeded in the identification of topological changes in the network while other commonly used measures (number of edges, clustering coefficient, average path length) failed.     

Topological evolution of coexpression networks by new gene integration maintains the hierarchical and modular structures in human ancestors

We analyze the global structure and evolution of human gene coexpression networks driven by new gene integration. When the Pearson correlation coefficient is greater than or equal to 0.5, we find that the coexpression network consists of 334 small components and one "giant" connected subnet comprising of 6317 interacting genes. This network shows the properties of power-law degree distribution and small-world. The average clustering coefficient of younger genes is larger than that of the elderly genes(0.6685 vs. 0.5762). Particularly, we find that the younger genes with a larger degree also show a property of hierarchical architecture. The younger genes play an important role in the overall pivotability of the network and this network contains few redundant duplicate genes. Moreover, we find that gene duplication and orphan genes are two dominant evolutionary forces in shaping this network. Both the duplicate genes and orphan genes develop new links through a "rich-gets-richer"mechanism. With the gradual integration of new genes into the ancestral network, most of the topological structure features of the network would gradually increase. However, the exponent of degree distribution and modularity coefficient of the whole network do not change significantly, which implies that the evolution of coexpression networks maintains the hierarchical and modular structures in human ancestors.     

残基相互作用网络特征与木聚糖酶耐热性的关系

残基相互作用网络是体现蛋白质中残基与残基之间协同和制约关系的重要形式。残基相互作用网络的拓扑性质以及社团结构与蛋白质的功能和性质有密切的关系。本文在构建一系列耐热木聚糖酶和常温木聚糖酶的残基相互作用网络后,通过计算网络的度、聚类系数、连接强度、特征路径长度、接近中心性、介数中心性等拓扑参数来确定网络拓扑结构与木聚糖酶耐热性的关系。识别残基相互作用网络的hub点,分析hub点的亲疏水性、带电性以及各种氨基酸在hub点中所占的比例。进一步使用GA-Net算法对网络进行社团划分,并计算社团的规模、直径和密度。网络的高平均度、高连接强度、以及更短的最短路径等表明耐热木聚糖酶残基相互作用网络的结构更加紧密;耐热木聚糖酶网络中的hub节点比常温木聚糖酶网络hub节点具有更多的疏水性残基,hub点中Phe、Ile、Val的占比更高。社团检测后发现,耐热木聚糖酶网络拥有更大的社团规模、较小的社团直径和较大的社团密度。社团规模越大表明耐热木聚糖酶的氨基酸残基更倾向于形成大的社团,而较小的社团直径和较大的社团密度则表明社团内部氨基酸残基的相互作用比常温木聚糖酶更强。     

残基相互作用网络特征与木聚糖酶耐热性的关系

残基相互作用网络是体现蛋白质中残基与残基之间协同和制约关系的重要形式。残基相互作用网络的拓扑性质以及社团结构与蛋白质的功能和性质有密切的关系。本文在构建一系列耐热木聚糖酶和常温木聚糖酶的残基相互作用网络后,通过计算网络的度、聚类系数、连接强度、特征路径长度、接近中心性、介数中心性等拓扑参数来确定网络拓扑结构与木聚糖酶耐热性的关系。识别残基相互作用网络的hub点,分析hub点的亲疏水性、带电性以及各种氨基酸在hub点中所占的比例。进一步使用GA-Net算法对网络进行社团划分,并计算社团的规模、直径和密度。网络的高平均度、高连接强度、以及更短的最短路径等表明耐热木聚糖酶残基相互作用网络的结构更加紧密;耐热木聚糖酶网络中的hub节点比常温木聚糖酶网络hub节点具有更多的疏水性残基,hub点中Phe、Ile、Val的占比更高。社团检测后发现,耐热木聚糖酶网络拥有更大的社团规模、较小的社团直径和较大的社团密度。社团规模越大表明耐热木聚糖酶的氨基酸残基更倾向于形成大的社团,而较小的社团直径和较大的社团密度则表明社团内部氨基酸残基的相互作用比常温木聚糖酶更强。     

Brain Network Organization in Focal Epilepsy: A Systematic Review and Meta-Analysis

Normal brain functioning is presumed to depend upon interacting regions within large-scale neuronal networks. Increasing evidence exists that interictal network alterations in focal epilepsy are associated with cognitive and behavioral deficits. Nevertheless, the reported network alterations are inconclusive and prone to low statistical power due to small sample sizes as well as modest effect sizes. We therefore systematically reviewed the existing literature and conducted a meta-analysis to characterize the changes in whole-brain interictal focal epilepsy networks at sufficient power levels. We focused on the two most commonly used metrics in whole-brain networks: average path length and average clustering coefficient. Twelve studies were included that reported whole-brain network average path length and average clustering coefficient characteristics in patients and controls. The overall group difference, quantified as the standardized mean average path length difference between epilepsy and control groups, corresponded to a significantly increased average path length of 0.29 (95% confidence interval (CI): 0.12 to 0.45, p = 0.0007) in the epilepsy group. This suggests a less integrated interictal whole-brain network. Similarly, a significantly increased standardized mean average clustering coefficient of 0.35 (CI: 0.05 to 0.65, p = 0.02) was found in the epilepsy group in comparison with controls, pointing towards a more segregated interictal network. Sub-analyses revealed similar results for functional and structural networks in terms of effect size and directionality for both metrics. In addition, we found individual network studies to be prone to low power due to the relatively small group differences in average path length and average clustering coefficient in combination with small sample sizes. The pooled network characteristics support the hypothesis that focal epilepsy has widespread detrimental effects, that is, reduced integration and increased segregation, on whole brain interictal network organization, which may relate to the co-morbid cognitive and behavioral impairments often reported in patients with focal epilepsy.     

Resilience of protein-protein interaction networks as determined by their large-scale topological features

The relationship between the structure and function of biological networks constitutes a fundamental issue in systems biology. Particularly, the structure of protein-protein interaction networks is related to important biological functions. In this work, we investigated how such a resilience is determined by the large scale features of the respective networks. Four species are taken into account, namely yeast Saccharomyces cerevisiae, worm Caenorhabditis elegans, fly Drosophila melanogaster and Homo sapiens. We adopted two entropy-related measurements (degree entropy and dynamic entropy) in order to quantify the overall degree of robustness of these networks. We verified that while they exhibit similar structural variations under random node removal, they differ significantly when subjected to intentional attacks (hub removal). As a matter of fact, more complex species tended to exhibit more robust networks. More specifically, we quantified how six important measurements of the networks topology (namely clustering coefficient, average degree of neighbors, average shortest path length, diameter, assortativity coefficient, and slope of the power law degree distribution) correlated with the two entropy measurements. Our results revealed that the fraction of hubs and the average neighbor degree contribute significantly for the resilience of networks. In addition, the topological analysis of the removed hubs indicated that the presence of alternative paths between the proteins connected to hubs tend to reinforce resilience. The performed analysis helps to understand how resilience is underlain in networks and can be applied to the development of protein network models.     

Topological structure of the space of phenotypes: the case of RNA neutral networks

The evolution and adaptation of molecular populations is constrained by the diversity accessible through mutational processes. RNA is a paradigmatic example of biopolymer where genotype (sequence) and phenotype (approximated by the secondary structure fold) are identified in a single molecule. The extreme redundancy of the genotype-phenotype map leads to large ensembles of RNA sequences that fold into the same secondary structure and can be connected through single-point mutations. These ensembles define neutral networks of phenotypes in sequence space. Here we analyze the topological properties of neutral networks formed by 12-nucleotides RNA sequences, obtained through the exhaustive folding of sequence space. A total of 4(12) sequences fragments into 645 subnetworks that correspond to 57 different secondary structures. The topological analysis reveals that each subnetwork is far from being random: it has a degree distribution with a well-defined average and a small dispersion, a high clustering coefficient, and an average shortest path between nodes close to its minimum possible value, i.e. the Hamming distance between sequences. RNA neutral networks are assortative due to the correlation in the composition of neighboring sequences, a feature that together with the symmetries inherent to the folding process explains the existence of communities. Several topological relationships can be analytically derived attending to structural restrictions and generic properties of the folding process. The average degree of these phenotypic networks grows logarithmically with their size, such that abundant phenotypes have the additional advantage of being more robust to mutations. This property prevents fragmentation of neutral networks and thus enhances the navigability of sequence space. In summary, RNA neutral networks show unique topological properties, unknown to other networks previously described.     

Incidental and Intentional Learning of Verbal Episodic Material Differentially Modifies Functional Brain Networks

Learning- and memory-related processes are thought to result from dynamic interactions in large-scale brain networks that include lateral and mesial structures of the temporal lobes. We investigate the impact of incidental and intentional learning of verbal episodic material on functional brain networks that we derive from scalp-EEG recorded continuously from 33 subjects during a neuropsychological test schedule. Analyzing the networks'' global statistical properties we observe that intentional but not incidental learning leads to a significantly increased clustering coefficient, and the average shortest path length remains unaffected. Moreover, network modifications correlate with subsequent recall performance: the more pronounced the modifications of the clustering coefficient, the higher the recall performance. Our findings provide novel insights into the relationship between topological aspects of functional brain networks and higher cognitive functions.     

Evolution Characteristics of the Network Core in the Facebook

Statistical properties of the static networks have been extensively studied. However, online social networks are evolving dynamically, understanding the evolving characteristics of the core is one of major concerns in online social networks. In this paper, we empirically investigate the evolving characteristics of the Facebook core. Firstly, we separate the Facebook-link(FL) and Facebook-wall(FW) datasets into 28 snapshots in terms of timestamps. By employing the k-core decomposition method to identify the core of each snapshot, we find that the core sizes of the FL and FW networks approximately contain about 672 and 373 nodes regardless of the exponential growth of the network sizes. Secondly, we analyze evolving topological properties of the core, including the k-core value, assortative coefficient, clustering coefficient and the average shortest path length. Empirical results show that nodes in the core are getting more interconnected in the evolving process. Thirdly, we investigate the life span of nodes belonging to the core. More than 50% nodes stay in the core for more than one year, and 19% nodes always stay in the core from the first snapshot. Finally, we analyze the connections between the core and the whole network, and find that nodes belonging to the core prefer to connect nodes with high k-core values, rather than the high degrees ones. This work could provide new insights into the online social network analysis.     

Biological Motion Coding in the Brain: Analysis of Visually Driven EEG Functional Networks

Herein, we address the time evolution of brain functional networks computed from electroencephalographic activity driven by visual stimuli. We describe how these functional network signatures change in fast scale when confronted with point-light display stimuli depicting biological motion (BM) as opposed to scrambled motion (SM). Whereas global network measures (average path length, average clustering coefficient, and average betweenness) computed as a function of time did not discriminate between BM and SM, local node properties did. Comparing the network local measures of the BM condition with those of the SM condition, we found higher degree and betweenness values in the left frontal (F7) electrode, as well as a higher clustering coefficient in the right occipital (O2) electrode, for the SM condition. Conversely, for the BM condition, we found higher degree values in central parietal (Pz) electrode and a higher clustering coefficient in the left parietal (P3) electrode. These results are discussed in the context of the brain networks involved in encoding BM versus SM.     

Failure tolerance of motif structure in biological networks

Complex networks serve as generic models for many biological systems that have been shown to share a number of common structural properties such as power-law degree distribution and small-worldness. Real-world networks are composed of building blocks called motifs that are indeed specific subgraphs of (usually) small number of nodes. Network motifs are important in the functionality of complex networks, and the role of some motifs such as feed-forward loop in many biological networks has been heavily studied. On the other hand, many biological networks have shown some degrees of robustness in terms of their efficiency and connectedness against failures in their components. In this paper we investigated how random and systematic failures in the edges of biological networks influenced their motif structure. We considered two biological networks, namely, protein structure network and human brain functional network. Furthermore, we considered random failures as well as systematic failures based on different strategies for choosing candidate edges for removal. Failure in the edges tipping to high degree nodes had the most destructive role in the motif structure of the networks by decreasing their significance level, while removing edges that were connected to nodes with high values of betweenness centrality had the least effect on the significance profiles. In some cases, the latter caused increase in the significance levels of the motifs.     

Biological network comparison using graphlet degree distribution

MOTIVATION: Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. RESULTS: We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes 'touching' k edges, into distributions measuring the number of nodes 'touching' k graphlets, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 graphlet degree distributions of graphlets with 2-5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network 'agreement' measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erd?s-Rény, random scale-free, or Barabási-Albert scale-free networks. AVAILABILITY: Software executables are available upon request.     

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.     

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.