Link Community Detection Using Generative Model and Nonnegative Matrix Factorization

Discovery of communities in complex networks is a fundamental data analysis problem with applications in various domains. While most of the existing approaches have focused on discovering communities of nodes, recent studies have shown the advantages and uses of link community discovery in networks. Generative models provide a promising class of techniques for the identification of modular structures in networks, but most generative models mainly focus on the detection of node communities rather than link communities. In this work, we propose a generative model, which is based on the importance of each node when forming links in each community, to describe the structure of link communities. We proceed to fit the model parameters by taking it as an optimization problem, and solve it using nonnegative matrix factorization. Thereafter, in order to automatically determine the number of communities, we extend the above method by introducing a strategy of iterative bipartition. This extended method not only finds the number of communities all by itself, but also obtains high efficiency, and thus it is more suitable to deal with large and unexplored real networks. We test this approach on both synthetic benchmarks and real-world networks including an application on a large biological network, and compare it with two highly related methods. Results demonstrate the superior performance of our approach over competing methods for the detection of link communities.     

Dynamic Social Community Detection and Its Applications

Community structure is one of the most commonly observed features of Online Social Networks (OSNs) in reality. The knowledge of this feature is of great advantage: it not only provides helpful insights into developing more efficient social-aware solutions but also promises a wide range of applications enabled by social and mobile networking, such as routing strategies in Mobile Ad Hoc Networks (MANETs) and worm containment in OSNs. Unfortunately, understanding this structure is very challenging, especially in dynamic social networks where social interactions are evolving rapidly. Our work focuses on the following questions: How can we efficiently identify communities in dynamic social networks? How can we adaptively update the network community structure based on its history instead of recomputing from scratch? To this end, we present Quick Community Adaptation (QCA), an adaptive modularity-based framework for not only discovering but also tracing the evolution of network communities in dynamic OSNs. QCA is very fast and efficient in the sense that it adaptively updates and discovers the new community structure based on its history together with the network changes only. This flexible approach makes QCA an ideal framework applicable for analyzing large-scale dynamic social networks due to its lightweight computing-resource requirement. To illustrate the effectiveness of our framework, we extensively test QCA on both synthesized and real-world social networks including Enron, arXiv e-print citation, and Facebook networks. Finally, we demonstrate the applicability of QCA in real applications: (1) A social-aware message forwarding strategy in MANETs, and (2) worm propagation containment in OSNs. Competitive results in comparison with other methods reveal that social-based techniques employing QCA as a community detection core outperform current available methods.     

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.     

Community Landscapes: An Integrative Approach to Determine Overlapping Network Module Hierarchy,Identify Key Nodes and Predict Network Dynamics

Background

Network communities help the functional organization and evolution of complex networks. However, the development of a method, which is both fast and accurate, provides modular overlaps and partitions of a heterogeneous network, has proven to be rather difficult.

Methodology/Principal Findings

Here we introduce the novel concept of ModuLand, an integrative method family determining overlapping network modules as hills of an influence function-based, centrality-type community landscape, and including several widely used modularization methods as special cases. As various adaptations of the method family, we developed several algorithms, which provide an efficient analysis of weighted and directed networks, and (1) determine pervasively overlapping modules with high resolution; (2) uncover a detailed hierarchical network structure allowing an efficient, zoom-in analysis of large networks; (3) allow the determination of key network nodes and (4) help to predict network dynamics.

Conclusions/Significance

The concept opens a wide range of possibilities to develop new approaches and applications including network routing, classification, comparison and prediction.     

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.     

Network frailty and the geometry of herd immunity

The spread of infectious disease through communities depends fundamentally on the underlying patterns of contacts between individuals. Generally, the more contacts one individual has, the more vulnerable they are to infection during an epidemic. Thus, outbreaks disproportionately impact the most highly connected demographics. Epidemics can then lead, through immunization or removal of individuals, to sparser networks that are more resistant to future transmission of a given disease. Using several classes of contact networks-Poisson, scale-free and small-world-we characterize the structural evolution of a network due to an epidemic in terms of frailty (the degree to which highly connected individuals are more vulnerable to infection) and interference (the extent to which the epidemic cuts off connectivity among the susceptible population that remains following an epidemic). The evolution of the susceptible network over the course of an epidemic differs among the classes of networks; frailty, relative to interference, accounts for an increasing component of network evolution on networks with greater variance in contacts. The result is that immunization due to prior epidemics can provide greater community protection than random vaccination on networks with heterogeneous contact patterns, while the reverse is true for highly structured populations.     

Characterizing the Community Structure of Complex Networks

Background

Community structure is one of the key properties of complex networks and plays a crucial role in their topology and function. While an impressive amount of work has been done on the issue of community detection, very little attention has been so far devoted to the investigation of communities in real networks.

Methodology/Principal Findings

We present a systematic empirical analysis of the statistical properties of communities in large information, communication, technological, biological, and social networks. We find that the mesoscopic organization of networks of the same category is remarkably similar. This is reflected in several characteristics of community structure, which can be used as “fingerprints” of specific network categories. While community size distributions are always broad, certain categories of networks consist mainly of tree-like communities, while others have denser modules. Average path lengths within communities initially grow logarithmically with community size, but the growth saturates or slows down for communities larger than a characteristic size. This behaviour is related to the presence of hubs within communities, whose roles differ across categories. Also the community embeddedness of nodes, measured in terms of the fraction of links within their communities, has a characteristic distribution for each category.

Conclusions/Significance

Our findings, verified by the use of two fundamentally different community detection methods, allow for a classification of real networks and pave the way to a realistic modelling of networks'' evolution.     

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.     

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.     

Structure and dynamics of pollination networks: the role of alien plants

Research on ecological communities, and plant–pollinator mutualistic networks in particular, has increasingly benefited from the theory and tools of complexity science. Nevertheless, up to now there have been few attempts to investigate the interplay between the structure of real pollination networks and their dynamics. This study is one of the first contributions to explore this issue. Biological invasions, of major concern for conservation, are also poorly understood from the perspective of complex ecological networks. In this paper we assess the role that established alien species play within a host community by analyzing the temporal changes in structural network properties driven by the removal of non‐native plants. Three topological measures have been used to represent the most relevant structural properties for the stability of ecological networks: degree distribution, nestedness, and modularity. Therefore, we investigate for a detailed pollination network, 1) how its dynamics, represented as changes in species abundances, affect the evolution of its structure, 2) how topology relates to dynamics focusing on long‐term species persistence; and 3) how both structure and dynamics are affected by the removal of alien plant species. Network dynamics were simulated by means of a stochastic metacommunity model. Our results showed that established alien plants are important for the persistence of the pollination network and for the maintenance of its structure. Removal of alien plants decreased the likelihood of species persistence. On the other hand, both the full network and the subset native network tended to lose their structure through time. Nevertheless, the structure of the full network was better preserved than the structure of the network without alien plants. Temporal topological shifts were evident in terms of degree distribution, nestedness, and modularity. However the effects of removing alien plants were more pronounced for degree distribution and modularity of the network. Therefore, elimination of alien plants affected the evolution of the architecture of the interaction web, which was closely related to the higher species loss found in the network where alien plants were removed.     

Relative stability of core groups in pollination networks in a biodiversity hotspot over four years

Plants and their pollinators form pollination networks integral to the evolution and persistence of species in communities. Previous studies suggest that pollination network structure remains nested while network composition is highly dynamic. However, little is known about temporal variation in the structure and function of plant-pollinator networks, especially in species-rich communities where the strength of pollinator competition is predicted to be high. Here we quantify temporal variation of pollination networks over four consecutive years in an alpine meadow in the Hengduan Mountains biodiversity hotspot in China. We found that ranked positions and idiosyncratic temperatures of both plants and pollinators were more conservative between consecutive years than in non-consecutive years. Although network compositions exhibited high turnover, generalized core groups--decomposed by a k-core algorithm--were much more stable than peripheral groups. Given the high rate of turnover observed, we suggest that identical plants and pollinators that persist for at least two successive years sustain pollination services at the community level. Our data do not support theoretical predictions of a high proportion of specialized links within species-rich communities. Plants were relatively specialized, exhibiting less variability in pollinator composition at pollinator functional group level than at the species level. Both specialized and generalized plants experienced narrow variation in functional pollinator groups. The dynamic nature of pollination networks in the alpine meadow demonstrates the potential for networks to mitigate the effects of fluctuations in species composition in a high biodiversity area.     

Discovering Preferential Patterns in Sectoral Trade Networks

We analyze the patterns of import/export bilateral relations, with the aim of assessing the relevance and shape of “preferentiality” in countries’ trade decisions. Preferentiality here is defined as the tendency to concentrate trade on one or few partners. With this purpose, we adopt a systemic approach through the use of the tools of complex network analysis. In particular, we apply a pattern detection approach based on community and pseudocommunity analysis, in order to highlight the groups of countries within which most of members’ trade occur. The method is applied to two intra-industry trade networks consisting of 221 countries, relative to the low-tech “Textiles and Textile Articles” and the high-tech “Electronics” sectors for the year 2006, to look at the structure of world trade before the start of the international financial crisis. It turns out that the two networks display some similarities and some differences in preferential trade patterns: they both include few significant communities that define narrow sets of countries trading with each other as preferential destinations markets or supply sources, and they are characterized by the presence of similar hierarchical structures, led by the largest economies. But there are also distinctive features due to the characteristics of the industries examined, in which the organization of production and the destination markets are different. Overall, the extent of preferentiality and partner selection at the sector level confirm the relevance of international trade costs still today, inducing countries to seek the highest efficiency in their trade patterns.     

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

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

A comprehensive examination of the network position hypothesis across multiple river metacommunities

The hierarchical branching nature of river networks can have a strong influence on the assembly of freshwater communities. This unique structure has spurred the development of the network position hypothesis (NPH), which states that the strength of different assembly processes depends on the community position in the river network. Specifically, it predicts that 1) headwater communities should be exclusively controlled by the local environment given that they are more isolated and environmentally heterogeneous relative to downstream reaches. In contrast, 2) downstream communities should be regulated by both environmental and dispersal processes due to increased connectivity given their central position in the riverscape. Although intuitive, the NPH has only been evaluated on a few catchments and it is not yet clear whether its predictions are generalizable. To fill this gap, we tested the NPH on river dwelling fishes using an extensive dataset from 28 French catchments. Stream and climatic variables were assembled to characterize environmental conditions and graph theory was applied on river networks to create spatial variables. We tested both predictions using variation partitioning analyses separately for headwater and downstream sites in each catchment. Only 10 catchments supported both predictions, 11 failed to support at least one of them, while in 7 the NPH was partially supported given that spatial variables were also significant for headwater communities. We then assembled a dataset at the catchment scale (e.g. topography, environmental heterogeneity, network connectivity) and applied a classification tree analysis (CTA) to determine which regional property could explain these results. The CTA showed that the NPH was not supported in catchments with high heterogeneity in connectivity among sites. In more homogeneously connected catchments, the NPH was only supported when headwaters were more environmentally heterogeneous than downstream sites. We conclude that the NPH is context dependent even for taxa dispersing exclusively within streams.     

The overlapping community structure of structural brain network in young healthy individuals

Community structure is a universal and significant feature of many complex networks in biology, society, and economics. Community structure has also been revealed in human brain structural and functional networks in previous studies. However, communities overlap and share many edges and nodes. Uncovering the overlapping community structure of complex networks remains largely unknown in human brain networks. Here, using regional gray matter volume, we investigated the structural brain network among 90 brain regions (according to a predefined anatomical atlas) in 462 young, healthy individuals. Overlapped nodes between communities were defined by assuming that nodes (brain regions) can belong to more than one community. We demonstrated that 90 brain regions were organized into 5 overlapping communities associated with several well-known brain systems, such as the auditory/language, visuospatial, emotion, decision-making, social, control of action, memory/learning, and visual systems. The overlapped nodes were mostly involved in an inferior-posterior pattern and were primarily related to auditory and visual perception. The overlapped nodes were mainly attributed to brain regions with higher node degrees and nodal efficiency and played a pivotal role in the flow of information through the structural brain network. Our results revealed fuzzy boundaries between communities by identifying overlapped nodes and provided new insights into the understanding of the relationship between the structure and function of the human brain. This study provides the first report of the overlapping community structure of the structural network of the human brain.     

Hidden Information Revealed by Optimal Community Structure from a Protein-Complex Bipartite Network Improves Protein Function Prediction

The task of extracting the maximal amount of information from a biological network has drawn much attention from researchers, for example, predicting the function of a protein from a protein-protein interaction (PPI) network. It is well known that biological networks consist of modules/communities, a set of nodes that are more densely inter-connected among themselves than with the rest of the network. However, practical applications of utilizing the community information have been rather limited. For protein function prediction on a network, it has been shown that none of the existing community-based protein function prediction methods outperform a simple neighbor-based method. Recently, we have shown that proper utilization of a highly optimal modularity community structure for protein function prediction can outperform neighbor-assisted methods. In this study, we propose two function prediction approaches on bipartite networks that consider the community structure information as well as the neighbor information from the network: 1) a simple screening method and 2) a random forest based method. We demonstrate that our community-assisted methods outperform neighbor-assisted methods and the random forest method yields the best performance. In addition, we show that using the optimal community structure information is essential for more accurate function prediction for the protein-complex bipartite network of Saccharomyces cerevisiae. Community detection can be carried out either using a modified modularity for dealing with the original bipartite network or first projecting the network into a single-mode network (i.e., PPI network) and then applying community detection to the reduced network. We find that the projection leads to the loss of information in a significant way. Since our prediction methods rely only on the network topology, they can be applied to various fields where an efficient network-based analysis is required.     

Insights into the structure of plant-insect communities: Specialism and generalism in a regional set of non-pollinating fig wasp communities

Insects show a multitude of symbiotic interactions that may vary in degree of specialization and structure. Gall-inducing insects and their parasitoids are thought to be relatively specialized organisms, but despite their ecological importance, the organization and structure of the interactions they establish with their hosts has seldom been investigated in tropical communities. Non-pollinating fig wasps (NPFW) are particularly interesting organisms for the study of ecological networks because most species strictly develop their offspring within fig inflorescences, and show a multitude of life history strategies. They can be gall-makers, cleptoparasites or parasitoids of pollinating or of other non-pollinating fig wasps. Here we analysed a set of non-pollinating fig wasp communities associated with six species of Ficus section Americanae over a wide area. This allowed us to investigate patterns of specialization in a diverse community composed of monophagous and polyphagous species. We observed that most NPFW species were cleptoparasites and parasitoids, colonizing figs several days after oviposition by pollinators. Most species that occurred in more than one host were much more abundant in a single preferential host, suggesting specialization. The food web established between wasps and figs shows structural properties that are typical of specific antagonistic relationships, especially of endophagous insect networks. Two species that occurred in all available hosts were highly abundant in the network, suggesting that in some cases generalized species can be more competitive than strict specialists. The Neotropical and, to a lesser extent, Afrotropical NPFW communities seem to be more generalized than other NPFW communities. However, evidence of host sharing in the Old World is quite limited, since most studies have focused on particular taxonomic groups (genera) of wasps instead of sampling the whole NPFW community. Moreover, the lack of quantitative information in previous studies prevents us from detecting patterns of host preferences in polyphagous species.     

The legacy of transnational lives: Beyond the first generation of Lebanese in Senegal

Definitions of transnationalism are modelled after first generation migrant communities in the west. Through presenting ethnographic detail on the Lebanese community in Senegal, this article applies the concept of transnationalism to the case of a historic South-South migrant community. Second and later generation ethnic groups maintain transnational ties through notions of self-identity and definitions by others, the importance given to the homeland, and political and religious ideologies. Race, geographic location, and changes in the structure of labour markets are factors that encourage continued ties with the country of origin. Furthermore, transnationalism cannot be limited only to sending and receiving countries. Colonial and former colonial powers can determine the destination of migrants, establish economic hierarchies, and offer a tertiary citizenship to transnational migrants in addition to the dual citizenship of country of origin and destination.