Supervised reconstruction of biological networks with local models

MOTIVATION: Inference and reconstruction of biological networks from heterogeneous data is currently an active research subject with several important applications in systems biology. The problem has been attacked from many different points of view with varying degrees of success. In particular, predicting new edges with a reasonable false discovery rate is highly demanded for practical applications, but remains extremely challenging due to the sparsity of the networks of interest. RESULTS: While most previous approaches based on the partial knowledge of the network to be inferred build global models to predict new edges over the network, we introduce here a novel method which predicts whether there is an edge from a newly added vertex to each of the vertices of a known network using local models. This involves learning individually a certain subnetwork associated with each vertex of the known network, then using the discovered classification rule associated with only that vertex to predict the edge to the new vertex. Excellent experimental results are shown in the case of metabolic and protein-protein interaction network reconstruction from a variety of genomic data. AVAILABILITY: An implementation of the proposed algorithm is available upon request from the authors.     

Discovering Link Communities in Complex Networks by an Integer Programming Model and a Genetic Algorithm

Identification of communities in complex networks is an important topic and issue in many fields such as sociology, biology, and computer science. Communities are often defined as groups of related nodes or links that correspond to functional subunits in the corresponding complex systems. While most conventional approaches have focused on discovering communities of nodes, some recent studies start partitioning links to find overlapping communities straightforwardly. In this paper, we propose a new quantity function for link community identification in complex networks. Based on this quantity function we formulate the link community partition problem into an integer programming model which allows us to partition a complex network into overlapping communities. We further propose a genetic algorithm for link community detection which can partition a network into overlapping communities without knowing the number of communities. We test our model and algorithm on both artificial networks and real-world networks. The results demonstrate that the model and algorithm are efficient in detecting overlapping community structure in complex networks.     

Multi-Objective Community Detection Based on Memetic Algorithm

Community detection has drawn a lot of attention as it can provide invaluable help in understanding the function and visualizing the structure of networks. Since single objective optimization methods have intrinsic drawbacks to identifying multiple significant community structures, some methods formulate the community detection as multi-objective problems and adopt population-based evolutionary algorithms to obtain multiple community structures. Evolutionary algorithms have strong global search ability, but have difficulty in locating local optima efficiently. In this study, in order to identify multiple significant community structures more effectively, a multi-objective memetic algorithm for community detection is proposed by combining multi-objective evolutionary algorithm with a local search procedure. The local search procedure is designed by addressing three issues. Firstly, nondominated solutions generated by evolutionary operations and solutions in dominant population are set as initial individuals for local search procedure. Then, a new direction vector named as pseudonormal vector is proposed to integrate two objective functions together to form a fitness function. Finally, a network specific local search strategy based on label propagation rule is expanded to search the local optimal solutions efficiently. The extensive experiments on both artificial and real-world networks evaluate the proposed method from three aspects. Firstly, experiments on influence of local search procedure demonstrate that the local search procedure can speed up the convergence to better partitions and make the algorithm more stable. Secondly, comparisons with a set of classic community detection methods illustrate the proposed method can find single partitions effectively. Finally, the method is applied to identify hierarchical structures of networks which are beneficial for analyzing networks in multi-resolution levels.     

A Stochastic Model for Detecting Overlapping and Hierarchical Community Structure

Community detection is a fundamental problem in the analysis of complex networks. Recently, many researchers have concentrated on the detection of overlapping communities, where a vertex may belong to more than one community. However, most current methods require the number (or the size) of the communities as a priori information, which is usually unavailable in real-world networks. Thus, a practical algorithm should not only find the overlapping community structure, but also automatically determine the number of communities. Furthermore, it is preferable if this method is able to reveal the hierarchical structure of networks as well. In this work, we firstly propose a generative model that employs a nonnegative matrix factorization (NMF) formulization with a l_2,1 norm regularization term, balanced by a resolution parameter. The NMF has the nature that provides overlapping community structure by assigning soft membership variables to each vertex; the l_2,1 regularization term is a technique of group sparsity which can automatically determine the number of communities by penalizing too many nonempty communities; and hence the resolution parameter enables us to explore the hierarchical structure of networks. Thereafter, we derive the multiplicative update rule to learn the model parameters, and offer the proof of its correctness. Finally, we test our approach on a variety of synthetic and real-world networks, and compare it with some state-of-the-art algorithms. The results validate the superior performance of our new method.     

An Efficient Immunization Strategy for Community Networks

An efficient algorithm that can properly identify the targets to immunize or quarantine for preventing an epidemic in a population without knowing the global structural information is of obvious importance. Typically, a population is characterized by its community structure and the heterogeneity in the weak ties among nodes bridging over communities. We propose and study an effective algorithm that searches for bridge hubs, which are bridge nodes with a larger number of weak ties, as immunizing targets based on the idea of referencing to an expanding friendship circle as a self-avoiding walk proceeds. Applying the algorithm to simulated networks and empirical networks constructed from social network data of five US universities, we show that the algorithm is more effective than other existing local algorithms for a given immunization coverage, with a reduced final epidemic ratio, lower peak prevalence and fewer nodes that need to be visited before identifying the target nodes. The effectiveness stems from the breaking up of community networks by successful searches on target nodes with more weak ties. The effectiveness remains robust even when errors exist in the structure of the networks.     

Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit

In recent years, there has been a surge of interest in community detection algorithms for complex networks. A variety of computational heuristics, some with a long history, have been proposed for the identification of communities or, alternatively, of good graph partitions. In most cases, the algorithms maximize a particular objective function, thereby finding the 'right' split into communities. Although a thorough comparison of algorithms is still lacking, there has been an effort to design benchmarks, i.e., random graph models with known community structure against which algorithms can be evaluated. However, popular community detection methods and benchmarks normally assume an implicit notion of community based on clique-like subgraphs, a form of community structure that is not always characteristic of real networks. Specifically, networks that emerge from geometric constraints can have natural non clique-like substructures with large effective diameters, which can be interpreted as long-range communities. In this work, we show that long-range communities escape detection by popular methods, which are blinded by a restricted 'field-of-view' limit, an intrinsic upper scale on the communities they can detect. The field-of-view limit means that long-range communities tend to be overpartitioned. We show how by adopting a dynamical perspective towards community detection [1], [2], in which the evolution of a Markov process on the graph is used as a zooming lens over the structure of the network at all scales, one can detect both clique- or non clique-like communities without imposing an upper scale to the detection. Consequently, the performance of algorithms on inherently low-diameter, clique-like benchmarks may not always be indicative of equally good results in real networks with local, sparser connectivity. We illustrate our ideas with constructive examples and through the analysis of real-world networks from imaging, protein structures and the power grid, where a multiscale structure of non clique-like communities is revealed.     

Dynamics and Control of Diseases in Networks with Community Structure

The dynamics of infectious diseases spread via direct person-to-person transmission (such as influenza, smallpox, HIV/AIDS, etc.) depends on the underlying host contact network. Human contact networks exhibit strong community structure. Understanding how such community structure affects epidemics may provide insights for preventing the spread of disease between communities by changing the structure of the contact network through pharmaceutical or non-pharmaceutical interventions. We use empirical and simulated networks to investigate the spread of disease in networks with community structure. We find that community structure has a major impact on disease dynamics, and we show that in networks with strong community structure, immunization interventions targeted at individuals bridging communities are more effective than those simply targeting highly connected individuals. Because the structure of relevant contact networks is generally not known, and vaccine supply is often limited, there is great need for efficient vaccination algorithms that do not require full knowledge of the network. We developed an algorithm that acts only on locally available network information and is able to quickly identify targets for successful immunization intervention. The algorithm generally outperforms existing algorithms when vaccine supply is limited, particularly in networks with strong community structure. Understanding the spread of infectious diseases and designing optimal control strategies is a major goal of public health. Social networks show marked patterns of community structure, and our results, based on empirical and simulated data, demonstrate that community structure strongly affects disease dynamics. These results have implications for the design of control strategies.     

残基相互作用网络特征与木聚糖酶耐热性的关系

残基相互作用网络是体现蛋白质中残基与残基之间协同和制约关系的重要形式。残基相互作用网络的拓扑性质以及社团结构与蛋白质的功能和性质有密切的关系。本文在构建一系列耐热木聚糖酶和常温木聚糖酶的残基相互作用网络后,通过计算网络的度、聚类系数、连接强度、特征路径长度、接近中心性、介数中心性等拓扑参数来确定网络拓扑结构与木聚糖酶耐热性的关系。识别残基相互作用网络的hub点,分析hub点的亲疏水性、带电性以及各种氨基酸在hub点中所占的比例。进一步使用GA-Net算法对网络进行社团划分,并计算社团的规模、直径和密度。网络的高平均度、高连接强度、以及更短的最短路径等表明耐热木聚糖酶残基相互作用网络的结构更加紧密;耐热木聚糖酶网络中的hub节点比常温木聚糖酶网络hub节点具有更多的疏水性残基,hub点中Phe、Ile、Val的占比更高。社团检测后发现,耐热木聚糖酶网络拥有更大的社团规模、较小的社团直径和较大的社团密度。社团规模越大表明耐热木聚糖酶的氨基酸残基更倾向于形成大的社团,而较小的社团直径和较大的社团密度则表明社团内部氨基酸残基的相互作用比常温木聚糖酶更强。     

Disentangling the effects of local and regional processes on biodiversity patterns through taxon‐contingent metacommunity network analysis

Metacommunity theory, which has gained a central position in ecology, accounts for the role of migration in patterns of diversity among communities at different scales. Community isolation has a main role in this theory, but is difficult to estimate empirically, partly due to the taxon‐dependent nature of dispersal. Landscapes could be perceived as either fragmented or connected for organisms with contrasting dispersal abilities. Indeed, the dispersal ability of a taxon, and the spatial scale at which eco‐evolutionary processes shape local diversity, determine a taxon‐dependent metacommunity network. In this paper, we introduce a methodology using graph theory to define this taxon‐dependent metacommunity network and then to estimate the isolation of local communities. We analyzed the relative importance of local conditions versus community isolation as determinants of community richness for 25 taxa inhabiting 18 temporary ponds. Although local factors have been the foci of most previous empirical and theoretical considerations, we demonstrate that the metacommunity network is an equally important contributor to local diversity. We also found that the relative effect of local conditions and the metacommunity network depend on body size and taxon abundance. Local diversity of larger species was more affected by patch isolation, while taxon abundances were associated with positive or negative effects of isolation. Our results provide empirical support for the proposed role of metacommunity networks as determinants of community diversity and show the taxon‐dependent nature of these networks.     

残基相互作用网络特征与木聚糖酶耐热性的关系

残基相互作用网络是体现蛋白质中残基与残基之间协同和制约关系的重要形式。残基相互作用网络的拓扑性质以及社团结构与蛋白质的功能和性质有密切的关系。本文在构建一系列耐热木聚糖酶和常温木聚糖酶的残基相互作用网络后,通过计算网络的度、聚类系数、连接强度、特征路径长度、接近中心性、介数中心性等拓扑参数来确定网络拓扑结构与木聚糖酶耐热性的关系。识别残基相互作用网络的hub点,分析hub点的亲疏水性、带电性以及各种氨基酸在hub点中所占的比例。进一步使用GA-Net算法对网络进行社团划分,并计算社团的规模、直径和密度。网络的高平均度、高连接强度、以及更短的最短路径等表明耐热木聚糖酶残基相互作用网络的结构更加紧密;耐热木聚糖酶网络中的hub节点比常温木聚糖酶网络hub节点具有更多的疏水性残基,hub点中Phe、Ile、Val的占比更高。社团检测后发现,耐热木聚糖酶网络拥有更大的社团规模、较小的社团直径和较大的社团密度。社团规模越大表明耐热木聚糖酶的氨基酸残基更倾向于形成大的社团,而较小的社团直径和较大的社团密度则表明社团内部氨基酸残基的相互作用比常温木聚糖酶更强。     

Consistent estimation of the number of communities via regularized network embedding

The network analysis plays an important role in numerous application domains including biomedicine. Estimation of the number of communities is a fundamental and critical issue in network analysis. Most existing studies assume that the number of communities is known a priori, or lack of rigorous theoretical guarantee on the estimation consistency. In this paper, we propose a regularized network embedding model to simultaneously estimate the community structure and the number of communities in a unified formulation. The proposed model equips network embedding with a novel composite regularization term, which pushes the embedding vector toward its center and pushes similar community centers collapsed with each other. A rigorous theoretical analysis is conducted, establishing asymptotic consistency in terms of community detection and estimation of the number of communities. Extensive numerical experiments have also been conducted on both synthetic networks and brain functional connectivity network, which demonstrate the superior performance of the proposed method compared with existing alternatives.     

Motifs in the assembly of food web networks

The assembly of local communities from regional pools is a multifaceted process that involves the confluence of interactions and environmental conditions at the local scale and biogeographic and evolutionary history at the regional scale. Understanding the relative influence of these factors on community structure has remained a challenge and mechanisms driving community assembly are often inferred from patterns of taxonomic, functional, and phylogenetic diversity. Moreover, community assembly is often viewed through the lens of competition and rarely includes trophic interactions or entire food webs. Here, we use motifs – subgraphs of nodes (e.g. species) and links (e.g. predation) whose abundance within a network deviates significantly as compared to a random network topology – to explore the assembly of food web networks found in the leaves of the northern pitcher plant Sarracenia purpurea. We compared counts of three‐node motifs across a hierarchy of scales to a suite of null models to determine if motifs are over‐, under‐, or randomly represented. We then assessed if the pattern of representation of a motif in a given network matched that of the network it was assembled from. We found that motif representation in over 70% of site networks matched the continental network they were assembled from and over 75% of local networks matched the site networks they were assembled from for the majority of null models. This suggests that the same processes are shaping networks across scales. To generalize our results and effectively use a motif perspective to study community assembly, a theoretical framework detailing potential mechanisms for all possible combinations of motif representation is necessary.     

Netgram: Visualizing Communities in Evolving Networks

Real-world complex networks are dynamic in nature and change over time. The change is usually observed in the interactions within the network over time. Complex networks exhibit community like structures. A key feature of the dynamics of complex networks is the evolution of communities over time. Several methods have been proposed to detect and track the evolution of these groups over time. However, there is no generic tool which visualizes all the aspects of group evolution in dynamic networks including birth, death, splitting, merging, expansion, shrinkage and continuation of groups. In this paper, we propose Netgram: a tool for visualizing evolution of communities in time-evolving graphs. Netgram maintains evolution of communities over 2 consecutive time-stamps in tables which are used to create a query database using the sql outer-join operation. It uses a line-based visualization technique which adheres to certain design principles and aesthetic guidelines. Netgram uses a greedy solution to order the initial community information provided by the evolutionary clustering technique such that we have fewer line cross-overs in the visualization. This makes it easier to track the progress of individual communities in time evolving graphs. Netgram is a generic toolkit which can be used with any evolutionary community detection algorithm as illustrated in our experiments. We use Netgram for visualization of topic evolution in the NIPS conference over a period of 11 years and observe the emergence and merging of several disciplines in the field of information processing systems.     

Manipulation of local environment produces different diversity outcomes depending on location within a river network

Ecologists have long been interested in mechanisms governing community composition and assembly. Spatial connectivity is one potential mechanism that can have a large influence on community processes. In accordance with network metrics such as closeness and betweenness, headwater streams are more isolated than mainstem streams. Theory and observational studies predict that community structure in isolated locations of dispersal networks should respond more strongly to manipulations of local conditions, whereas well-connected communities subject to high levels of dispersal should not respond strongly to local manipulations. We experimentally investigated this prediction by manipulating habitat complexity in headwaters and mainstem streams while monitoring macroinvertebrate communities through time. As predicted, the manipulation of local habitat had a stronger influence in headwaters than mainstreams. Both taxon richness and community similarity showed strong responses to alterations in habitat complexity in headwaters, but not in mainstem streams. These findings support the hypothesis that location within a dispersal network affects the relative importance of local and regional factors in structuring the local communities within a spatially structured metacommunity. In addition, our results suggest that conservation strategies need to account for the possibility that the relative importance of local and regional drivers of community composition and assembly can vary spatially.     

Fast Fragmentation of Networks Using Module-Based Attacks

In the multidisciplinary field of Network Science, optimization of procedures for efficiently breaking complex networks is attracting much attention from a practical point of view. In this contribution, we present a module-based method to efficiently fragment complex networks. The procedure firstly identifies topological communities through which the network can be represented using a well established heuristic algorithm of community finding. Then only the nodes that participate of inter-community links are removed in descending order of their betweenness centrality. We illustrate the method by applying it to a variety of examples in the social, infrastructure, and biological fields. It is shown that the module-based approach always outperforms targeted attacks to vertices based on node degree or betweenness centrality rankings, with gains in efficiency strongly related to the modularity of the network. Remarkably, in the US power grid case, by deleting 3% of the nodes, the proposed method breaks the original network in fragments which are twenty times smaller in size than the fragments left by betweenness-based attack.     

Generating Attributed Networks with Communities

In many modern applications data is represented in the form of nodes and their relationships, forming an information network. When nodes are described with a set of attributes we have an attributed network. Nodes and their relationships tend to naturally form into communities or clusters, and discovering these communities is paramount to many applications. Evaluating algorithms or comparing algorithms for automatic discovery of communities requires networks with known structures. Synthetic generators of networks have been proposed for this task but most solely focus on connectivity and their properties and overlook attribute values and the network properties vis-à-vis these attributes. In this paper, we propose a new generator for attributed networks with community structure that dependably follows the properties of real world networks.     

A complex speciation-richness relationship in a simple neutral model

Speciation is the "elephant in the room" of community ecology. As the ultimate source of biodiversity, its integration in ecology's theoretical corpus is necessary to understand community assembly. Yet, speciation is often completely ignored or stripped of its spatial dimension. Recent approaches based on network theory have allowed ecologists to effectively model complex landscapes. In this study, we use this framework to model allopatric and parapatric speciation in networks of communities. We focus on the relationship between speciation, richness, and the spatial structure of communities. We find a strong opposition between speciation and local richness, with speciation being more common in isolated communities and local richness being higher in more connected communities. Unlike previous models, we also find a transition to a positive relationship between speciation and local richness when dispersal is low and the number of communities is small. We use several measures of centrality to characterize the effect of network structure on diversity. The degree, the simplest measure of centrality, is the best predictor of local richness and speciation, although it loses some of its predictive power as connectivity grows. Our framework shows how a simple neutral model can be combined with network theory to reveal complex relationships between speciation, richness, and the spatial organization of populations.     

A Novel Top-k Strategy for Influence Maximization in Complex Networks with Community Structure

In complex networks, it is of great theoretical and practical significance to identify a set of critical spreaders which help to control the spreading process. Some classic methods are proposed to identify multiple spreaders. However, they sometimes have limitations for the networks with community structure because many chosen spreaders may be clustered in a community. In this paper, we suggest a novel method to identify multiple spreaders from communities in a balanced way. The network is first divided into a great many super nodes and then k spreaders are selected from these super nodes. Experimental results on real and synthetic networks with community structure show that our method outperforms the classic methods for degree centrality, k-core and ClusterRank in most cases.     

A Shadowing Problem in the Detection of Overlapping Communities: Lifting the Resolution Limit through a Cascading Procedure

Community detection is the process of assigning nodes and links in significant communities (e.g. clusters, function modules) and its development has led to a better understanding of complex networks. When applied to sizable networks, we argue that most detection algorithms correctly identify prominent communities, but fail to do so across multiple scales. As a result, a significant fraction of the network is left uncharted. We show that this problem stems from larger or denser communities overshadowing smaller or sparser ones, and that this effect accounts for most of the undetected communities and unassigned links. We propose a generic cascading approach to community detection that circumvents the problem. Using real and artificial network datasets with three widely used community detection algorithms, we show how a simple cascading procedure allows for the detection of the missing communities. This work highlights a new detection limit of community structure, and we hope that our approach can inspire better community detection algorithms.