Browse
Submit Data
Databases
API
Help

Dataset Information

25 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Deciphering network community structure by surprise.

ABSTRACT: The analysis of complex networks permeates all sciences, from biology to sociology. A fundamental, unsolved problem is how to characterize the community structure of a network. Here, using both standard and novel benchmarks, we show that maximization of a simple global parameter, which we call Surprise (S), leads to a very efficient characterization of the community structure of complex synthetic networks. Particularly, S qualitatively outperforms the most commonly used criterion to define communities, Newman and Girvan's modularity (Q). Applying S maximization to real networks often provides natural, well-supported partitions, but also sometimes counterintuitive solutions that expose the limitations of our previous knowledge. These results indicate that it is possible to define an effective global criterion for community structure and open new routes for the understanding of complex networks.

SUBMITTER: Aldecoa R

PROVIDER: S-EPMC3164713 | biostudies-literature | 2011

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Deciphering network community structure by surprise.

Aldecoa Rodrigo R Marín Ignacio I

PloS one 20110901 9

The analysis of complex networks permeates all sciences, from biology to sociology. A fundamental, unsolved problem is how to characterize the community structure of a network. Here, using both standard and novel benchmarks, we show that maximization of a simple global parameter, which we call Surprise (S), leads to a very efficient characterization of the community structure of complex synthetic networks. Particularly, S qualitatively outperforms the most commonly used criterion to define commu ...[more]

PMID: 21909420

Similar Datasets

Surprise maximization reveals the community structure of complex networks.

Project description:How to determine the community structure of complex networks is an open question. It is critical to establish the best strategies for community detection in networks of unknown structure. Here, using standard synthetic benchmarks, we show that none of the algorithms hitherto developed for community structure characterization perform optimally. Significantly, evaluating the results according to their modularity, the most popular measure of the quality of a partition, systematically provides mistaken solutions. However, a novel quality function, called Surprise, can be used to elucidate which is the optimal division into communities. Consequently, we show that the best strategy to find the community structure of all the networks examined involves choosing among the solutions provided by multiple algorithms the one with the highest Surprise value. We conclude that Surprise maximization precisely reveals the community structure of complex networks.

| S-EPMC3544010 | biostudies-literature

Community structure in the phonological network.

Project description:Community structure, which refers to the presence of densely connected groups within a larger network, is a common feature of several real-world networks from a variety of domains such as the human brain, social networks of hunter-gatherers and business organizations, and the World Wide Web (Porter et al., 2009). Using a community detection technique known as the Louvain optimization method, 17 communities were extracted from the giant component of the phonological network described in Vitevitch (2008). Additional analyses comparing the lexical and phonological characteristics of words in these communities against words in randomly generated communities revealed several novel discoveries. Larger communities tend to consist of short, frequent words of high degree and low age of acquisition ratings, and smaller communities tend to consist of longer, less frequent words of low degree and high age of acquisition ratings. Real communities also contained fewer different phonological segments compared to random communities, although the number of occurrences of phonological segments found in real communities was much higher than that of the same phonological segments in random communities. Interestingly, the observation that relatively few biphones occur very frequently and a large number of biphones occur rarely within communities mirrors the pattern of the overall frequency of words in a language (Zipf, 1935). The present findings have important implications for understanding the dynamics of activation spread among words in the phonological network that are relevant to lexical processing, as well as understanding the mechanisms that underlie language acquisition and the evolution of language.

| S-EPMC3753538 | biostudies-literature

AMR-SURPRISE

Project description:AMR-SURPRISE

| PRJEB71832 | ENA

Positive affect, surprise, and fatigue are correlates of network flexibility.

Project description:Advances in neuroimaging have made it possible to reconstruct functional networks from the activity patterns of brain regions distributed across the cerebral cortex. Recent work has shown that flexible reconfiguration of human brain networks over short timescales supports cognitive flexibility and learning. However, modulating network flexibility to enhance learning requires an understanding of an as-yet unknown relationship between flexibility and brain state. Here, we investigate the relationship between network flexibility and affect, leveraging an unprecedented longitudinal data set. We demonstrate that indices associated with positive mood and surprise are both associated with network flexibility - positive mood portends a more flexible brain while increased levels of surprise portend a less flexible brain. In both cases, these relationships are driven predominantly by a subset of brain regions comprising the somatomotor system. Our results simultaneously suggest a network-level mechanism underlying learning deficits in mood disorders as well as a potential target - altering an individual's mood or task novelty - to improve learning.

| S-EPMC5428446 | biostudies-literature

Improved network community structure improves function prediction.

Project description:We are overwhelmed by experimental data, and need better ways to understand large interaction datasets. While clustering related nodes in such networks-known as community detection-appears a promising approach, detecting such communities is computationally difficult. Further, how to best use such community information has not been determined. Here, within the context of protein function prediction, we address both issues. First, we apply a novel method that generates improved modularity solutions than the current state of the art. Second, we develop a better method to use this community information to predict proteins' functions. We discuss when and why this community information is important. Our results should be useful for two distinct scientific communities: first, those using various cost functions to detect community structure, where our new optimization approach will improve solutions, and second, those working to extract novel functional information about individual nodes from large interaction datasets.

| S-EPMC3711050 | biostudies-literature

Critical analysis of (Quasi-)Surprise for community detection in complex networks.

Project description:Module or community structures widely exist in complex networks, and optimizing statistical measures is one of the most popular approaches for revealing and identifying such structures in real-world applications. In this paper, we focus on critical behaviors of (Quasi-)Surprise, a type of statistical measure of interest for community structure, accompanied by a series of comparisons with other measures. Specially, the effect of various network parameters on the measures is thoroughly investigated. The critical number of dense subgraphs in partition transition is derived, and a kind of phase diagrams is provided to display and compare the phase transitions of the measures. The effect of "potential well" for (Quasi-)Surprise is revealed, which may be difficult to get across by general greedy (agglomerative or divisive) algorithms. Finally, an extension of Quasi-Surprise is introduced for the study of multi-scale structures. Experimental results are of help for understanding the critical behaviors of (Quasi-)Surprise, and may provide useful insight for the design of effective tools for community detection.

| S-EPMC6160439 | biostudies-literature

The network structure of human personality according to the NEO-PI-R: matching network community structure to factor structure.

Project description:INTRODUCTION: Human personality is described preferentially in terms of factors (dimensions) found using factor analysis. An alternative and highly related method is network analysis, which may have several advantages over factor analytic methods. AIM: To directly compare the ability of network community detection (NCD) and principal component factor analysis (PCA) to examine modularity in multidimensional datasets such as the neuroticism-extraversion-openness personality inventory revised (NEO-PI-R). METHODS: 434 healthy subjects were tested on the NEO-PI-R. PCA was performed to extract factor structures (FS) of the current dataset using both item scores and facet scores. Correlational network graphs were constructed from univariate correlation matrices of interactions between both items and facets. These networks were pruned in a link-by-link fashion while calculating the network community structure (NCS) of each resulting network using the Wakita Tsurumi clustering algorithm. NCSs were matched against FS and networks of best matches were kept for further analysis. RESULTS: At facet level, NCS showed a best match (96.2%) with a 'confirmatory' 5-FS. At item level, NCS showed a best match (80%) with the standard 5-FS and involved a total of 6 network clusters. Lesser matches were found with 'confirmatory' 5-FS and 'exploratory' 6-FS of the current dataset. Network analysis did not identify facets as a separate level of organization in between items and clusters. A small-world network structure was found in both item- and facet level networks. CONCLUSION: We present the first optimized network graph of personality traits according to the NEO-PI-R: a 'Personality Web'. Such a web may represent the possible routes that subjects can take during personality development. NCD outperforms PCA by producing plausible modularity at item level in non-standard datasets, and can identify the key roles of individual items and clusters in the network.

| S-EPMC3527484 | biostudies-other

The community structure of human cellular signaling network.

Project description:Living cell is highly responsive to specific chemicals in its environment, such as hormones and molecules in food or aromas. The reason is ascribed to the existence of widespread and diverse signal transduction pathways, between which crosstalks usually exist, thus constitute a complex signaling network. Evidently, knowledge of topology characteristic of this network could contribute a lot to the understanding of diverse cellular behaviors and life phenomena thus come into being. In this presentation, signal transduction data is extracted from KEGG to construct a cellular signaling network of Homo sapiens, which has 931 nodes and 6798 links in total. Computing the degree distribution, we find it is not a random network, but a scale-free network following a power-law of P(K) approximately K(-gamma), with gamma approximately equal to 2.2. Among three graph partition algorithms, the Guimera's simulated annealing method is chosen to study the details of topology structure and other properties of this cellular signaling network, as it shows the best performance. To reveal the underlying biological implications, further investigation is conducted on ad hoc community and sketch map of individual community is drawn accordingly. The involved experiment data can be found in the supplementary material.

| S-EPMC7094101 | biostudies-literature

Network community structure of substorms using SuperMAG magnetometers.

Project description:Geomagnetic substorms are a global magnetospheric reconfiguration, during which energy is abruptly transported to the ionosphere. Central to this are the auroral electrojets, large-scale ionospheric currents that are part of a larger three-dimensional system, the substorm current wedge. Many, often conflicting, magnetospheric reconfiguration scenarios have been proposed to describe the substorm current wedge evolution and structure. SuperMAG is a worldwide collaboration providing easy access to ground based magnetometer data. Here we show application of techniques from network science to analyze data from 137 SuperMAG ground-based magnetometers. We calculate a time-varying directed network and perform community detection on the network, identifying locally dense groups of connections. Analysis of 41 substorms exhibit robust structural change from many small, uncorrelated current systems before substorm onset, to a large spatially-extended coherent system, approximately 10 minutes after onset. We interpret this as strong indication that the auroral electrojet system during substorm expansions is inherently a large-scale phenomenon and is not solely due to many meso-scale wedgelets.

| S-EPMC7988152 | biostudies-literature

bacterial community structure

Project description:bacterial community structure and function changes after fire

| PRJEB12433 | ENA