Browse
Submit Data
Databases
API
Help

Dataset Information

21 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Detecting overlapping communities in complex networks using non-cooperative games.

ABSTRACT: Detecting communities in complex networks is of paramount importance, and its wide range of real-life applications in various areas has caused a lot of attention to be paid to it, and many efforts have been made to have efficient and accurate algorithms for this purpose. In this paper, we proposed a non-cooperative game theoretic-based algorithm that is able to detect overlapping communities. In this algorithm, nodes are regarded as players, and communities are assumed to be groups of players with similar strategies. Our two-phase algorithm detects communities and the overlapping nodes in separate phases that, while increasing the accuracy, especially in detecting overlapping nodes, brings about higher algorithm speed. Moreover, there is no need for setting parameters regarding the size or number of communities, and the absence of any stochastic process caused this algorithm to be stable. By appropriately adjusting stop criteria, our algorithm can be categorized among those with linear time complexity, making it highly scalable for large networks. Experiments on synthetic and real-world networks demonstrate our algorithm's good performance compared to similar algorithms in terms of detected overlapping nodes, detected communities size distribution, modularity, and normalized mutual information.

SUBMITTER: Ferdowsi F

PROVIDER: S-EPMC9247049 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Similar Datasets

Identifying stress responsive genes using overlapping communities in co-expression networks.

Project description:BackgroundThis paper proposes a workflow to identify genes that respond to specific treatments in plants. The workflow takes as input the RNA sequencing read counts and phenotypical data of different genotypes, measured under control and treatment conditions. It outputs a reduced group of genes marked as relevant for treatment response. Technically, the proposed approach is both a generalization and an extension of WGCNA. It aims to identify specific modules of overlapping communities underlying the co-expression network of genes. Module detection is achieved by using Hierarchical Link Clustering. The overlapping nature of the systems' regulatory domains that generate co-expression can be identified by such modules. LASSO regression is employed to analyze phenotypic responses of modules to treatment.ResultsThe workflow is applied to rice (Oryza sativa), a major food source known to be highly sensitive to salt stress. The workflow identifies 19 rice genes that seem relevant in the response to salt stress. They are distributed across 6 modules: 3 modules, each grouping together 3 genes, are associated to shoot K content; 2 modules of 3 genes are associated to shoot biomass; and 1 module of 4 genes is associated to root biomass. These genes represent target genes for the improvement of salinity tolerance in rice.ConclusionsA more effective framework to reduce the search-space for target genes that respond to a specific treatment is introduced. It facilitates experimental validation by restraining efforts to a smaller subset of genes of high potential relevance.

| S-EPMC8574028 | biostudies-literature

Finding overlapping communities in multilayer networks.

Project description:Finding communities in multilayer networks is a vital step in understanding the structure and dynamics of these layers, where each layer represents a particular type of relationship between nodes in the natural world. However, most community discovery methods for multilayer networks may ignore the interplay between layers or the unique topological structure in a layer. Moreover, most of them can only detect non-overlapping communities. In this paper, we propose a new community discovery method for multilayer networks, which leverages the interplay between layers and the unique topology in a layer to reveal overlapping communities. Through a comprehensive analysis of edge behaviors within and across layers, we first calculate the similarities for edges from the same layer and the cross layers. Then, by leveraging these similarities, we can construct a dendrogram for the multilayer networks that takes both the unique topological structure and the important interplay into consideration. Finally, by introducing a new community density metric for multilayer networks, we can cut the dendrogram to get the overlapping communities for these layers. By applying our method on both synthetic and real-world datasets, we demonstrate that our method has an accurate performance in discovering overlapping communities in multilayer networks.

| S-EPMC5919045 | biostudies-literature

Combined node and link partitions method for finding overlapping communities in complex networks.

Project description:Community detection in complex networks is a fundamental data analysis task in various domains, and how to effectively find overlapping communities in real applications is still a challenge. In this work, we propose a new unified model and method for finding the best overlapping communities on the basis of the associated node and link partitions derived from the same framework. Specifically, we first describe a unified model that accommodates node and link communities (partitions) together, and then present a nonnegative matrix factorization method to learn the parameters of the model. Thereafter, we infer the overlapping communities based on the derived node and link communities, i.e., determine each overlapped community between the corresponding node and link community with a greedy optimization of a local community function conductance. Finally, we introduce a model selection method based on consensus clustering to determine the number of communities. We have evaluated our method on both synthetic and real-world networks with ground-truths, and compared it with seven state-of-the-art methods. The experimental results demonstrate the superior performance of our method over the competing ones in detecting overlapping communities for all analysed data sets. Improved performance is particularly pronounced in cases of more complicated networked community structures.

| S-EPMC4341207 | biostudies-literature

Using dual-network-analyser for communities detecting in dual networks.

Project description:BackgroundRepresentations of the relationships among data using networks are widely used in several research fields such as computational biology, medical informatics and social network mining. Recently, complex networks have been introduced to better capture the insights of the modelled scenarios. Among others, dual networks (DNs) consist of mapping information as pairs of networks containing the same set of nodes but with different edges: one, called physical network, has unweighted edges, while the other, called conceptual network, has weighted edges.ResultsWe focus on DNs and we propose a tool to find common subgraphs (aka communities) in DNs with particular properties. The tool, called Dual-Network-Analyser, is based on the identification of communities that induce optimal modular subgraphs in the conceptual network and connected subgraphs in the physical one. It includes the Louvain algorithm applied to the considered case. The Dual-Network-Analyser can be used to study DNs, to find common modular communities. We report results on using the tool to identify communities on synthetic DNs as well as real cases in social networks and biological data.ConclusionThe proposed method has been tested by using synthetic and biological networks. Results demonstrate that it is well able to detect meaningful information from DNs.

| S-EPMC8750846 | biostudies-literature

Detecting overlapping protein complexes in protein-protein interaction networks.

Project description:We introduce clustering with overlapping neighborhood expansion (ClusterONE), a method for detecting potentially overlapping protein complexes from protein-protein interaction data. ClusterONE-derived complexes for several yeast data sets showed better correspondence with reference complexes in the Munich Information Center for Protein Sequence (MIPS) catalog and complexes derived from the Saccharomyces Genome Database (SGD) than the results of seven popular methods. The results also showed a high extent of functional homogeneity.

| S-EPMC3543700 | biostudies-literature

Efficient discovery of overlapping communities in massive networks.

Project description:Detecting overlapping communities is essential to analyzing and exploring natural networks such as social networks, biological networks, and citation networks. However, most existing approaches do not scale to the size of networks that we regularly observe in the real world. In this paper, we develop a scalable approach to community detection that discovers overlapping communities in massive real-world networks. Our approach is based on a Bayesian model of networks that allows nodes to participate in multiple communities, and a corresponding algorithm that naturally interleaves subsampling from the network and updating an estimate of its communities. We demonstrate how we can discover the hidden community structure of several real-world networks, including 3.7 million US patents, 575,000 physics articles from the arXiv preprint server, and 875,000 connected Web pages from the Internet. Furthermore, we demonstrate on large simulated networks that our algorithm accurately discovers the true community structure. This paper opens the door to using sophisticated statistical models to analyze massive networks.

| S-EPMC3767539 | biostudies-literature

Constant communities in complex networks.

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

Beyond Activity Space: Detecting Communities in Ecological Networks.

Project description:Emerging research suggests that the extent to which activity spaces - the collection of an individual's routine activity locations - overlap provides important information about the functioning of a city and its neighborhoods. To study patterns of overlapping activity spaces, we draw on the notion of an ecological network, a type of two-mode network with the two modes being individuals and the geographic locations where individuals perform routine activities. We describe a method for detecting "ecological communities" within these networks based on shared activity locations among individuals. Specifically, we identify latent activity pattern profiles, which, for each community, summarize its members' probability distribution of going to each location, and community assignment vectors, which, for each individual, summarize his/her probability distribution of belonging to each community. Using data from the Adolescent Health and Development in Context (AHDC) Study, we employ latent Dirichlet allocation (LDA) to identify activity pattern profiles and communities. We then explore differences across neighborhoods in the strength, and within-neighborhood consistency of community assignment. We hypothesize that these aspects of the neighborhood structure of ecological community membership capture meaningful dimensions of neighborhood functioning likely to co-vary with economic and racial composition. We discuss the implications of a focus on ecological communities for the conduct of "neighborhood effects" research more broadly.

| S-EPMC7685241 | biostudies-literature

Complex cooperative networks from evolutionary preferential attachment.

Project description:In spite of its relevance to the origin of complex networks, the interplay between form and function and its role during network formation remains largely unexplored. While recent studies introduce dynamics by considering rewiring processes of a pre-existent network, we study network growth and formation by proposing an evolutionary preferential attachment model, its main feature being that the capacity of a node to attract new links depends on a dynamical variable governed in turn by the node interactions. As a specific example, we focus on the problem of the emergence of cooperation by analyzing the formation of a social network with interactions given by the Prisoner's Dilemma. The resulting networks show many features of real systems, such as scale-free degree distributions, cooperative behavior and hierarchical clustering. Interestingly, results such as the cooperators being located mostly on nodes of intermediate degree are very different from the observations of cooperative behavior on static networks. The evolutionary preferential attachment mechanism points to an evolutionary origin of scale-free networks and may help understand similar feedback problems in the dynamics of complex networks by appropriately choosing the game describing the interaction of nodes.

| S-EPMC2413409 | biostudies-literature

Non-overlapping Neural Networks in Hydra vulgaris.

Project description:To understand the emergent properties of neural circuits, it would be ideal to record the activity of every neuron in a behaving animal and decode how it relates to behavior. We have achieved this with the cnidarian Hydra vulgaris, using calcium imaging of genetically engineered animals to measure the activity of essentially all of its neurons. Although the nervous system of Hydra is traditionally described as a simple nerve net, we surprisingly find instead a series of functional networks that are anatomically non-overlapping and are associated with specific behaviors. Three major functional networks extend through the entire animal and are activated selectively during longitudinal contractions, elongations in response to light, and radial contractions, whereas an additional network is located near the hypostome and is active during nodding. These results demonstrate the functional sophistication of apparently simple nerve nets, and the potential of Hydra and other basal metazoans as a model system for neural circuit studies.

| S-EPMC5423359 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data