Fast Fragmentation of Networks Using Module-Based Attacks.
ABSTRACT: In the multidisciplinary field of Network Science, optimization of procedures for efficiently breaking complex networks is attracting much attention from a practical point of view. In this contribution, we present a module-based method to efficiently fragment complex networks. The procedure firstly identifies topological communities through which the network can be represented using a well established heuristic algorithm of community finding. Then only the nodes that participate of inter-community links are removed in descending order of their betweenness centrality. We illustrate the method by applying it to a variety of examples in the social, infrastructure, and biological fields. It is shown that the module-based approach always outperforms targeted attacks to vertices based on node degree or betweenness centrality rankings, with gains in efficiency strongly related to the modularity of the network. Remarkably, in the US power grid case, by deleting 3% of the nodes, the proposed method breaks the original network in fragments which are twenty times smaller in size than the fragments left by betweenness-based attack.
Project description:Identifying driver genes that contribute to cancer progression from numerous passenger genes, although a central goal, is a major challenge. The protein-protein interaction network provides convenient and reasonable assistance for driver gene discovery. Random walk-based methods have been widely used to prioritize nodes in social or biological networks. However, most studies select the next arriving node uniformly from the random walker's neighbors. Few consider transiting preference according to the degree of random walker's neighbors. In this study, based on the random walk method, we propose a novel approach named Driver_IRW (Driver genes discovery with Improved Random Walk method), to prioritize cancer genes in cancer-related network. The key idea of Driver_IRW is to assign different transition probabilities for different edges of a constructed cancer-related network in accordance with the degree of the nodes' neighbors. Furthermore, the global centrality (here is betweenness centrality) and Katz feedback centrality are incorporated into the framework to evaluate the probability to walk to the seed nodes. Experimental results on four cancer types indicate that Driver_IRW performs more efficiently than some previously published methods for uncovering known cancer-related genes. In conclusion, our method can aid in prioritizing cancer-related genes and complement traditional frequency and network-based methods.
Project description:Recent developments in network theory have allowed for the study of the structure and function of the human brain in terms of a network of interconnected components. Among the many nodes that form a network, some play a crucial role and are said to be central within the network structure. Central nodes may be identified via centrality metrics, with degree, betweenness, and eigenvector centrality being three of the most popular measures. Degree identifies the most connected nodes, whereas betweenness centrality identifies those located on the most traveled paths. Eigenvector centrality considers nodes connected to other high degree nodes as highly central. In the work presented here, we propose a new centrality metric called leverage centrality that considers the extent of connectivity of a node relative to the connectivity of its neighbors. The leverage centrality of a node in a network is determined by the extent to which its immediate neighbors rely on that node for information. Although similar in concept, there are essential differences between eigenvector and leverage centrality that are discussed in this manuscript. Degree, betweenness, eigenvector, and leverage centrality were compared using functional brain networks generated from healthy volunteers. Functional cartography was also used to identify neighborhood hubs (nodes with high degree within a network neighborhood). Provincial hubs provide structure within the local community, and connector hubs mediate connections between multiple communities. Leverage proved to yield information that was not captured by degree, betweenness, or eigenvector centrality and was more accurate at identifying neighborhood hubs. We propose that this metric may be able to identify critical nodes that are highly influential within the network.
Project description: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.
Project description:It is a classic topic of social network analysis to evaluate the importance of nodes and identify the node that takes on the role of core or bridge in a network. Because a single indicator is not sufficient to analyze multiple characteristics of a node, it is a natural solution to apply multiple indicators that should be selected carefully. An intuitive idea is to select some indicators with weak correlations to efficiently assess different characteristics of a node. However, this paper shows that it is much better to select the indicators with strong correlations. Because indicator correlation is based on the statistical analysis of a large number of nodes, the particularity of an important node will be outlined if its indicator relationship doesn't comply with the statistical correlation. Therefore, the paper selects the multiple indicators including degree, ego-betweenness centrality and eigenvector centrality to evaluate the importance and the role of a node. The importance of a node is equal to the normalized sum of its three indicators. A candidate for core or bridge is selected from the great degree nodes or the nodes with great ego-betweenness centrality respectively. Then, the role of a candidate is determined according to the difference between its indicators' relationship with the statistical correlation of the overall network. Based on 18 real networks and 3 kinds of model networks, the experimental results show that the proposed methods perform quite well in evaluating the importance of nodes and in identifying the node role.
Project description:Degree centrality is a widely used measure in complex networks. Within the brain, degree relates to other topological features, with high-degree nodes (i.e., hubs) exhibiting high betweenness centrality, participation coefficient, and within-module z-score. However, increasing evidence from neuroanatomical and predictive processing literature suggests that topological properties of a brain network may also be impacted by topography, that is, anatomical (spatial) distribution. More specifically, cortical limbic areas (agranular and dysgranular cortices), which occupy an anatomically central position, have been proposed to be topologically central and well suited to initiate predictions in the cerebral cortex. We estimated anatomical centrality and showed that it positively correlated with betweenness centrality, participation coefficient, and communicability, analogously to degree. In contrast to degree, however, anatomical centrality negatively correlated with within-module z-score. Our data suggest that degree centrality and anatomical centrality reflect distinct contributions to cortical organization. Whereas degree would be more related to the amount of information integration performed by an area, anatomical centrality would be more related to an area's position in the predictive hierarchy. Highly anatomically central areas may function as "high-level connectors," integrating already highly integrated information across modules. These results are consistent with a high-level, domain-general limbic workspace, integrated by highly anatomically central cortical areas.
Project description: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.
Project description:This paper introduces two new closely related betweenness centrality measures based on the Randomized Shortest Paths (RSP) framework, which fill a gap between traditional network centrality measures based on shortest paths and more recent methods considering random walks or current flows. The framework defines Boltzmann probability distributions over paths of the network which focus on the shortest paths, but also take into account longer paths depending on an inverse temperature parameter. RSP's have previously proven to be useful in defining distance measures on networks. In this work we study their utility in quantifying the importance of the nodes of a network. The proposed RSP betweenness centralities combine, in an optimal way, the ideas of using the shortest and purely random paths for analysing the roles of network nodes, avoiding issues involving these two paradigms. We present the derivations of these measures and how they can be computed in an efficient way. In addition, we show with real world examples the potential of the RSP betweenness centralities in identifying interesting nodes of a network that more traditional methods might fail to notice.
Project description:BACKGROUND:Contact tracing data of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) pandemic is used to estimate basic epidemiological parameters. Contact tracing data could also be potentially used for assessing the heterogeneity of transmission at the individual patient level. Characterization of individuals based on different levels of infectiousness could better inform the contact tracing interventions at field levels. METHODS:Standard social network analysis methods used for exploring infectious disease transmission dynamics was employed to analyze contact tracing data of 1959 diagnosed SARS-CoV-2 patients from a large state of India. Relational network data set with diagnosed patients as "nodes" and their epidemiological contact as "edges" was created. Directed network perspective was utilized in which directionality of infection emanated from a "source patient" towards a "target patient". Network measures of " degree centrality" and "betweenness centrality" were calculated to identify influential patients in the transmission of infection. Components analysis was conducted to identify patients connected as sub- groups. Descriptive statistics was used to summarise network measures and percentile ranks were used to categorize influencers. RESULTS:Out-degree centrality measures identified that of the total 1959 patients, 11.27% (221) patients have acted as a source of infection to 40.19% (787) other patients. Among these source patients, 0.65% (12) patients had a higher out-degree centrality (>?=?10) and have collectively infected 37.61% (296 of 787), secondary patients. Betweenness centrality measures highlighted that 7.50% (93) patients had a non-zero betweenness (range 0.5 to 135) and thus have bridged the transmission between other patients. Network component analysis identified nineteen connected components comprising of influential patient's which have overall accounted for 26.95% of total patients (1959) and 68.74% of epidemiological contacts in the network. CONCLUSIONS:Social network analysis method for SARS-CoV-2 contact tracing data would be of use in measuring individual patient level variations in disease transmission. The network metrics identified individual patients and patient components who have disproportionately contributed to transmission. The network measures and graphical tools could complement the existing contact tracing indicators and could help improve the contact tracing activities.
Project description:This study proposes a novel Normalized Wide network Ranking algorithm (NWRank) that has the advantage of ranking nodes and links of a network simultaneously. This algorithm combines the mutual reinforcement feature of Hypertext Induced Topic Selection (HITS) and the weight normalization feature of PageRank. Relative weights are assigned to links based on the degree of the adjacent neighbors and the Betweenness Centrality instead of assigning the same weight to every link as assumed in PageRank. Numerical experiment results show that NWRank performs consistently better than HITS, PageRank, eigenvector centrality, and edge betweenness from the perspective of network connectivity and approximate network flow, which is also supported by comparisons with the expensive N-1 benchmark removal criteria based on network efficiency. Furthermore, it can avoid some problems, such as the Tightly Knit Community effect, which exists in HITS. NWRank provides a new inexpensive way to rank nodes and links of a network, which has practical applications, particularly to prioritize resource allocation for upgrade of hierarchical and distributed networks, as well as to support decision making in the design of networks, where node and link importance depend on a balance of local and global integrity.
Project description:Introducing the Minimum Spanning Tree (MST) algorithms to neural networks science eliminated the problem of arbitrary setting of the threshold for connectivity strength. Despite these advantages, MST has been rarely used to study network abnormalities in schizophrenia. An MST graph mapping a network structure is its simplification, therefore, it is important to verify whether the reconfigured network is significantly related to the behavioural dimensions of the clinical picture of schizophrenia. 35 first-episode schizophrenia patients and 35 matched healthy controls underwent an assessment of information processing speed, cognitive inter-trial variability modelled with ex-Gaussian distributional analysis of reaction times and resting-state EEG recordings to obtain frequency-specific functional connectivity matrices from which MST graphs were computed. The patients' network had a more random structure and star-like arrangement with overloaded hubs positioned more posteriorly than it was in the case of the control group. Deficient processing speed in the group of patients was predicted by increased maximal betweenness centrality in beta and gamma bands, while decreased consistency in cognitive processing was predicted by the betweenness centrality of posterior nodes in the gamma band, together with duration of illness. The betweenness centrality of posterior nodes in the gamma band was also significantly correlated with positive psychotic symptoms in the clinical group.