Control Centrality and Hierarchical Structure in Complex Networks

We introduce the concept of control centrality to quantify the ability of a single node to control a directed weighted network. We calculate the distribution of control centrality for several real networks and find that it is mainly determined by the network’s degree distribution. We show that in a directed network without loops the control centrality of a node is uniquely determined by its layer index or topological position in the underlying hierarchical structure of the network. Inspired by the deep relation between control centrality and hierarchical structure in a general directed network, we design an efficient attack strategy against the controllability of malicious networks.     

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.     

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.     

Preserved Modular Network Organization in the Sedated Rat Brain

Translation of resting-state functional connectivity (FC) magnetic resonance imaging (rs-fMRI) applications from human to rodents has experienced growing interest, and bears a great potential in pre-clinical imaging as it enables assessing non-invasively the topological organization of complex FC networks (FCNs) in rodent models under normal and various pathophysiological conditions. However, to date, little is known about the organizational architecture of FCNs in rodents in a mentally healthy state, although an understanding of the same is of paramount importance before investigating networks under compromised states. In this study, we characterized the properties of resting-state FCN in an extensive number of Sprague-Dawley rats (n = 40) under medetomidine sedation by evaluating its modular organization and centrality of brain regions and tested for reproducibility. Fully-connected large-scale complex networks of positively and negatively weighted connections were constructed based on Pearson partial correlation analysis between the time courses of 36 brain regions encompassing almost the entire brain. Applying recently proposed complex network analysis measures, we show that the rat FCN exhibits a modular architecture, comprising six modules with a high between subject reproducibility. In addition, we identified network hubs with strong connections to diverse brain regions. Overall our results obtained under a straight medetomidine protocol show for the first time that the community structure of the rat brain is preserved under pharmacologically induced sedation with a network modularity contrasting from the one reported for deep anesthesia but closely resembles the organization described for the rat in conscious state.     

Relevance of intra-hospital patient movements for the spread of healthcare-associated infections within hospitals - a mathematical modeling study

The aim of this study is to analyze patient movement patterns between hospital departments to derive the underlying intra-hospital movement network, and to assess if movement patterns differ between patients at high or low risk of colonization. For that purpose, we analyzed patient electronic medical record data from five hospitals to extract information on risk stratification and patient intra-hospital movements. Movement patterns were visualized as networks, and network centrality measures were calculated. Next, using an agent-based model where agents represent patients and intra-hospital patient movements were explicitly modeled, we simulated the spread of multidrug resistant enterobacteriacae (MDR-E) inside a hospital. Risk stratification of patients according to certain ICD-10 codes revealed that length of stay, patient age, and mean number of movements per admission were higher in the high-risk groups. Movement networks in all hospitals displayed a high variability among departments concerning their network centrality and connectedness with a few highly connected departments and many weakly connected peripheral departments. Simulating the spread of a pathogen in one hospital network showed positive correlation between department prevalence and network centrality measures. This study highlights the importance of intra-hospital patient movements and their possible impact on pathogen spread. Targeting interventions to departments of higher (weighted) degree may help to control the spread of MDR-E. Moreover, when the colonization status of patients coming from different departments is unknown, a ranking system based on department centralities may be used to design more effective interventions that mitigate pathogen spread.     

Role of Cattle Movements in Bovine Tuberculosis Spread in France between 2005 and 2014

Live animal movements are a major transmission route for the spread of infectious agents such as Mycobacterium bovis, the main agent of bovine Tuberculosis (bTB). France became officially bTB-free in 2001, but M. bovis is still circulating in the cattle population, with about a hundred of outbreaks per year, most located in a few geographic areas. The aim of this study was to analyse the role of cattle movements in bTB spread in France between 2005 and 2014, using social network analysis and logistic regression models. At a global scale, the trade network was studied to assess the association between several centrality measures and bTB infection though a case-control analysis. The bTB infection status was associated with a higher in-degree (odds-ratio [OR] = 2.4 [1.1–5.4]) and with a higher ingoing contact chain (OR = 2.2 [1.0–4.7]). At a more local scale, a second case-control analysis was conducted to estimate the relative importance of cattle movements and spatial neighbourhood. Only direct purchase from infected herds was shown to be associated with bTB infection (OR = 2.9 [1.7–5.2]), spatial proximity to infected herds being the predominant risk factor, with decreasing ORs when distance increases. Indeed, the population attributable fraction was 12% [5%–18%] for cattle movements and 73% [68%–78%] for spatial neighbourhood. Based on these results, networks of potential effective contacts between herds were built and analysed for the three major spoligotypes reported in France. In these networks, the links representing cattle movements were associated with higher edge betweenness than those representing the spatial proximity between infected herds. They were often links connecting distinct communities and sometimes distinct geographical areas. Therefore, although their role was quantitatively lower than the one of spatial neighbourhood, cattle movements appear to have been essential in the French bTB dynamics between 2005 and 2014.     

Neural Network of Body Representation Differs between Transsexuals and Cissexuals

Body image is the internal representation of an individual’s own physical appearance. Individuals with gender identity disorder (GID), commonly referred to as transsexuals (TXs), are unable to form a satisfactory body image due to the dissonance between their biological sex and gender identity. We reasoned that changes in the resting-state functional connectivity (rsFC) network would neurologically reflect such experiential incongruence in TXs. Using graph theory-based network analysis, we investigated the regional changes of the degree centrality of the rsFC network. The degree centrality is an index of the functional importance of a node in a neural network. We hypothesized that three key regions of the body representation network, i.e., the primary somatosensory cortex, the superior parietal lobule and the insula, would show a higher degree centrality in TXs. Twenty-three pre-treatment TXs (11 male-to-female and 12 female-to-male TXs) as one psychosocial group and 23 age-matched healthy cissexual control subjects (CISs, 11 males and 12 females) were recruited. Resting-state functional magnetic resonance imaging was performed, and binarized rsFC networks were constructed. The TXs demonstrated a significantly higher degree centrality in the bilateral superior parietal lobule and the primary somatosensory cortex. In addition, the connectivity between the right insula and the bilateral primary somatosensory cortices was negatively correlated with the selfness rating of their desired genders. These data indicate that the key components of body representation manifest in TXs as critical function hubs in the rsFC network. The negative association may imply a coping mechanism that dissociates bodily emotion from body image. The changes in the functional connectome may serve as representational markers for the dysphoric bodily self of TXs.     

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

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

Evolutionary and Topological Properties of Genes and Community Structures in Human Gene Regulatory Networks

The diverse, specialized genes present in today’s lifeforms evolved from a common core of ancient, elementary genes. However, these genes did not evolve individually: gene expression is controlled by a complex network of interactions, and alterations in one gene may drive reciprocal changes in its proteins’ binding partners. Like many complex networks, these gene regulatory networks (GRNs) are composed of communities, or clusters of genes with relatively high connectivity. A deep understanding of the relationship between the evolutionary history of single genes and the topological properties of the underlying GRN is integral to evolutionary genetics. Here, we show that the topological properties of an acute myeloid leukemia GRN and a general human GRN are strongly coupled with its genes’ evolutionary properties. Slowly evolving (“cold”), old genes tend to interact with each other, as do rapidly evolving (“hot”), young genes. This naturally causes genes to segregate into community structures with relatively homogeneous evolutionary histories. We argue that gene duplication placed old, cold genes and communities at the center of the networks, and young, hot genes and communities at the periphery. We demonstrate this with single-node centrality measures and two new measures of efficiency, the set efficiency and the interset efficiency. We conclude that these methods for studying the relationships between a GRN’s community structures and its genes’ evolutionary properties provide new perspectives for understanding evolutionary genetics.     

Network Effects on Scientific Collaborations

Background

The analysis of co-authorship network aims at exploring the impact of network structure on the outcome of scientific collaborations and research publications. However, little is known about what network properties are associated with authors who have increased number of joint publications and are being cited highly.

Methodology/Principal Findings

Measures of social network analysis, for example network centrality and tie strength, have been utilized extensively in current co-authorship literature to explore different behavioural patterns of co-authorship networks. Using three SNA measures (i.e., degree centrality, closeness centrality and betweenness centrality), we explore scientific collaboration networks to understand factors influencing performance (i.e., citation count) and formation (tie strength between authors) of such networks. A citation count is the number of times an article is cited by other articles. We use co-authorship dataset of the research field of ‘steel structure’ for the year 2005 to 2009. To measure the strength of scientific collaboration between two authors, we consider the number of articles co-authored by them. In this study, we examine how citation count of a scientific publication is influenced by different centrality measures of its co-author(s) in a co-authorship network. We further analyze the impact of the network positions of authors on the strength of their scientific collaborations. We use both correlation and regression methods for data analysis leading to statistical validation. We identify that citation count of a research article is positively correlated with the degree centrality and betweenness centrality values of its co-author(s). Also, we reveal that degree centrality and betweenness centrality values of authors in a co-authorship network are positively correlated with the strength of their scientific collaborations.

Conclusions/Significance

Authors’ network positions in co-authorship networks influence the performance (i.e., citation count) and formation (i.e., tie strength) of scientific collaborations.     

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.     

Basketball Teams as Strategic Networks

We asked how team dynamics can be captured in relation to function by considering games in the first round of the NBA 2010 play-offs as networks. Defining players as nodes and ball movements as links, we analyzed the network properties of degree centrality, clustering, entropy and flow centrality across teams and positions, to characterize the game from a network perspective and to determine whether we can assess differences in team offensive strategy by their network properties. The compiled network structure across teams reflected a fundamental attribute of basketball strategy. They primarily showed a centralized ball distribution pattern with the point guard in a leadership role. However, individual play-off teams showed variation in their relative involvement of other players/positions in ball distribution, reflected quantitatively by differences in clustering and degree centrality. We also characterized two potential alternate offensive strategies by associated variation in network structure: (1) whether teams consistently moved the ball towards their shooting specialists, measured as “uphill/downhill” flux, and (2) whether they distributed the ball in a way that reduced predictability, measured as team entropy. These network metrics quantified different aspects of team strategy, with no single metric wholly predictive of success. However, in the context of the 2010 play-offs, the values of clustering (connectedness across players) and network entropy (unpredictability of ball movement) had the most consistent association with team advancement. Our analyses demonstrate the utility of network approaches in quantifying team strategy and show that testable hypotheses can be evaluated using this approach. These analyses also highlight the richness of basketball networks as a dataset for exploring the relationships between network structure and dynamics with team organization and effectiveness.     

Influence of APOE Genotype on Whole-Brain Functional Networks in Cognitively Normal Elderly

This study aimed to investigate the influence of apolipoprotein E (APOE) ε4 allele on whole-brain functional networks in cognitively normal (CN) elderly by applying graph theoretical analysis to brain glucose metabolism. Eighty-six CN elderly [28 APOE ε4 carriers (ε4+) and 58 non-carriers (ε4-)] underwent clinical evaluation and resting [¹⁸F] fluorodeoxyglucose positron emission tomography scan. Whole-brain functional networks were constructed from correlations of the 90 regions of interest using the automated anatomical labeling template, and analyzed using graph theoretical approaches. The overall small-world property seen in ε4- was preserved in ε4+. However, both local clustering and path length were lower in ε4+ compared to ε4-. In terms of the hubs of functional networks, ε4+ showed decreased centrality of the right hippocampus but increased centrality of several brain regions associated with the default mode network compared to ε4-. Our results indicate that genetic vulnerability to Alzheimer’s disease may alter whole-brain functional networks even before clinical symptoms appear.     

A Graph Theoretical Approach to Study the Organization of the Cortical Networks during Different Mathematical Tasks

The two core systems of mathematical processing (subitizing and retrieval) as well as their functionality are already known and published. In this study we have used graph theory to compare the brain network organization of these two core systems in the cortical layer during difficult calculations. We have examined separately all the EEG frequency bands in healthy young individuals and we found that the network organization at rest, as well as during mathematical tasks has the characteristics of Small World Networks for all the bands, which is the optimum organization required for efficient information processing. The different mathematical stimuli provoked changes in the graph parameters of different frequency bands, especially the low frequency bands. More specific, in Delta band the induced network increases it’s local and global efficiency during the transition from subitizing to retrieval system, while results suggest that difficult mathematics provoke networks with higher cliquish organization due to more specific demands. The network of the Theta band follows the same pattern as before, having high nodal and remote organization during difficult mathematics. Also the spatial distribution of the network’s weights revealed more prominent connections in frontoparietal regions, revealing the working memory load due to the engagement of the retrieval system. The cortical networks of the alpha brainwaves were also more efficient, both locally and globally, during difficult mathematics, while the fact that alpha’s network was more dense on the frontparietal regions as well, reveals the engagement of the retrieval system again. Concluding, this study gives more evidences regarding the interaction of the two core systems, exploiting the produced functional networks of the cerebral cortex, especially for the difficult mathematics.     

The Role of Community Mixing Styles in Shaping Epidemic Behaviors in Weighted Networks

The dynamics of infectious diseases that are spread through direct contact have been proven to depend on the strength of community structure or modularity within the underlying network. It has been recently shown that weighted networks with similar modularity values may exhibit different mixing styles regarding the number of connections among communities and their respective weights. However, the effect of mixing style on epidemic behavior was still unclear. In this paper, we simulate the spread of disease within networks with different mixing styles: a dense-weak style (i.e., many edges among the communities with small weights) and a sparse-strong style (i.e., a few edges among the communities with large weights). Simulation results show that, with the same modularity: 1) the mixing style significantly influences the epidemic size, speed, pattern and immunization strategy; 2) the increase of the number of communities amplifies the effect of the mixing style; 3) when the mixing style changes from sparse-strong to dense-weak, there is a ‘saturation point’, after which the epidemic size and pattern become stable. We also provide a mean-field solution of the epidemic threshold and size on weighted community networks with arbitrary external and internal degree distribution. The solution explains the effect of the second moment of the degree distribution, and a symmetric effect of internal and external connections (incl. degree distribution and weight). Our study has both potential significance for designing more accurate metrics for the community structure and exploring diffusion dynamics on metapopulation networks.     

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.     

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.     

The organisational structure of protein networks: revisiting the centrality–lethality hypothesis

Protein networks, describing physical interactions as well as functional associations between proteins, have been unravelled for many organisms in the recent past. Databases such as the STRING provide excellent resources for the analysis of such networks. In this contribution, we revisit the organisation of protein networks, particularly the centrality–lethality hypothesis, which hypothesises that nodes with higher centrality in a network are more likely to produce lethal phenotypes on removal, compared to nodes with lower centrality. We consider the protein networks of a diverse set of 20 organisms, with essentiality information available in the Database of Essential Genes and assess the relationship between centrality measures and lethality. For each of these organisms, we obtained networks of high-confidence interactions from the STRING database, and computed network parameters such as degree, betweenness centrality, closeness centrality and pairwise disconnectivity indices. We observe that the networks considered here are predominantly disassortative. Further, we observe that essential nodes in a network have a significantly higher average degree and betweenness centrality, compared to the network average. Most previous studies have evaluated the centrality–lethality hypothesis for Saccharomyces cerevisiae and Escherichia coli; we here observe that the centrality–lethality hypothesis hold goods for a large number of organisms, with certain limitations. Betweenness centrality may also be a useful measure to identify essential nodes, but measures like closeness centrality and pairwise disconnectivity are not significantly higher for essential nodes.     

Yeast Protein Interactome topology provides framework for coordinated-functionality

The architecture of the network of protein–protein physical interactions in Saccharomyces cerevisiae is exposed through the combination of two complementary theoretical network measures, betweenness centrality and ‘Q-modularity’. The yeast interactome is characterized by well-defined topological modules connected via a small number of inter-module protein interactions. Should such topological inter-module connections turn out to constitute a form of functional coordination between the modules, we speculate that this coordination is occurring typically in a pairwise fashion, rather than by way of high-degree hub proteins responsible for coordinating multiple modules. The unique non-hub-centric hierarchical organization of the interactome is not reproduced by gene duplication-and-divergence stochastic growth models that disregard global selective pressures.