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.     

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.     

Place-Based Attributes Predict Community Membership in a Mobile Phone Communication Network

Social networks can be organized into communities of closely connected nodes, a property known as modularity. Because diseases, information, and behaviors spread faster within communities than between communities, understanding modularity has broad implications for public policy, epidemiology and the social sciences. Explanations for community formation in social networks often incorporate the attributes of individual people, such as gender, ethnicity or shared activities. High modularity is also a property of large-scale social networks, where each node represents a population of individuals at a location, such as call flow between mobile phone towers. However, whether or not place-based attributes, including land cover and economic activity, can predict community membership for network nodes in large-scale networks remains unknown. We describe the pattern of modularity in a mobile phone communication network in the Dominican Republic, and use a linear discriminant analysis (LDA) to determine whether geographic context can explain community membership. Our results demonstrate that place-based attributes, including sugar cane production, urbanization, distance to the nearest airport, and wealth, correctly predicted community membership for over 70% of mobile phone towers. We observed a strongly positive correlation (r = 0.97) between the modularity score and the predictive ability of the LDA, suggesting that place-based attributes can accurately represent the processes driving modularity. In the absence of social network data, the methods we present can be used to predict community membership over large scales using solely place-based attributes.     

Multi-Scale Analysis of the European Airspace Using Network Community Detection

We show that the European airspace can be represented as a multi-scale traffic network whose nodes are airports, sectors, or navigation points and links are defined and weighted according to the traffic of flights between the nodes. By using a unique database of the air traffic in the European airspace, we investigate the architecture of these networks with a special emphasis on their community structure. We propose that unsupervised network community detection algorithms can be used to monitor the current use of the airspace and improve it by guiding the design of new ones. Specifically, we compare the performance of several community detection algorithms, both with fixed and variable resolution, and also by using a null model which takes into account the spatial distance between nodes, and we discuss their ability to find communities that could be used to define new control units of the airspace.     

Spatial predictions at the community level: from current approaches to future frameworks

A fundamental goal of ecological research is to understand and model how processes generate patterns so that if conditions change, changes in the patterns can be predicted. Different approaches have been proposed for modelling species assemblage, but their use to predict spatial patterns of species richness and other community attributes over a range of spatial and temporal scales remains challenging. Different methods emphasize different processes of structuring communities and different goals. In this review, we focus on models that were developed for generating spatially explicit predictions of communities, with a particular focus on species richness, composition, relative abundance and related attributes. We first briefly describe the concepts and theories that span the different drivers of species assembly. A combination of abiotic processes and biotic mechanisms are thought to influence the community assembly process. In this review, we describe four categories of drivers: (i) historical and evolutionary, (ii) environmental, (iii) biotic, and (iv) stochastic. We discuss the different modelling approaches proposed or applied at the community level and examine them from different standpoints, i.e. the theoretical bases, the drivers included, the source data, and the expected outputs, with special emphasis on conservation needs under climate change. We also highlight the most promising novelties, possible shortcomings, and potential extensions of existing methods. Finally, we present new approaches to model and predict species assemblages by reviewing promising ‘integrative frameworks’ and views that seek to incorporate all drivers of community assembly into a unique modelling workflow. We discuss the strengths and weaknesses of these new solutions and how they may hasten progress in community‐level modelling.     

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.     

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.     

Behavior Based Social Dimensions Extraction for Multi-Label Classification

Classification based on social dimensions is commonly used to handle the multi-label classification task in heterogeneous networks. However, traditional methods, which mostly rely on the community detection algorithms to extract the latent social dimensions, produce unsatisfactory performance when community detection algorithms fail. In this paper, we propose a novel behavior based social dimensions extraction method to improve the classification performance in multi-label heterogeneous networks. In our method, nodes’ behavior features, instead of community memberships, are used to extract social dimensions. By introducing Latent Dirichlet Allocation (LDA) to model the network generation process, nodes’ connection behaviors with different communities can be extracted accurately, which are applied as latent social dimensions for classification. Experiments on various public datasets reveal that the proposed method can obtain satisfactory classification results in comparison to other state-of-the-art methods on smaller social dimensions.     

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.     

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.     

内蒙古草原植被近地面反射波谱特征与地上生物量相关关系的研究

在1994～2001年7～8月期间,对内蒙古草原的15个草地群落类型进行了反射波谱与生物学参数的测量,在1996、2001年分别对其中的7个群落开展了反射波谱与生物学参数季节变化研究,利用Duncan方差分析、主分量分析方法在3个空间尺度上讨论了不同群落类型波谱特征的差异性与可区分性。在大尺度上,草甸草原、典型草原和荒漠草原的植被反射波谱特征之间存在显著的差异,它们之间的平均鉴别错误概率小于20%,在中小尺度上,典型草原中不同群落之间波谱特征差异程度较高,平均鉴别错误概率在15%左右,而在草甸草原和荒漠草原中,不同群落之间波谱特征的差异性较小。相关分析结果指出,空间尺度和群落类型决定了地上生物量与植被指数之间相关性的大小、相关形式以及植被指数的类型,随着尺度的增大,生物量与植被指数的相关性趋于下降,在盖度较高的草原群落中,直线型的估产模型相关性最高,估测精度大于90%,而在覆盖度低于30%～40%的荒漠草原群落中, 非线性估产模型相关性最高,估测精度只有85%。对典型草原和荒漠草原估产模型的季节动态分析表明, 在6月中旬至9月中旬期间的估产模型之间没有显著差异,可以利用一个共同的估产模型来监测草地生物量季节动态。     

Mesoscopic effects in an agent-based bargaining model in regular lattices

The effect of spatial structure has been proved very relevant in repeated games. In this work we propose an agent based model where a fixed finite population of tagged agents play iteratively the Nash demand game in a regular lattice. The model extends the multiagent bargaining model by Axtell, Epstein and Young modifying the assumption of global interaction. Each agent is endowed with a memory and plays the best reply against the opponent's most frequent demand. We focus our analysis on the transient dynamics of the system, studying by computer simulation the set of states in which the system spends a considerable fraction of the time. The results show that all the possible persistent regimes in the global interaction model can also be observed in this spatial version. We also find that the mesoscopic properties of the interaction networks that the spatial distribution induces in the model have a significant impact on the diffusion of strategies, and can lead to new persistent regimes different from those found in previous research. In particular, community structure in the intratype interaction networks may cause that communities reach different persistent regimes as a consequence of the hindering diffusion effect of fluctuating agents at their borders.     

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.     

传粉网络的研究进展:网络的结构和动态

植物与传粉者之间相互作用,构成了复杂的传粉网络。近年来,社会网络分析技术的发展使得复杂生态网络的研究成为可能。从群落水平上研究植物与传粉者之间的互惠关系,为理解群落的结构和动态以及花部特征的演化提供了全新的视角。传粉网络的嵌套结构说明自然界的传粉服务存在冗余,而且是相对泛化的物种主导了传粉。在多年或者多季度的传粉网络中,虽然有很高的物种替换率,但是其网络结构仍然保持相对稳定,说明传粉网络对干扰有很强的抗性。尽管有关网络结构和动态的研究逐渐增多,但传粉网络维持的机制仍不清楚。网络结构可以部分由花部特征与传粉者的匹配来解释,也受到系统发生的制约,影响因素还包括群落构建的时间和物种多样性,以及物种在群落中的位置。开展大尺度群落动态的研究,为探索不同时间尺度、不同物种多样性水平上的传粉网络的生态学意义提供了条件。但已有的研究仍存在不足,比如基于访问观察的网络无法准确衡量传粉者的访问效率和植物间的花粉流动,以及结果受到调查精度区域研究不平衡的制约等。目前的研究只深入到传粉者携带花粉构成成分的水平,传粉者访问植物的网络不能代表植物的整个传粉过程。因此,研究应当更多地深入到物种之间关系对有性生殖的切实影响上。     

Habitat loss and fragmentation affecting mammal and bird communities—The role of interspecific competition and individual space use

Fragmentation and loss of habitat are major threats to animal communities and are therefore important to conservation. Due to the complexity of the interplay of spatial effects and community processes, our mechanistic understanding of how communities respond to such landscape changes is still poor. Modelling studies have mostly focused on elucidating the principles of community response to fragmentation and habitat loss at relatively large spatial and temporal scales relevant to metacommunity dynamics. Yet, it has been shown that also small scale processes, like foraging behaviour, space use by individuals and local resource competition are also important factors. However, most studies that consider these smaller scales are designed for single species and are characterized by high model complexity. Hence, they are not easily applicable to ecological communities of interacting individuals. To fill this gap, we apply an allometric model of individual home range formation to investigate the effects of habitat loss and fragmentation on mammal and bird communities, and, in this context, to investigate the role of interspecific competition and individual space use. Results show a similar response of both taxa to habitat loss. Community composition is shifted towards higher frequency of relatively small animals. The exponent and the 95%-quantile of the individual size distribution (ISD, described as a power law distribution) of the emerging communities show threshold behaviour with decreasing habitat area. Fragmentation per se has a similar and strong effect on mammals, but not on birds. The ISDs of bird communities were insensitive to fragmentation at the small scales considered here. These patterns can be explained by competitive release taking place in interacting animal communities, with the exception of bird's buffering response to fragmentation, presumably by adjusting the size of their home ranges. These results reflect consequences of higher mobility of birds compared to mammals of the same size and the importance of considering competitive interaction, particularly for mammal communities, in response to landscape fragmentation. Our allometric approach enables scaling up from individual physiology and foraging behaviour to terrestrial communities, and disentangling the role of individual space use and interspecific competition in controlling the response of mammal and bird communities to landscape changes.     

Spatial hierarchical approach in community ecology: a way beyond high context-dependency and low predictability in local phenomena

Patterns and functioning of communities, which are determined by a set of processes operating at a large variety of spatial and temporal scales, exhibit quite high context-dependency and low predictability at the fine spatial scales at which recent studies have concentrated. More attention to broader scale and across-scale phenomena may be useful to search for general patterns and rules in communities. In this context, it is effective to incorporate hierarchical spatial scale explicitly into the experimental and sampling design of field studies, an approach referred to here as the spatial hierarchical approach, focusing on a particular assemblage in which biological interaction and species life history are well known. The spatial hierarchical approach can provide insight into the effects of scale in operating processes and answers to a number of important questions in community ecology such as: (1) detection of patterns and processes in spatiotemporal variability in communities, including how to explain the partitioning of pattern information of species diversity at a broad scale into finer scales, and the pattern of spatial variability of community properties at the finest spatial scale; (2) evaluation of changes in patterns observed in macroecology at finer scales; (3) testing of models explaining the coexistence of competing species; and (4) detection of latitudinal patterns in spatiotemporal variability in communities and their causal processes.     

Evidence of structural balance in spatial ecological networks

Despite recent advances in applying networks to study ecological systems, most of the network datasets are built attending only to a single type of interaction between nodes, which can be an oversimplification. In the present work, we built ecological networks that had positive and negative links for multiple plant communities based on the local spatial association between species. Then, we evaluated whether those networks were in balance, a hypothesis commonly formulated for real signed graphs but never tested in systems other than social networks. Specifically, we quantified the global and the local structural balance in the networks. We found that plant community networks were more balanced than expected by chance, and that this pattern was due to a large number of balanced triads to the detriment of unbalanced ones. Furthermore, this pattern was consistent among all of the types of the plant communities examined, which suggests that configurations that promote structural balance might be common in ecological signed networks. We also found that almost all networks had some unbalanced components, which might be responsible for the adaptation of the system. Mechanisms behind these structure and possible applications for community ecology are discussed. Our results encourage testing structural balance in other ecological networks to confirm if it is a widespread architecture of natural systems.     

Discovering Communities through Friendship

We introduce a new method for detecting communities of arbitrary size in an undirected weighted network. Our approach is based on tracing the path of closest-friendship between nodes in the network using the recently proposed Generalized Erds Numbers. This method does not require the choice of any arbitrary parameters or null models, and does not suffer from a system-size resolution limit. Our closest-friend community detection is able to accurately reconstruct the true network structure for a large number of real world and artificial benchmarks, and can be adapted to study the multi-level structure of hierarchical communities as well. We also use the closeness between nodes to develop a degree of robustness for each node, which can assess how robustly that node is assigned to its community. To test the efficacy of these methods, we deploy them on a variety of well known benchmarks, a hierarchal structured artificial benchmark with a known community and robustness structure, as well as real-world networks of coauthorships between the faculty at a major university and the network of citations of articles published in Physical Review. In all cases, microcommunities, hierarchy of the communities, and variable node robustness are all observed, providing insights into the structure of the network.     

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.