Network theory analysis of antibody-antigen reactivity data: the immune trees at birth and adulthood

MOTIVATION: New antigen microarray technology enables parallel recording of antibody reactivities with hundreds of antigens. Such data affords system level analysis of the immune system's organization using methods and approaches from network theory. Here we measured the reactivity of 290 antigens (for both the IgG and IgM isotypes) of 10 healthy mothers and their term newborns. We constructed antigen correlation networks (or immune networks) whose nodes are the antigens and the edges are the antigen-antigen reactivity correlations, and we also computed their corresponding minimum spanning trees (MST)--maximal information reduced sub-graphs. We quantify the network organization (topology) in terms of the network theory divergence rate measure and rank the antigen importance in the full antigen correlation networks by the eigen-value centrality measure. This analysis makes possible the characterization and comparison of the IgG and IgM immune networks at birth (newborns) and adulthood (mothers) in terms of topology and node importance. RESULTS: Comparison of the immune network topology at birth and adulthood revealed partial conservation of the IgG immune network topology, and significant reorganization of the IgM immune networks. Inspection of the antigen importance revealed some dominant (in terms of high centrality) antigens in the IgG and IgM networks at birth, which retain their importance at adulthood.     

Towards a Methodology for Validation of Centrality Measures in Complex Networks

Background

Living systems are associated with Social networks — networks made up of nodes, some of which may be more important in various aspects as compared to others. While different quantitative measures labeled as “centralities” have previously been used in the network analysis community to find out influential nodes in a network, it is debatable how valid the centrality measures actually are. In other words, the research question that remains unanswered is: how exactly do these measures perform in the real world? So, as an example, if a centrality of a particular node identifies it to be important, is the node actually important?

Purpose

The goal of this paper is not just to perform a traditional social network analysis but rather to evaluate different centrality measures by conducting an empirical study analyzing exactly how do network centralities correlate with data from published multidisciplinary network data sets.

Method

We take standard published network data sets while using a random network to establish a baseline. These data sets included the Zachary''s Karate Club network, dolphin social network and a neural network of nematode Caenorhabditis elegans. Each of the data sets was analyzed in terms of different centrality measures and compared with existing knowledge from associated published articles to review the role of each centrality measure in the determination of influential nodes.

Results

Our empirical analysis demonstrates that in the chosen network data sets, nodes which had a high Closeness Centrality also had a high Eccentricity Centrality. Likewise high Degree Centrality also correlated closely with a high Eigenvector Centrality. Whereas Betweenness Centrality varied according to network topology and did not demonstrate any noticeable pattern. In terms of identification of key nodes, we discovered that as compared with other centrality measures, Eigenvector and Eccentricity Centralities were better able to identify important nodes.     

Making Large-Scale Networks from fMRI Data

Pairwise correlations are currently a popular way to estimate a large-scale network (> 1000 nodes) from functional magnetic resonance imaging data. However, this approach generally results in a poor representation of the true underlying network. The reason is that pairwise correlations cannot distinguish between direct and indirect connectivity. As a result, pairwise correlation networks can lead to fallacious conclusions; for example, one may conclude that a network is a small-world when it is not. In a simulation study and an application to resting-state fMRI data, we compare the performance of pairwise correlations in large-scale networks (2000 nodes) against three other methods that are designed to filter out indirect connections. Recovery methods are evaluated in four simulated network topologies (small world or not, scale-free or not) in scenarios where the number of observations is very small compared to the number of nodes. Simulations clearly show that pairwise correlation networks are fragmented into separate unconnected components with excessive connectedness within components. This often leads to erroneous estimates of network metrics, like small-world structures or low betweenness centrality, and produces too many low-degree nodes. We conclude that using partial correlations, informed by a sparseness penalty, results in more accurate networks and corresponding metrics than pairwise correlation networks. However, even with these methods, the presence of hubs in the generating network can be problematic if the number of observations is too small. Additionally, we show for resting-state fMRI that partial correlations are more robust than correlations to different parcellation sets and to different lengths of time-series.     

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.     

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.     

Characterization of topological keystone species: Local,global and “meso-scale” centralities in food webs

An important question in the network representation of ecological systems is to determine how direct and indirect interactions between species determine the positional importance of species in the ecosystem. Here we present a quantitative analysis of the similarities and differences of six different topological centrality measures as indicators of keystone species in 17 food webs. These indicators account for local, global and “meso-scale” – intermediate between local and global – topological information about species in the food webs. Using factor analysis we shown that most of these centrality indices share a great deal of topological information, which range from 75% to 96%. A generalized keystone indicator is then proposed by considering the factor loadings of the six-centrality measures, which contains most of the information encoded by these indices. However, the individual ordering of species according to these criteria display significant differences in most food webs. We simulate the effects of species extinction by removing species ranked according to a local and a “meso-scale” centrality indicator. The differences observed on three network characteristics – size, average distance and clustering coefficient of the largest component – after the removal of the most central nodes indicate that the consideration of these indices have different impacts for the ranking of species with conservational biology purposes. The “meso-scale” indicator appears to play an important role in determining the relative importance of species in epidemic spread and parasitism rates.     

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.     

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.     

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.     

Topological Strata of Weighted Complex Networks

The statistical mechanical approach to complex networks is the dominant paradigm in describing natural and societal complex systems. The study of network properties, and their implications on dynamical processes, mostly focus on locally defined quantities of nodes and edges, such as node degrees, edge weights and –more recently– correlations between neighboring nodes. However, statistical methods quickly become cumbersome when dealing with many-body properties and do not capture the precise mesoscopic structure of complex networks. Here we introduce a novel method, based on persistent homology, to detect particular non-local structures, akin to weighted holes within the link-weight network fabric, which are invisible to existing methods. Their properties divide weighted networks in two broad classes: one is characterized by small hierarchically nested holes, while the second displays larger and longer living inhomogeneities. These classes cannot be reduced to known local or quasilocal network properties, because of the intrinsic non-locality of homological properties, and thus yield a new classification built on high order coordination patterns. Our results show that topology can provide novel insights relevant for many-body interactions in social and spatial networks. Moreover, this new method creates the first bridge between network theory and algebraic topology, which will allow to import the toolset of algebraic methods to complex systems.     

Interdependent Multi-Layer Networks: Modeling and Survivability Analysis with Applications to Space-Based Networks

This article develops a novel approach and algorithmic tools for the modeling and survivability analysis of networks with heterogeneous nodes, and examines their application to space-based networks. Space-based networks (SBNs) allow the sharing of spacecraft on-orbit resources, such as data storage, processing, and downlink. Each spacecraft in the network can have different subsystem composition and functionality, thus resulting in node heterogeneity. Most traditional survivability analyses of networks assume node homogeneity and as a result, are not suited for the analysis of SBNs. This work proposes that heterogeneous networks can be modeled as interdependent multi-layer networks, which enables their survivability analysis. The multi-layer aspect captures the breakdown of the network according to common functionalities across the different nodes, and it allows the emergence of homogeneous sub-networks, while the interdependency aspect constrains the network to capture the physical characteristics of each node. Definitions of primitives of failure propagation are devised. Formal characterization of interdependent multi-layer networks, as well as algorithmic tools for the analysis of failure propagation across the network are developed and illustrated with space applications. The SBN applications considered consist of several networked spacecraft that can tap into each other''s Command and Data Handling subsystem, in case of failure of its own, including the Telemetry, Tracking and Command, the Control Processor, and the Data Handling sub-subsystems. Various design insights are derived and discussed, and the capability to perform trade-space analysis with the proposed approach for various network characteristics is indicated. The select results here shown quantify the incremental survivability gains (with respect to a particular class of threats) of the SBN over the traditional monolith spacecraft. Failure of the connectivity between nodes is also examined, and the results highlight the importance of the reliability of the wireless links between spacecraft (nodes) to enable any survivability improvements for space-based networks.     

Connectivity,reproduction number,and mobility interact to determine communities’ epidemiological superspreader potential in a metapopulation network

Disease epidemic outbreaks on human metapopulation networks are often driven by a small number of superspreader nodes, which are primarily responsible for spreading the disease throughout the network. Superspreader nodes typically are characterized either by their locations within the network, by their degree of connectivity and centrality, or by their habitat suitability for the disease, described by their reproduction number (R). Here we introduce a model that considers simultaneously the effects of network properties and R on superspreaders, as opposed to previous research which considered each factor separately. This type of model is applicable to diseases for which habitat suitability varies by climate or land cover, and for direct transmitted diseases for which population density and mitigation practices influences R. We present analytical models that quantify the superspreader capacity of a population node by two measures: probability-dependent superspreader capacity, the expected number of neighboring nodes to which the node in consideration will randomly spread the disease per epidemic generation, and time-dependent superspreader capacity, the rate at which the node spreads the disease to each of its neighbors. We validate our analytical models with a Monte Carlo analysis of repeated stochastic Susceptible-Infected-Recovered (SIR) simulations on randomly generated human population networks, and we use a random forest statistical model to relate superspreader risk to connectivity, R, centrality, clustering, and diffusion. We demonstrate that either degree of connectivity or R above a certain threshold are sufficient conditions for a node to have a moderate superspreader risk factor, but both are necessary for a node to have a high-risk factor. The statistical model presented in this article can be used to predict the location of superspreader events in future epidemics, and to predict the effectiveness of mitigation strategies that seek to reduce the value of R, alter host movements, or both.     

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.

     

Eigenvector Centrality Mapping for Analyzing Connectivity Patterns in fMRI Data of the Human Brain

Functional magnetic resonance data acquired in a task-absent condition (“resting state”) require new data analysis techniques that do not depend on an activation model. In this work, we introduce an alternative assumption- and parameter-free method based on a particular form of node centrality called eigenvector centrality. Eigenvector centrality attributes a value to each voxel in the brain such that a voxel receives a large value if it is strongly correlated with many other nodes that are themselves central within the network. Google''s PageRank algorithm is a variant of eigenvector centrality. Thus far, other centrality measures - in particular “betweenness centrality” - have been applied to fMRI data using a pre-selected set of nodes consisting of several hundred elements. Eigenvector centrality is computationally much more efficient than betweenness centrality and does not require thresholding of similarity values so that it can be applied to thousands of voxels in a region of interest covering the entire cerebrum which would have been infeasible using betweenness centrality. Eigenvector centrality can be used on a variety of different similarity metrics. Here, we present applications based on linear correlations and on spectral coherences between fMRI times series. This latter approach allows us to draw conclusions of connectivity patterns in different spectral bands. We apply this method to fMRI data in task-absent conditions where subjects were in states of hunger or satiety. We show that eigenvector centrality is modulated by the state that the subjects were in. Our analyses demonstrate that eigenvector centrality is a computationally efficient tool for capturing intrinsic neural architecture on a voxel-wise level.     

A network perspective on the topological importance of enzymes and their phylogenetic conservation

Background  

A metabolic network is the sum of all chemical transformations or reactions in the cell, with the metabolites being interconnected by enzyme-catalyzed reactions. Many enzymes exist in numerous species while others occur only in a few. We ask if there are relationships between the phylogenetic profile of an enzyme, or the number of different bacterial species that contain it, and its topological importance in the metabolic network. Our null hypothesis is that phylogenetic profile is independent of topological importance. To test our null hypothesis we constructed an enzyme network from the KEGG (Kyoto Encyclopedia of Genes and Genomes) database. We calculated three network indices of topological importance: the degree or the number of connections of a network node; closeness centrality, which measures how close a node is to others; and betweenness centrality measuring how frequently a node appears on all shortest paths between two other nodes.     

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.