Finding communities in directed networks by PageRank random walk induced network embedding

Community structure has been found to exist ubiquitously in many different kinds of real world complex networks. Most of the previous literature ignores edge directions and applies methods designed for community finding in undirected networks to find communities. Here, we address the problem of finding communities in directed networks. Our proposed method uses PageRank random walk induced network embedding to transform a directed network into an undirected one, where the information on edge directions is effectively incorporated into the edge weights. Starting from this new undirected weighted network, previously developed methods for undirected network community finding can be used without any modification. Moreover, our method improves on recent work in terms of community definition and meaning. We provide two simulated examples, a real social network and different sets of power law benchmark networks, to illustrate how our method can correctly detect communities in directed networks.     

Directed LPA: Propagating labels in directed networks

Ignoring edge directionality and considering the graph as undirected is a common approach to detect communities in directed networks. However, it's not a meaningful way due to the loss of information captured by the edge property. Even if Leicht and Newman extended the original modularity to a directed version to address this issue, the problem of distinguishing the directionality of the edges still exists in maximizing modularity algorithms. To this direction, we extend one of the most famous scalable algorithms, namely label propagation algorithm (LPA), to a directed case, which can recognize the flow direction among nodes. To explore what properties the directed modularity should have, we also use another directed modularity, called LinkRank, and provide an empirical study. The experimental results on both real and synthetic networks demonstrate that the proposed directed algorithms can not only make use of the edge directionality but also keep the same time complexity as LPA.     

The map equation

Many real-world networks are so large that we must simplify their structure before we can extract useful information about the systems they represent. As the tools for doing these simplifications proliferate within the network literature, researchers would benefit from some guidelines about which of the so-called community detection algorithms are most appropriate for the structures they are studying and the questions they are asking. Here we show that different methods highlight different aspects of a network's structure and that the the sort of information that we seek to extract about the system must guide us in our decision. For example, many community detection algorithms, including the popular modularity maximization approach, infer module assignments from an underlying model of the network formation process. However, we are not always as interested in how a system's network structure was formed, as we are in how a network's extant structure influences the system's behavior. To see how structure influences current behavior, we will recognize that links in a network induce movement across the network and result in system-wide interdependence. In doing so, we explicitly acknowledge that most networks carry flow. To highlight and simplify the network structure with respect to this flow, we use the map equation. We present an intuitive derivation of this flow-based and information-theoretic method and provide an interactive on-line application that anyone can use to explore the mechanics of the map equation. The differences between the map equation and the modularity maximization approach are not merely conceptual. Because the map equation attends to patterns of flow on the network and the modularity maximization approach does not, the two methods can yield dramatically different results for some network structures. To illustrate this and build our understanding of each method, we partition several sample networks. We also describe an algorithm and provide source code to efficiently decompose large weighted and directed networks based on the map equation.     

Edge intensity-based community measurement in complex networks

Community is the dominant structure of complex networks. In recent years, community detection has become a heavily researched issue in network science, and many algorithms have been proposed to solve it. However, how to evaluate these algorithms and measure the strength of community structures is still an open problem. The modularity, as well as many of its variants, is widely used for this purpose, and maximizing such metrics is also a main approach to uncover communities, but this technique has a resolution limit problem in some cases, which means larger structures are favored over smaller ones. In this paper, we define the edge intensity to measure local density of network and propose an intensity-based measurement to support community evaluation; with an additional constraint the proposed measurement would also support multiresolution investigation of the networks. Experimental results on synthetic and real networks illustrate that the maximization of the new metric further reduces the resolution limit problem, and the maximization of the restricted intensity-based measurement provides multiresolution details of the investigated networks.     

Modularity density of network community divisions

The problem of dividing a network into communities is extremely complex and grows very rapidly with the number of nodes and edges that are involved. In order to develop good algorithms to identify optimal community divisions it is extremely beneficial to identify properties that are similar for most networks. We introduce the concept of modularity density, the distribution of modularity values as a function of the number of communities, and find strong indications that the general features of this modularity density are quite similar for different networks. The region of high modularity generally has very low probability density and occurs where the number of communities is small. The properties and shape of the modularity density may give valuable information and aid in the search for efficient algorithms to find community divisions with high modularities.     

Graph spectra and the detectability of community structure in networks

We study networks that display community structure--groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods, we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.     

Detecting hierarchical and overlapping network communities using locally optimal modularity changes

Agglomerative clustering is a well established strategy for identifying communities in networks. Communities are successively merged into larger communities, coarsening a network of actors into a more manageable network of communities. The order in which merges should occur is not in general clear, necessitating heuristics for selecting pairs of communities to merge. We describe a hierarchical clustering algorithm based on a local optimality property. For each edge in the network, we associate the modularity change for merging the communities it links. For each community vertex, we call the preferred edge that edge for which the modularity change is maximal. When an edge is preferred by both vertices that it links, it appears to be the optimal choice from the local viewpoint. We use the locally optimal edges to define the algorithm: simultaneously merge all pairs of communities that are connected by locally optimal edges that would increase the modularity, redetermining the locally optimal edges after each step and continuing so long as the modularity can be further increased. We apply the algorithm to model and empirical networks, demonstrating that it can efficiently produce high-quality community solutions. We relate the performance and implementation details to the structure of the resulting community hierarchies. We additionally consider a complementary local clustering algorithm, describing how to identify overlapping communities based on the local optimality condition.     

复杂网络中社团结构发现的多分辨率密度模块度

现实中的许多复杂网络呈现出明显的模块性或社团性.模块度是衡量社团结构划分优劣的效益函数, 它也通常被用作社团结构探测的目标函数,但最为广泛使用的Newman-Girvan模块度却存在着分辨率限制问题,多分辨率模块度也不能克服误合并社团和误分裂社团同时存在的缺陷. 本文在网络密度的基础上提出了多分辨率的密度模块度函数, 通过实验和分析证实了该函数能够使社团结构的误划分率显著降低, 而且能够体现出网络社团结构是一个有机整体,不是各个社团的简单相加.     

Deterministic modularity optimization

We study community structure of networks. We have developed a scheme for maximizing the modularity Q [Newman and Girvan, Phys. Rev. E 69, 026113 (2004)] based on mean field methods. Further, we have defined a simple family of random networks with community structure; we understand the behavior of these networks analytically. Using these networks, we show how the mean field methods display better performance than previously known deterministic methods for optimization of Q.     

Maximum modular graphs

Modularity has been explored as an important quantitative metric for community and cluster detection in networks. Finding the maximum modularity of a given graph has been proven to be NP-complete and therefore, several heuristic algorithms have been proposed. We investigate the problem of finding the maximum modularity of classes of graphs that have the same number of links and/or nodes and determine analytical upper bounds. Moreover, from the set of all connected graphs with a fixed number of links and/or number of nodes, we construct graphs that can attain maximum modularity, named maximum modular graphs. The maximum modularity is shown to depend on the residue obtained when the number of links is divided by the number of communities. Two applications in transportation networks and data-centers design that can benefit of maximum modular partitioning are proposed.     

Modularity functions maximization with nonnegative relaxation facilitates community detection in networks

We show here that the problem of maximizing a family of quantitative functions, encompassing both the modularity (Q-measure) and modularity density (D-measure), for community detection can be uniformly understood as a combinatoric optimization involving the trace of a matrix called modularity Laplacian. Instead of using traditional spectral relaxation, we apply additional nonnegative constraint into this graph clustering problem and design efficient algorithms to optimize the new objective. With the explicit nonnegative constraint, our solutions are very close to the ideal community indicator matrix and can directly assign nodes into communities. The near-orthogonal columns of the solution can be reformulated as the posterior probability of corresponding node belonging to each community. Therefore, the proposed method can be exploited to identify the fuzzy or overlapping communities and thus facilitates the understanding of the intrinsic structure of networks. Experimental results show that our new algorithm consistently, sometimes significantly, outperforms the traditional spectral relaxation approaches.     

Overlapping Modularity at the Critical Point of k-Clique Percolation

One of the most remarkable social phenomena is the formation of communities in social networks corresponding to families, friendship circles, work teams, etc. Since people usually belong to several different communities at the same time, the induced overlaps result in an extremely complicated web of the communities themselves. Thus, uncovering the intricate community structure of social networks is a non-trivial task with great potential for practical applications, gaining a notable interest in the recent years. The Clique Percolation Method (CPM) is one of the earliest overlapping community finding methods, which was already used in the analysis of several different social networks. In this approach the communities correspond to k-clique percolation clusters, and the general heuristic for setting the parameters of the method is to tune the system just below the critical point of k-clique percolation. However, this rule is based on simple physical principles and its validity was never subject to quantitative analysis. Here we examine the quality of the partitioning in the vicinity of the critical point using recently introduced overlapping modularity measures. According to our results on real social and other networks, the overlapping modularities show a maximum close to the critical point, justifying the original criteria for the optimal parameter settings.     

Efficient overlapping community detection in huge real-world networks

The detection of overlapping community structure in networks can give insight into the structures and functions of many complex systems. In this paper, we propose a simple but efficient overlapping community detection method for very large real-world networks. Taking a high-quality, non-overlapping partition generated by existing, efficient, non-overlapping community detection methods as input, our method identifies overlapping nodes between each pair of connected non-overlapping communities in turn. Through our analysis on modularity, we deduce that, to become an overlapping node without demolishing modularity, nodes should satisfy a specific condition presented in this paper. The proposed algorithm outputs high quality overlapping communities by efficiently identifying overlapping nodes that satisfy the above condition. Experiments on synthetic and real-world networks show that in most cases our method is better than other algorithms either in the quality of results or the computational performance. In some cases, our method is the only one that can produce overlapping communities in the very large real-world networks used in the experiments.     

Methods to find community based on edge centrality

Divisive algorithms are of great importance for community detection in complex networks. One algorithm proposed by Girvan and Newman (GN) based on an edge centrality named betweenness, is a typical representative of this field. Here we studied three edge centralities based on network topology, walks and paths respectively to quantify the relevance of each edge in a network, and proposed a divisive algorithm based on the rationale of GN algorithm for finding communities that removes edges iteratively according to the edge centrality values in a certain order. In addition, we gave a comparison analysis of these measures with the edge betweenness and information centrality. We found the principal difference among these measures in the partition procedure is that the edge centrality based on walks first removes the edge connected with a leaf vertex, but the others first delete the edge as a bridge between communities. It indicates that the edge centrality based on walks is harder to uncover communities than other edge centralities. We also tested these measures for community detection. The results showed that the edge information centrality outperforms other measures, the edge centrality based on walks obtains the worst results, and the edge betweenness gains better performance than the edge centrality based on network topology. We also discussed our method’s efficiency and found that the edge centrality based on walks has a high time complexity and is not suitable for large networks.     

Limitation of multi-resolution methods in community detection

Community detection is of considerable interest for analyzing the structure and function of complex networks. Recently, a type of multi-resolution methods in community detection was introduced, which can adjust the resolution of modularity by modifying the modularity function with tunable resolution parameters, such as those proposed by Arenas, Fernández and Gómez and by Reichardt and Bornholdt. In this paper, we show that these methods still have the intrinsic limitation–large communities may have been split before small communities become visible–because it is at the cost of the community stability that the enhancement of the modularity resolution is obtained. The theoretical results indicated that the limitation depends on the degree of interconnectedness of small communities and the difference between the sizes of small communities and of large communities, while independent of the size of the whole network. These findings have been confirmed in several example networks, where communities even are full-completed sub-graphs.     

Fuzzy modularity and fuzzy community structure in networks

To find the fuzzy community structure in a complex network, in which each node has a certain probability of belonging to a certain community, is a hard problem and not yet satisfactorily solved over the past years. In this paper, an extension of modularity, the fuzzy modularity is proposed, which can provide a measure of goodness for the fuzzy community structure in networks. The simulated annealing strategy is used to maximize the fuzzy modularity function, associating with an alternating iteration based on our previous work. The proposed algorithm can efficiently identify the probabilities of each node belonging to different communities with random initial fuzzy partition during the cooling process. An appropriate number of communities can be automatically determined without any prior knowledge about the community structure. The computational results on several artificial and real-world networks confirm the capability of the algorithm.     

Cascades with coupled map lattices in preferential attachment community networks

In this paper, cascading failure is studied by coupled map lattice （CML） methods in preferential attachment community networks. It is found that external perturbation R is increasing with modularity Q growing by simulation. In particular, the large modularity Q can hold off the cascading failure dynamic process in community networks. Furthermore, different attack strategies also greatly affect the cascading failure dynamic process. It is particularly significant to control cascading failure process in real community networks.     

Finding community structures in complex networks using mixed integer optimisation

The detection of community structure has been used to reveal the relationships between individual objects and their groupings in networks. This paper presents a mathematical programming approach to identify the optimal community structures in complex networks based on the maximisation of a network modularity metric for partitioning a network into modules. The overall problem is formulated as a mixed integer quadratic programming (MIQP) model, which can then be solved to global optimality using standard optimisation software. The solution procedure is further enhanced by developing special symmetry-breaking constraints to eliminate equivalent solutions. It is shown that additional features such as minimum/maximum module size and balancing among modules can easily be incorporated in the model. The applicability of the proposed optimisation-based approach is demonstrated by four examples. Comparative results with other approaches from the literature show that the proposed methodology has superior performance while global optimum is guaranteed.     

Structural preferential attachment: network organization beyond the link

We introduce a mechanism which models the emergence of the universal properties of complex networks, such as scale independence, modularity and self-similarity, and unifies them under a scale-free organization beyond the link. This brings a new perspective on network organization where communities, instead of links, are the fundamental building blocks of complex systems. We show how our simple model can reproduce social and information networks by predicting their community structure and more importantly, how their nodes or communities are interconnected, often in a self-similar manner.     

Detecting community structure using biased random merging

Decomposing a network into small modules or communities is beneficial for understanding the structure and dynamics of the network. One of the most prominent approaches is to repeatedly join communities together in pairs with the greatest increase in modularity so that a dendrogram that shows the order of joins is obtained. Then the community structure is acquired by cutting the dendrogram at the levels corresponding to the maximum modularity. However, there tends to be multiple pairs of communities that share the maximum modularity increment and the greedy agglomerative procedure may only merge one of them. Although the modularity function typically admits a lot of high-scoring solutions, the greedy strategy may fail to reach any of them. In this paper we propose an enhanced data structure in order to enable diverse choices of merging operations in community finding procedure. This data structure is actually a max-heap equipped with an extra array that stores the maximum modularity increments; and the corresponding community pairs is merged in the next move. By randomly sampling elements in this head array, additional diverse community structures can be efficiently extracted. The head array is designed to host the community pairs corresponding to the most significant increments in modularity so that the modularity structures obtained out of the sampling exhibit high modularity scores that are, on the average, even greater than what the CNM algorithm produces. Our method is tested on both real-world and computer-generated networks.