Community detection in complex networks using extremal optimization

Modularity-based graph partitioning using conditional expected models

Modularity-based partitioning methods divide networks into modules by comparing their structure against random networks conditioned to have the same number of nodes, edges, and degree distribution. We propose a novel way to measure modularity and divide graphs, based on conditional probabilities of the edge strength of random networks. We provide closed-form solutions for the expected strength of an edge when it is conditioned on the degrees of the two neighboring nodes, or alternatively on the degrees of all nodes comprising the network. We analytically compute the expected network under the assumptions of Gaussian and Bernoulli distributions. When the Gaussian distribution assumption is violated, we prove that our expression is the best linear unbiased estimator. Finally, we investigate the performance of our conditional expected model in partitioning simulated and real-world networks.

Replica inference approach to unsupervised multiscale image segmentation

We apply a replica-inference-based Potts model method to unsupervised image segmentation on multiple scales. This approach was inspired by the statistical mechanics problem of "community detection" and its phase diagram. Specifically, the problem is cast as identifying tightly bound clusters ("communities" or "solutes") against a background or "solvent." Within our multiresolution approach, we compute information-theory-based correlations among multiple solutions ("replicas") of the same graph over a range of resolutions. Significant multiresolution structures are identified by replica correlations manifest by information theory overlaps. We further employ such information theory measures (such as normalized mutual information and variation of information), thermodynamic quantities such as the system entropy and energy, and dynamic measures monitoring the convergence time to viable solutions as metrics for transitions between various solvable and unsolvable phases. Within the solvable phase, transitions between contending solutions (such as those corresponding to segmentations on different scales) may also appear. With the aid of these correlations as well as thermodynamic measures, the phase diagram of the corresponding Potts model is analyzed at both zero and finite temperatures. Optimal parameters corresponding to a sensible unsupervised segmentations appear within the "easy phase" of the Potts model. Our algorithm is fast and shown to be at least as accurate as the best algorithms to date and to be especially suited to the detection of camouflaged images.

Modularity detection in protein-protein interaction networks

Background

Many recent studies have investigated modularity in biological networks, and its role in functional and structural characterization of constituent biomolecules. A technique that has shown considerable promise in the domain of modularity detection is the Newman and Girvan (NG) algorithm, which relies on the number of shortest-paths across pairs of vertices in the network traversing a given edge, referred to as the betweenness of that edge. The edge with the highest betweenness is iteratively eliminated from the network, with the betweenness of the remaining edges recalculated in every iteration. This generates a complete dendrogram, from which modules are extracted by applying a quality metric called modularity denoted by Q. This exhaustive computation can be prohibitively expensive for large networks such as Protein-Protein Interaction Networks. In this paper, we present a novel optimization to the modularity detection algorithm, in terms of an efficient termination criterion based on a target edge betweenness value, using which the process of iterative edge removal may be terminated.

Results

We validate the robustness of our approach by applying our algorithm on real-world protein-protein interaction networks of Yeast, C.Elegans and Drosophila, and demonstrate that our algorithm consistently has significant computational gains in terms of reduced runtime, when compared to the NG algorithm. Furthermore, our algorithm produces modules comparable to those from the NG algorithm, qualitatively and quantitatively. We illustrate this using comparison metrics such as module distribution, module membership cardinality, modularity Q, and Jaccard Similarity Coefficient.

Conclusions

We have presented an optimized approach for efficient modularity detection in networks. The intuition driving our approach is the extraction of holistic measures of centrality from graphs, which are representative of inherent modular structure of the underlying network, and the application of those measures to efficiently guide the modularity detection process. We have empirically evaluated our approach in the specific context of real-world large scale biological networks, and have demonstrated significant savings in computational time while maintaining comparable quality of detected modules.

Using amino acid correlation and community detection algorithms to identify functional determinants in protein families

Correlated mutation analysis has a long history of interesting applications, mostly in the detection of contact pairs in protein structures. Based on previous observations that, if properly assessed, amino acid correlation data can also provide insights about functional sub-classes in a protein family, we provide a complete framework devoted to this purpose. An amino acid specific correlation measure is proposed, which can be used to build networks summarizing all correlation and anti-correlation patterns in a protein family. These networks can be submitted to community structure detection algorithms, resulting in subsets of correlated amino acids which can be further assessed by specific parameters and procedures that provide insight into the relationship between different communities, the individual importance of community members and the adherence of a given amino acid sequence to a given community. By applying this framework to three protein families with contrasting characteristics (the Fe/Mn-superoxide dismutases, the peroxidase-catalase family and the C-type lysozyme/α-lactalbumin family), we show how our method and the proposed parameters and procedures are related to biological characteristics observed in these protein families, highlighting their potential use in protein characterization and gene annotation.

Emerging meso- and macroscales from synchronization of adaptive networks

We consider a set of interacting phase oscillators, with a coupling between synchronized nodes adaptively reinforced, and the constraint of a limited resource for a node to establish connections with the other units of the network. We show that such a competitive mechanism leads to the emergence of a rich modular structure underlying cluster synchronization, and to a scale-free distribution for the connection strengths of the units.

Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications

In this paper we extend our previous work on the stochastic block model, a commonly used generative model for social and biological networks, and the problem of inferring functional groups or communities from the topology of the network. We use the cavity method of statistical physics to obtain an asymptotically exact analysis of the phase diagram. We describe in detail properties of the detectability-undetectability phase transition and the easy-hard phase transition for the community detection problem. Our analysis translates naturally into a belief propagation algorithm for inferring the group memberships of the nodes in an optimal way, i.e., that maximizes the overlap with the underlying group memberships, and learning the underlying parameters of the block model. Finally, we apply the algorithm to two examples of real-world networks and discuss its performance.

Finding communities in weighted networks through synchronization

Community detection in weighted networks is an important challenge. In this paper, we introduce a local weight ratio scheme for identifying the community structures of weighted networks within the context of the Kuramoto model by taking into account weights of links. The proposed scheme takes full advantage of the information of the link density among vertices and the closeness of relations between each vertex and its neighbors. By means of this scheme, we explore the connection between community structures and dynamic time scales of synchronization. Moreover, we can also unravel the hierarchical structures of weighted networks with a well-defined connectivity pattern by the synchronization process. The performance of the proposed method is evaluated on both computer-generated benchmark graphs and real-world networks.

Clustering drives assortativity and community structure in ensembles of networks

Clustering, assortativity, and communities are key features of complex networks. We probe dependencies between these features and find that ensembles of networks with high clustering display both high assortativity by degree and prominent community structure, while ensembles with high assortativity show much less enhancement of the clustering or community structure. Further, clustering can amplify a small homophilic bias for trait assortativity in network ensembles. This marked asymmetry suggests that transitivity could play a larger role than homophily in determining the structure of many complex networks.

The ubiquity of small-world networks

Small-world networks, according to Watts and Strogatz, are a class of networks that are "highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs." These characteristics result in networks with unique properties of regional specialization with efficient information transfer. Social networks are intuitive examples of this organization, in which cliques or clusters of friends being interconnected but each person is really only five or six people away from anyone else. Although this qualitative definition has prevailed in network science theory, in application, the standard quantitative application is to compare path length (a surrogate measure of distributed processing) and clustering (a surrogate measure of regional specialization) to an equivalent random network. It is demonstrated here that comparing network clustering to that of a random network can result in aberrant findings and that networks once thought to exhibit small-world properties may not. We propose a new small-world metric, ω (omega), which compares network clustering to an equivalent lattice network and path length to a random network, as Watts and Strogatz originally described. Example networks are presented that would be interpreted as small-world when clustering is compared to a random network but are not small-world according to ω. These findings have important implications in network science because small-world networks have unique topological properties, and it is critical to accurately distinguish them from networks without simultaneous high clustering and short path length.

Exploring the structural regularities in networks

In this paper, we consider the problem of exploring structural regularities of networks by dividing the nodes of a network into groups such that the members of each group have similar patterns of connections to other groups. Specifically, we propose a general statistical model to describe network structure. In this model, a group is viewed as a hidden or unobserved quantity and it is learned by fitting the observed network data using the expectation-maximization algorithm. Compared with existing models, the most prominent strength of our model is the high flexibility. This strength enables it to possess the advantages of existing models and to overcome their shortcomings in a unified way. As a result, not only can broad types of structure be detected without prior knowledge of the type of intrinsic regularities existing in the target network, but also the type of identified structure can be directly learned from the network. Moreover, by differentiating outgoing edges from incoming edges, our model can detect several types of structural regularities beyond competing models. Tests on a number of real world and artificial networks demonstrate that our model outperforms the state-of-the-art model in shedding light on the structural regularities of networks, including the overlapping community structure, multipartite structure, and several other types of structure, which are beyond the capability of existing models.

Memetic algorithm for community detection in networks

Community structure is one of the most important properties in networks, and community detection has received an enormous amount of attention in recent years. Modularity is by far the most used and best known quality function for measuring the quality of a partition of a network, and many community detection algorithms are developed to optimize it. However, there is a resolution limit problem in modularity optimization methods. In this study, a memetic algorithm, named Meme-Net, is proposed to optimize another quality function, modularity density, which includes a tunable parameter that allows one to explore the network at different resolutions. Our proposed algorithm is a synergy of a genetic algorithm with a hill-climbing strategy as the local search procedure. Experiments on computer-generated and real-world networks show the effectiveness and the multiresolution ability of the proposed method.

Tracking traders' understanding of the market using e-communication data

Tracking the volume of keywords in Internet searches, message boards, or Tweets has provided an alternative for following or predicting associations between popular interest or disease incidences. Here, we extend that research by examining the role of e-communications among day traders and their collective understanding of the market. Our study introduces a general method that focuses on bundles of words that behave differently from daily communication routines, and uses original data covering the content of instant messages among all day traders at a trading firm over a 40-month period. Analyses show that two word bundles convey traders' understanding of same day market events and potential next day market events. We find that when market volatility is high, traders' communications are dominated by same day events, and when volatility is low, communications are dominated by next day events. We show that the stronger the traders' attention to either same day or next day events, the higher their collective trading performance. We conclude that e-communication among traders is a product of mass collaboration over diverse viewpoints that embodies unique information about their weak or strong understanding of the market.

Topological structure of the space of phenotypes: the case of RNA neutral networks

The evolution and adaptation of molecular populations is constrained by the diversity accessible through mutational processes. RNA is a paradigmatic example of biopolymer where genotype (sequence) and phenotype (approximated by the secondary structure fold) are identified in a single molecule. The extreme redundancy of the genotype-phenotype map leads to large ensembles of RNA sequences that fold into the same secondary structure and can be connected through single-point mutations. These ensembles define neutral networks of phenotypes in sequence space. Here we analyze the topological properties of neutral networks formed by 12-nucleotides RNA sequences, obtained through the exhaustive folding of sequence space. A total of 4(12) sequences fragments into 645 subnetworks that correspond to 57 different secondary structures. The topological analysis reveals that each subnetwork is far from being random: it has a degree distribution with a well-defined average and a small dispersion, a high clustering coefficient, and an average shortest path between nodes close to its minimum possible value, i.e. the Hamming distance between sequences. RNA neutral networks are assortative due to the correlation in the composition of neighboring sequences, a feature that together with the symmetries inherent to the folding process explains the existence of communities. Several topological relationships can be analytically derived attending to structural restrictions and generic properties of the folding process. The average degree of these phenotypic networks grows logarithmically with their size, such that abundant phenotypes have the additional advantage of being more robust to mutations. This property prevents fragmentation of neutral networks and thus enhances the navigability of sequence space. In summary, RNA neutral networks show unique topological properties, unknown to other networks previously described.

Universal fractal scaling of self-organized networks

There is an abundance of literature on complex networks describing a variety of relationships among units in social, biological, and technological systems. Such networks, consisting of interconnected nodes, are often self-organized, naturally emerging without any overarching designs on topological structure yet enabling efficient interactions among nodes. Here we show that the number of nodes and the density of connections in such self-organized networks exhibit a power law relationship. We examined the size and connection density of 47 self-organizing networks of various biological, social, and technological origins, and found that the size-density relationship follows a fractal relationship spanning over 6 orders of magnitude. This finding indicates that there is an optimal connection density in self-organized networks following fractal scaling regardless of their sizes.

Identifying communities by influence dynamics in social networks

Communities are not static; they evolve, split and merge, appear and disappear, i.e., they are the product of dynamical processes that govern the evolution of a network. A good algorithm for community detection should not only quantify the topology of the network but incorporate the dynamical processes that take place on the network. We present an algorithm for community detection that combines network structure with processes that support the creation and/or evolution of communities. The algorithm does not embrace the universal approach but instead tries to focus on social networks and model dynamic social interactions that occur on those networks. It identifies leaders and communities that form around those leaders. It naturally supports overlapping communities by associating each node with a membership vector that describes the node's involvement in each community. This way, in addition to the overlapping communities, we can identify nodes that are good followers of their leader and also nodes with no clear community involvement that serve as proxies between several communities and that are equally as important. We run the algorithm for several real social networks which we believe represent a good fraction of the wide body of social networks and discuss the results, including other possible applications.

Emergence of structural patterns out of synchronization in networks with competitive interactions

Synchronization is a collective phenomenon occurring in systems of interacting units, and is ubiquitous in nature, society and technology. Recent studies have enlightened the important role played by the interaction topology on the emergence of synchronized states. However, most of these studies neglect that real world systems change their interaction patterns in time. Here, we analyze synchronization features in networks in which structural and dynamical features co-evolve. The feedback of the node dynamics on the interaction pattern is ruled by the competition of two mechanisms: homophily (reinforcing those interactions with other correlated units in the graph) and homeostasis (preserving the value of the input strength received by each unit). The competition between these two adaptive principles leads to the emergence of key structural properties observed in real world networks, such as modular and scale-free structures, together with a striking enhancement of local synchronization in systems with no global order.

Deciphering network community structure by surprise

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.

Computationally efficient measure of topological redundancy of biological and social networks

It is well known that biological and social interaction networks have a varying degree of redundancy, though a consensus of the precise cause of this is so far lacking. In this paper, we introduce a topological redundancy measure for labeled directed networks that is formal, computationally efficient, and applicable to a variety of directed networks such as cellular signaling, and metabolic and social interaction networks. We demonstrate the computational efficiency of our measure by computing its value and statistical significance on a number of biological and social networks with up to several thousands of nodes and edges. Our results suggest a number of interesting observations: (1) Social networks are more redundant that their biological counterparts, (2) transcriptional networks are less redundant than signaling networks, (3) the topological redundancy of the C. elegans metabolic network is largely due to its inclusion of currency metabolites, and (4) the redundancy of signaling networks is highly (negatively) correlated with the monotonicity of their dynamics.

Networks for systems biology: conceptual connection of data and function

The purpose of this study is to survey the use of networks and network-based methods in systems biology. This study starts with an introduction to graph theory and basic measures allowing to quantify structural properties of networks. Then, the authors present important network classes and gene networks as well as methods for their analysis. In the last part of this study, the authors review approaches that aim at analysing the functional organisation of gene networks and the use of networks in medicine. In addition to this, the authors advocate networks as a systematic approach to general problems in systems biology, because networks are capable of assuming multiple roles that are very beneficial connecting experimental data with a functional interpretation in biological terms.

Interplay between structure and dynamics in adaptive complex networks: emergence and amplification of modularity by adaptive dynamics

Many real networks display modular organization, which can influence dynamical clustering on the networks. Therefore, there have been proposals put forth recently to detect network communities by using dynamical clustering. In this paper, we study how the feedback from dynamical clusters can shape the network connection weights with a weight-adaptation scheme motivated from Hebbian learning in neural systems. We show that such a scheme generically leads to the formation of community structure in globally coupled chaotic oscillators. The number of communities in the adaptive network depends on coupling strength c and adaptation strength r. In a modular network, the adaptation scheme will enhance the intramodule connection weights and weaken the intermodule connection strengths, generating effectively separated dynamical clusters that coincide with the communities of the network. In this sense, the modularity of the network is amplified by the adaptation. Thus, for a network with a strong community structure, the adaptation scheme can evidently reflect its community structure by the resulting amplified weighted network. For a network with a weak community structure, the statistical properties of synchronization clusters from different realizations can be used to amplify the modularity of the communities so that they can be detected reliably by the other traditional algorithms.

Penalized versions of the Newman-Girvan modularity and their relation to normalized cuts and k-means clustering

Two penalized-balanced and normalized-versions of the Newman-Girvan modularity are introduced and estimated by the non-negative eigenvalues of the modularity and normalized modularity matrix, respectively. In this way, the partition of the vertices that maximizes the modularity can be obtained by applying the k-means algorithm for the representatives of the vertices based on the eigenvectors belonging to the largest positive eigenvalues of the modularity or normalized modularity matrix. The proper dimension depends on the number of the structural eigenvalues of positive sign, while dominating negative eigenvalues indicate an anticommunity structure; the balance between the negative and the positive eigenvalues determines whether the underlying graph has a community, anticommunity, or randomlike structure.

Overlapping community detection using Bayesian non-negative matrix factorization

Identifying overlapping communities in networks is a challenging task. In this work we present a probabilistic approach to community detection that utilizes a Bayesian non-negative matrix factorization model to extract overlapping modules from a network. The scheme has the advantage of soft-partitioning solutions, assignment of node participation scores to modules, and an intuitive foundation. We present the performance of the method against a variety of benchmark problems and compare and contrast it to several other algorithms for community detection.

Evolutionary method for finding communities in bipartite networks

An important step in unveiling the relation between network structure and dynamics defined on networks is to detect communities, and numerous methods have been developed separately to identify community structure in different classes of networks, such as unipartite networks, bipartite networks, and directed networks. Here, we show that the finding of communities in such networks can be unified in a general framework-detection of community structure in bipartite networks. Moreover, we propose an evolutionary method for efficiently identifying communities in bipartite networks. To this end, we show that both unipartite and directed networks can be represented as bipartite networks, and their modularity is completely consistent with that for bipartite networks, the detection of modular structure on which can be reformulated as modularity maximization. To optimize the bipartite modularity, we develop a modified adaptive genetic algorithm (MAGA), which is shown to be especially efficient for community structure detection. The high efficiency of the MAGA is based on the following three improvements we make. First, we introduce a different measure for the informativeness of a locus instead of the standard deviation, which can exactly determine which loci mutate. This measure is the bias between the distribution of a locus over the current population and the uniform distribution of the locus, i.e., the Kullback-Leibler divergence between them. Second, we develop a reassignment technique for differentiating the informative state a locus has attained from the random state in the initial phase. Third, we present a modified mutation rule which by incorporating related operations can guarantee the convergence of the MAGA to the global optimum and can speed up the convergence process. Experimental results show that the MAGA outperforms existing methods in terms of modularity for both bipartite and unipartite networks.

Parameterized centrality metric for network analysis

A variety of metrics have been proposed to measure the relative importance of nodes in a network. One of these, alpha-centrality [P. Bonacich, Am. J. Sociol. 92, 1170 (1987)], measures the number of attenuated paths that exist between nodes. We introduce a normalized version of this metric and use it to study network structure, for example, to rank nodes and find community structure of the network. Specifically, we extend the modularity-maximization method for community detection to use this metric as the measure of node connectivity. Normalized alpha-centrality is a powerful tool for network analysis, since it contains a tunable parameter that sets the length scale of interactions. Studying how rankings and discovered communities change when this parameter is varied allows us to identify locally and globally important nodes and structures. We apply the proposed metric to several benchmark networks and show that it leads to better insights into network structure than alternative metrics.

Locally optimal heuristic for modularity maximization of networks

Community detection in networks based on modularity maximization is currently done with hierarchical divisive or agglomerative as well as partitioning heuristics, hybrids, and, in a few papers, exact algorithms. We consider here the case of hierarchical networks in which communities should be detected and propose a divisive heuristic which is locally optimal in the sense that each of the successive bipartitions is done in a provably optimal way. This heuristic is compared with the spectral-based hierarchical divisive heuristic of Newman [Proc. Natl. Acad. Sci. USA 103, 8577 (2006).] and with the hierarchical agglomerative heuristic of Clauset, Newman, and Moore [Phys. Rev. E 70, 066111 (2004).]. Computational results are given for a series of problems of the literature with up to 4941 vertices and 6594 edges. They show that the proposed divisive heuristic gives better results than the divisive heuristic of Newman and than the agglomerative heuristic of Clauset et al.

Multilevel local search algorithms for modularity clustering

Modularity is a widely used quality measure for graph clusterings. Its exact maximization is NP-hard and prohibitively expensive for large graphs. Popular heuristics first perform a coarsening phase, where local search starting from singleton clusters is used to compute a preliminary clustering, and then optionally a refinement phase, where this clustering is improved by moving vertices between clusters. As a generalization, multilevel heuristics coarsen in several stages, and refine by moving entire clusters from each of these stages, not only individual vertices.

This article organizes existing and new single-level and multilevel heuristics into a coherent design space, and compares them experimentally with respect to their effectiveness (achieved modularity) and runtime. For coarsening by iterated cluster joining, it turns out that the most widely used criterion for joining clusters (modularity increase) is outperformed by other simple criteria, that a recent multistep algorithm [Schuetz and Caflisch 2008] is no improvement over simple single-step coarsening for these criteria, and that the recent multilevel coarsening by iterated vertex moving [Blondel et al. 2008] is somewhat faster but slightly less effective (with refinement). The new multilevel refinement is significantly more effective than the conventional single-level refinement or no refinement, in reasonable runtime.

A comparison with published benchmark results and algorithm implementations shows that multilevel local search heuristics, despite their relative simplicity, are competitive with the best algorithms in the literature.

Network community-detection enhancement by proper weighting

In this paper, we show how proper assignment of weights to the edges of a complex network can enhance the detection of communities and how it can circumvent the resolution limit and the extreme degeneracy problems associated with modularity. Our general weighting scheme takes advantage of graph theoretic measures and it introduces two heuristics for tuning its parameters. We use this weighting as a preprocessing step for the greedy modularity optimization algorithm of Newman to improve its performance. The result of the experiments of our approach on computer-generated and real-world data networks confirm that the proposed approach not only mitigates the problems of modularity but also improves the modularity optimization.

Mesoscopic analysis of networks: applications to exploratory analysis and data clustering

We investigate the adaptation and performance of modularity-based algorithms, designed in the scope of complex networks, to analyze the mesoscopic structure of correlation matrices. Using a multiresolution analysis, we are able to describe the structure of the data in terms of clusters at different topological levels. We demonstrate the applicability of our findings in two different scenarios: to analyze the neural connectivity of the nematode Caenorhabditis elegans and to automatically classify a typical benchmark of unsupervised clustering, the Iris dataset, with considerable success.

The unreasonable effectiveness of tree-based theory for networks with clustering

We demonstrate that a tree-based theory for various dynamical processes operating on static, undirected networks yields extremely accurate results for several networks with high levels of clustering. We find that such a theory works well as long as the mean intervertex distance ℓ is sufficiently small--that is, as long as it is close to the value of ℓ in a random network with negligible clustering and the same degree-degree correlations. We support this hypothesis numerically using both real-world networks from various domains and several classes of synthetic clustered networks. We present analytical calculations that further support our claim that tree-based theories can be accurate for clustered networks, provided that the networks are "sufficiently small" worlds.

Improving community detection in networks by targeted node removal

How a network breaks up into subnetworks or communities is of wide interest. Here we show that vertices connected to many other vertices across a network can disturb the community structures of otherwise ordered networks, introducing noise. We investigate strategies to identify and remove noisy vertices ("violators") and develop a quantitative approach using statistical breakpoints to identify when the largest enhancement to a modularity measure is achieved. We show that removing nodes thus identified reduces noise in detected community structures for a range of different types of real networks in software systems and in biological systems.

Partitioning networks into communities by message passing

Community structures are found to exist ubiquitously in a number of systems conveniently represented as complex networks. Partitioning networks into communities is thus important and crucial to both capture and simplify these systems' complexity. The prevalent and standard approach to meet this goal is related to the maximization of a quality function, modularity, which measures the goodness of a partition of a network into communities. However, it has recently been found that modularity maximization suffers from a resolution limit, which prevents its effectiveness and range of applications. Even when neglecting the resolution limit, methods designed for detecting communities in undirected networks cannot always be easily extended, and even less directly applied, to directed networks (for which specifically designed community detection methods are very limited). Furthermore, real-world networks are frequently found to possess hierarchical structure and the problem of revealing such type of structure is far from being addressed. In this paper, we propose a scheme that partitions networks into communities by electing community leaders via message passing between nodes. Using random walk on networks, this scheme derives an effective similarity measure between nodes, which is closely related to community memberships of nodes. Importantly, this approach can be applied to a very broad range of networks types. In fact, the successful validation of the proposed scheme on real and synthetic networks shows that this approach can effectively (i) address the problem of resolution limit and (ii) find communities in both directed and undirected networks within a unified framework, including revealing multiple levels of robust community partitions.

Topological traps control flow on real networks: the case of coordination failures

We study evolutionary games in real social networks, with a focus on coordination games. We find that populations fail to coordinate in the same behavior for a wide range of parameters, a novel phenomenon not observed in most artificial model networks. We show that this result arises from the relevance of correlations beyond the first neighborhood, in particular from topological traps formed by links between nodes of different degrees in regions with few or no redundant paths. This specificity of real networks has not been modeled so far with synthetic networks. We thus conclude that model networks must be improved to include these mesoscopic structures, in order to successfully address issues such as the emergence of cooperation in real societies. We finally show that topological traps are a very generic phenomenon that may arise in very many different networks and fields, such as opinion models, spread of diseases or ecological networks.

Evolution of functional subnetworks in complex systems

Links in a realistic network may have different functions, which makes the network virtually a combination of some small-size functional subnetworks. Here, by a model of coupled phase oscillators, we investigate how such functional subnetworks are evolved and developed according to the network structure and dynamics. In particular, we study the case of evolutionary clustered networks in which the function type of each link (attractive or repulsive coupling) is adaptively updated according to the local network dynamics. It is found that during the process of system evolution, the network is gradually stabilized into a particular form in which the attractive (repulsive) subnetwork consists only of the intralinks (interlinks). Based on the observed properties of subnetwork evolution, we also propose a new algorithm for network partition which, compared with the conventional algorithms, is distinguished by its convenient operation and fast computing speed.

Measuring the significance of community structure in complex networks

Many complex systems can be represented as networks, and separating a network into communities could simplify functional analysis considerably. Many approaches have recently been proposed to detect communities, but a method to determine whether the detected communities are significant is still lacking. In this paper, an index to evaluate the significance of communities in networks is proposed based on perturbation of the network. In contrast to previous approaches, the network is disturbed gradually, and the index is defined by integrating all of the similarities between the community structures before and after perturbation. Moreover, by taking the null model into account, the index eliminates scale effects. Thus, it can evaluate and compare the significance of communities in different networks. The method has been tested in many artificial and real-world networks. The results show that the index is in fact independent of the size of the network and the number of communities. With this approach, clear communities are found to always exist in social networks, but significant communities cannot be found in protein interactions and metabolic networks.

Recent advances in clustering methods for protein interaction networks

The increasing availability of large-scale protein-protein interaction data has made it possible to understand the basic components and organization of cell machinery from the network level. The arising challenge is how to analyze such complex interacting data to reveal the principles of cellular organization, processes and functions. Many studies have shown that clustering protein interaction network is an effective approach for identifying protein complexes or functional modules, which has become a major research topic in systems biology. In this review, recent advances in clustering methods for protein interaction networks will be presented in detail. The predictions of protein functions and interactions based on modules will be covered. Finally, the performance of different clustering methods will be compared and the directions for future research will be discussed.

Modular organization of brain resting state networks in chronic back pain patients

Recent work on functional magnetic resonance imaging large-scale brain networks under resting conditions demonstrated its potential to evaluate the integrity of brain function under normal and pathological conditions. A similar approach is used in this work to study a group of chronic back pain patients and healthy controls to determine the impact of long enduring pain over brain dynamics. Correlation networks were constructed from the mutual partial correlations of brain activity's time series selected from ninety regions using a well validated brain parcellation atlas. The study of the resulting networks revealed an organization of up to six communities with similar modularity in both groups, but with important differences in the membership of key communities of frontal and temporal regions. The bulk of these findings were confirmed by a surprisingly naive analysis based on the pairwise correlations of the strongest and weakest correlated healthy regions. Beside confirming the brain effects of long enduring pain, these results provide a framework to study the effect of other chronic conditions over cortical function.

Module detection in complex networks using integer optimisation

BACKGROUND

The detection of modules or community structure is widely used to reveal the underlying properties of complex networks in biology, as well as physical and social sciences. Since the adoption of modularity as a measure of network topological properties, several methodologies for the discovery of community structure based on modularity maximisation have been developed. However, satisfactory partitions of large graphs with modest computational resources are particularly challenging due to the NP-hard nature of the related optimisation problem. Furthermore, it has been suggested that optimising the modularity metric can reach a resolution limit whereby the algorithm fails to detect smaller communities than a specific size in large networks.

RESULTS

We present a novel solution approach to identify community structure in large complex networks and address resolution limitations in module detection. The proposed algorithm employs modularity to express network community structure and it is based on mixed integer optimisation models. The solution procedure is extended through an iterative procedure to diminish effects that tend to agglomerate smaller modules (resolution limitations).

CONCLUSIONS

A comprehensive comparative analysis of methodologies for module detection based on modularity maximisation shows that our approach outperforms previously reported methods. Furthermore, in contrast to previous reports, we propose a strategy to handle resolution limitations in modularity maximisation. Overall, we illustrate ways to improve existing methodologies for community structure identification so as to increase its efficiency and applicability.

Improved prognostic classification of breast cancer defined by antagonistic activation patterns of immune response pathway modules

Background

Elucidating the activation pattern of molecular pathways across a given tumour type is a key challenge necessary for understanding the heterogeneity in clinical response and for developing novel more effective therapies. Gene expression signatures of molecular pathway activation derived from perturbation experiments in model systems as well as structural models of molecular interactions ("model signatures") constitute an important resource for estimating corresponding activation levels in tumours. However, relatively few strategies for estimating pathway activity from such model signatures exist and only few studies have used activation patterns of pathways to refine molecular classifications of cancer.

Methods

Here we propose a novel network-based method for estimating pathway activation in tumours from model signatures. We find that although the pathway networks inferred from cancer expression data are highly consistent with the prior information contained in the model signatures, that they also exhibit a highly modular structure and that estimation of pathway activity is dependent on this modular structure. We apply our methodology to a panel of 438 estrogen receptor negative (ER-) and 785 estrogen receptor positive (ER+) breast cancers to infer activation patterns of important cancer related molecular pathways.

Results

We show that in ER negative basal and HER2+ breast cancer, gene expression modules reflecting T-cell helper-1 (Th1) and T-cell helper-2 (Th2) mediated immune responses play antagonistic roles as major risk factors for distant metastasis. Using Boolean interaction Cox-regression models to identify non-linear pathway combinations associated with clinical outcome, we show that simultaneous high activation of Th1 and low activation of a TGF-beta pathway module defines a subtype of particularly good prognosis and that this classification provides a better prognostic model than those based on the individual pathways. In ER+ breast cancer, we find that simultaneous high MYC and RAS activity confers significantly worse prognosis than either high MYC or high RAS activity alone. We further validate these novel prognostic classifications in independent sets of 173 ER- and 567 ER+ breast cancers.

Conclusion

We have proposed a novel method for pathway activity estimation in tumours and have shown that pathway modules antagonize or synergize to delineate novel prognostic subtypes. Specifically, our results suggest that simultaneous modulation of T-helper differentiation and TGF-beta pathways may improve clinical outcome of hormone insensitive breast cancers over treatments that target only one of these pathways.

Column generation algorithms for exact modularity maximization in networks

Finding modules, or clusters, in networks currently attracts much attention in several domains. The most studied criterion for doing so, due to Newman and Girvan [Phys. Rev. E 69, 026113 (2004)], is modularity maximization. Many heuristics have been proposed for maximizing modularity and yield rapidly near optimal solution or sometimes optimal ones but without a guarantee of optimality. There are few exact algorithms, prominent among which is a paper by Xu [Eur. Phys. J. B 60, 231 (2007)]. Modularity maximization can also be expressed as a clique partitioning problem and the row generation algorithm of Grötschel and Wakabayashi [Math. Program. 45, 59 (1989)] applied. We propose to extend both of these algorithms using the powerful column generation methods for linear and non linear integer programming. Performance of the four resulting algorithms is compared on problems from the literature. Instances with up to 512 entities are solved exactly. Moreover, the computing time of previously solved problems are reduced substantially.

Combinatorial approach to modularity

Communities are clusters of nodes with a higher than average density of internal connections. Their detection is of great relevance to better understand the structure and hierarchies present in a network. Modularity has become a standard tool in the area of community detection, providing at the same time a way to evaluate partitions and, by maximizing it, a method to find communities. In this work, we study the modularity from a combinatorial point of view. Our analysis (as the modularity definition) relies on the use of the configurational model, a technique that given a graph produces a series of randomized copies keeping the degree sequence invariant. We develop an approach that enumerates the null model partitions and can be used to calculate the probability distribution function of the modularity. Our theory allows for a deep inquiry of several interesting features characterizing modularity such as its resolution limit and the statistics of the partitions that maximize it. Additionally, the study of the probability of extremes of the modularity in the random graph partitions opens the way for a definition of the statistical significance of network partitions.

Covariance, correlation matrix, and the multiscale community structure of networks

Empirical studies show that real world networks often exhibit multiple scales of topological descriptions. However, it is still an open problem how to identify the intrinsic multiple scales of networks. In this paper, we consider detecting the multiscale community structure of network from the perspective of dimension reduction. According to this perspective, a covariance matrix of network is defined to uncover the multiscale community structure through the translation and rotation transformations. It is proved that the covariance matrix is the unbiased version of the well-known modularity matrix. We then point out that the translation and rotation transformations fail to deal with the heterogeneous network, which is very common in nature and society. To address this problem, a correlation matrix is proposed through introducing the rescaling transformation into the covariance matrix. Extensive tests on real world and artificial networks demonstrate that the correlation matrix significantly outperforms the covariance matrix, identically the modularity matrix, as regards identifying the multiscale community structure of network. This work provides a novel perspective to the identification of community structure and thus various dimension reduction methods might be used for the identification of community structure. Through introducing the correlation matrix, we further conclude that the rescaling transformation is crucial to identify the multiscale community structure of network, as well as the translation and rotation transformations.