Discovering communities in complex networks by edge label propagation.
Ontology highlight
ABSTRACT:
SUBMITTER: Liu W
PROVIDER: S-EPMC4772381 | biostudies-other | 2016
REPOSITORIES: biostudies-other
Similar Datasets
Project description:Identifying community structure is a fundamental problem in network analysis. Most community detection algorithms are based on optimizing a combinatorial parameter, for example modularity. This optimization is generally NP-hard, thus merely changing the vertex order can alter their assignments to the community. However, there has been less study on how vertex ordering influences the results of the community detection algorithms. Here we identify and study the properties of invariant groups of vertices (constant communities) whose assignment to communities are, quite remarkably, not affected by vertex ordering. The percentage of constant communities can vary across different applications and based on empirical results we propose metrics to evaluate these communities. Using constant communities as a pre-processing step, one can significantly reduce the variation of the results. Finally, we present a case study on phoneme network and illustrate that constant communities, quite strikingly, form the core functional units of the larger communities.
| S-EPMC6504828 | biostudies-other
Project description:Semi-supervised relational learning methods aim to classify nodes in a partially-labeled graph. While popular, existing methods using Graph Neural Networks (GNN) for semi-supervised relational learning have mainly focused on learning node representations by aggregating nearby attributes, and it is still challenging to leverage inferences about unlabeled nodes with few attributes—particularly when trying to exploit higher-order relationships in the network efficiently. To address this, we propose a Graph Neural Network architecture that incorporates patterns among the available class labels and uses (1) a Role Equivalence attention mechanism and (2) a mini-batch importance sampling method to improve efficiency when learning over high-order paths. In particular, our Role Equivalence attention mechanism is able to use nodes’ roles to learn how to focus on relevant distant neighbors, in order to adaptively reduce the increased noise that occurs when higher-order structures are considered. In experiments on six different real-world datasets, we show that our model (REGNN) achieves significant performance gains compared to other recent state-of-the-art baselines, particularly when higher-order paths are considered in the models.
| S-EPMC7206289 | biostudies-literature
Project description:Human tumors have distinct profiles of genomic alterations, and each of these alterations has the potential to cause unique changes to cellular homeostasis. Detailed analyses of these changes could reveal downstream effects of genomic alterations, contributing to our understanding of their roles in tumor development and progression. Across a range of tumor types, including bladder, lung, and endometrial carcinoma, we determined genes that are frequently altered in The Cancer Genome Atlas patient populations, then examined the effects of these alterations on signaling and regulatory pathways. To achieve this, we used a label propagation-based methodology to generate networks from gene expression signatures associated with defined mutations. Individual networks offered a large-scale view of signaling changes represented by gene signatures, which in turn reflected the scope of molecular events that are perturbed in the presence of a given genomic alteration. Comparing different networks to one another revealed common biological pathways impacted by distinct genomic alterations, highlighting the concept that tumors can dysregulate key pathways through multiple, seemingly unrelated mechanisms. Finally, altered genes inducing common changes to the signaling network were used to search for genomic markers of drug response, connecting shared perturbations to differential drug sensitivity.
| S-EPMC6599034 | biostudies-literature
Project description:Dynamical processes occurring on the edges in complex networks are relevant to a variety of real-world situations. Despite recent advances, a framework for edge controllability is still required for complex networks of arbitrary structure and interaction strength. Generalizing a previously introduced class of processes for edge dynamics, the switchboard dynamics, and exploit- ing the exact controllability theory, we develop a universal framework in which the controllability of any node is exclusively determined by its local weighted structure. This framework enables us to identify a unique set of critical nodes for control, to derive analytic formulas and articulate efficient algorithms to determine the exact upper and lower controllability bounds, and to evaluate strongly structural controllability of any given network. Applying our framework to a large number of model and real-world networks, we find that the interaction strength plays a more significant role in edge controllability than the network structure does, due to a vast range between the bounds determined mainly by the interaction strength. Moreover, transcriptional regulatory networks and electronic circuits are much more strongly structurally controllable (SSC) than other types of real-world networks, directed networks are more SSC than undirected networks, and sparse networks are typically more SSC than dense networks.
| S-EPMC5484715 | biostudies-literature
Project description:Label propagation algorithm (LPA) is an extremely fast community detection method and is widely used in large scale networks. In spite of the advantages of LPA, the issue of its poor stability has not yet been well addressed. We propose a novel node influence based label propagation algorithm for community detection (NIBLPA), which improves the performance of LPA by improving the node orders of label updating and the mechanism of label choosing when more than one label is contained by the maximum number of nodes. NIBLPA can get more stable results than LPA since it avoids the complete randomness of LPA. The experimental results on both synthetic and real networks demonstrate that NIBLPA maintains the efficiency of the traditional LPA algorithm, and, at the same time, it has a superior performance to some representative methods.
| S-EPMC4066938 | biostudies-other
Project description:In a complex system, perturbations propagate by following paths on the network of interactions among the system's units. In contrast to what happens with the spreading of epidemics, observations of general perturbations are often very sparse in time (there is a single observation of the perturbed system) and in "space" (only a few perturbed and unperturbed units are observed). A major challenge in many areas, from biology to the social sciences, is to infer the propagation paths from observations of the effects of perturbation under these sparsity conditions. We address this problem and show that it is possible to go beyond the usual approach of using the shortest paths connecting the known perturbed nodes. Specifically, we show that a simple and general probabilistic model, which we solved using belief propagation, provides fast and accurate estimates of the probabilities of nodes being perturbed.
| S-EPMC5088640 | biostudies-literature
Project description:We introduce a new method for detecting communities of arbitrary size in an undirected weighted network. Our approach is based on tracing the path of closest-friendship between nodes in the network using the recently proposed Generalized Erds Numbers. This method does not require the choice of any arbitrary parameters or null models, and does not suffer from a system-size resolution limit. Our closest-friend community detection is able to accurately reconstruct the true network structure for a large number of real world and artificial benchmarks, and can be adapted to study the multi-level structure of hierarchical communities as well. We also use the closeness between nodes to develop a degree of robustness for each node, which can assess how robustly that node is assigned to its community. To test the efficacy of these methods, we deploy them on a variety of well known benchmarks, a hierarchal structured artificial benchmark with a known community and robustness structure, as well as real-world networks of coauthorships between the faculty at a major university and the network of citations of articles published in Physical Review. In all cases, microcommunities, hierarchy of the communities, and variable node robustness are all observed, providing insights into the structure of the network.
| S-EPMC3409242 | biostudies-literature
Project description:This paper proposes a new methodology based on non-negative matrix factorization to detect communities and to identify central nodes in a network as well as within communities. The method is specifically designed for directed weighted networks and, consequently, it has been applied to the interbank network derived from the e-MID interbank market. In an interbank network indeed links are directed, representing flows of funds between lenders and borrowers. Besides distinguishing between Systemically Important Borrowers and Lenders, the technique complements the detection of systemically important banks, revealing the community structure of the network, that proxies the most plausible areas of contagion of institutions' distress.
| S-EPMC5176285 | biostudies-literature
Project description:To understand the formation, evolution, and function of complex systems, it is crucial to understand the internal organization of their interaction networks. Partly due to the impossibility of visualizing large complex networks, resolving network structure remains a challenging problem. Here we overcome this difficulty by combining the visual pattern recognition ability of humans with the high processing speed of computers to develop an exploratory method for discovering groups of nodes characterized by common network properties, including but not limited to communities of densely connected nodes. Without any prior information about the nature of the groups, the method simultaneously identifies the number of groups, the group assignment, and the properties that define these groups. The results of applying our method to real networks suggest the possibility that most group structures lurk undiscovered in the fast-growing inventory of social, biological, and technological networks of scientific interest.
| S-EPMC3240966 | biostudies-literature
Project description:Recent advances indicate that assigning or reversing edge direction can significantly improve the structural controllability of complex networks. For directed networks, approaching the optimal structural controllability can be achieved by detecting and reversing certain "inappropriate" edge directions. However, the existence of multiple sets of "inappropriate" edge directions suggests that different edges have different effects on optimal controllability-that is, different combinations of edges can be reversed to achieve the same structural controllability. Therefore, we classify edges into three categories based on their direction: critical, redundant and intermittent. We then investigate the effects of changing these edge directions on network controllability, and demonstrate that the existence of more critical edge directions implies not only a lower cost of modifying inappropriate edges but also better controllability. Motivated by this finding, we present a simple edge orientation method aimed at producing more critical edge directions-utilizing only local information-which achieves near optimal controllability. Furthermore, we explore the effects of edge direction on the controllability of several real networks.
| S-EPMC4539223 | biostudies-literature