Advanced modularity-specialized label propagation algorithm for detecting communities in networks

A modularity-specialized label propagation algorithm (LPAm) for detecting network communities was recently proposed. This promising algorithm offers some desirable qualities. However, LPAm favors community divisions where all communities are similar in total degree and thus it is prone to get stuck in poor local maxima in the modularity space. To escape local maxima, we employ a multistep greedy agglomerative algorithm (MSG) that can merge multiple pairs of communities at a time. Combining LPAm and MSG, we propose an advanced modularity-specialized label propagation algorithm (LPAm+). Experiments show that LPAm+ successfully detects communities with higher modularity values than ever reported in two commonly used real-world networks. Moreover, LPAm+ offers a fair compromise between accuracy and speed.     

Recursive filtration method for detecting community structure in networks

Community detection is a topic of considerable recent interest within complex networks, but most methods proposed so far are divisive and agglomerative methods which delete only one edge each time to split the network, or agglomerating only one node each time until no individual node remains. Unlike those, we propose a method to split networks in parallel by deleting many edges in each filtration operation, and propose a community recursive coefficient (CRC) denoted by M instead of Q (modularity) to quantify the effect of the splitting results in this paper. We proved that recursive optimizing of the local M is equivalent to acquiring the maximal global Q value corresponding to good divisions. For a network with m edges, c communities and arbitrary topology, the method split the network at most c+1 times and detected the community structure in time O(m²+(c+1)m). We give several example applications, and show that the method can detect local communities according to the densities of external links to them in increasing order especially in large networks.     

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.     

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.     

EAMCD: an efficient algorithm based on minimum coupling distance for community identification in complex networks

Community structure is an important feature in many real-world networks, which can help us understand structure and function in complex networks better. In recent years, there have been many algorithms proposed to detect community structure in complex networks. In this paper, we try to detect potential community beams whose link strengths are greater than surrounding links and propose the minimum coupling distance (MCD) between community beams. Based on MCD, we put forward an optimization heuristic algorithm (EAMCD) for modularity density function to welded these community beams into community frames which are seen as a core part of community. Using the principle of random walk, we regard the remaining nodes into the community frame to form a community. At last, we merge several small community frame fragments using local greedy strategy for the modularity density general function. Real-world and synthetic networks are used to demonstrate the effectiveness of our algorithm in detecting communities in complex networks.     

Fuzzy analysis of community detection in complex networks

A snowball algorithm is proposed to find community structures in complex networks by introducing the definition of community core and some quantitative conditions. A community core is first constructed, and then its neighbors, satisfying the quantitative conditions, will be tied to this core until no node can be added. Subsequently, one by one, all communities in the network are obtained by repeating this process. The use of the local information in the proposed algorithm directly leads to the reduction of complexity. The algorithm runs in O(n+m) time for a general network and O(n) for a sparse network, where n is the number of vertices and m is the number of edges in a network. The algorithm fast produces the desired results when applied to search for communities in a benchmark and five classical real-world networks, which are widely used to test algorithms of community detection in the complex network. Furthermore, unlike existing methods, neither global modularity nor local modularity is utilized in the proposal. By converting the considered problem into a graph, the proposed algorithm can also be applied to solve other cluster problems in data mining.     

A smart local moving algorithm for large-scale modularity-based community detection

We introduce a new algorithm for modularity-based community detection in large networks. The algorithm, which we refer to as a smart local moving algorithm, takes advantage of a well-known local moving heuristic that is also used by other algorithms. Compared with these other algorithms, our proposed algorithm uses the local moving heuristic in a more sophisticated way. Based on an analysis of a diverse set of networks, we show that our smart local moving algorithm identifies community structures with higher modularity values than other algorithms for large-scale modularity optimization, among which the popular “Louvain algorithm”. The computational efficiency of our algorithm makes it possible to perform community detection in networks with tens of millions of nodes and hundreds of millions of edges. Our smart local moving algorithm also performs well in small and medium-sized networks. In short computing times, it identifies community structures with modularity values equally high as, or almost as high as, the highest values reported in the literature, and sometimes even higher than the highest values found in the literature.     

Community structure in directed networks

We consider the problem of finding communities or modules in directed networks. In the past, the most common approach to this problem has been to ignore edge direction and apply methods developed for community discovery in undirected networks, but this approach discards potentially useful information contained in the edge directions. Here we show how the widely used community finding technique of modularity maximization can be generalized in a principled fashion to incorporate information contained in edge directions. We describe an explicit algorithm based on spectral optimization of the modularity and show that it gives demonstrably better results than previous methods on a variety of test networks, both real and computer generated.     

Density-based shrinkage for revealing hierarchical and overlapping community structure in networks

The investigation of community structure in networks is an important issue in many disciplines, which still remains a challenging task. First, complex networks often show a hierarchical structure with communities embedded within other communities. Moreover, communities in the network may overlap and have noise, e.g., some nodes belonging to multiple communities and some nodes marginally connected with the communities, which are called hub and outlier, respectively. Therefore, a good algorithm is desirable to be able to not only detect hierarchical communities, but also to identify hubs and outliers. In this paper, we propose a parameter-free hierarchical network clustering algorithm DenShrink. By combining the advantages of density-based clustering and modularity optimization methods, our algorithm can reveal the embedded hierarchical community structure efficiently in large-scale weighted undirected networks, and identify hubs and outliers as well. Moreover, it overcomes the resolution limit possessed by other modularity-based methods. Our experiments on the real-world and synthetic datasets show that DenShrink generates more accurate results than the baseline methods.     

Community structure and modularity in networks of correlated brain activity

Functional connectivity patterns derived from neuroimaging data may be represented as graphs or networks, with individual image voxels or anatomically-defined structures representing the nodes, and a measure of correlation between the responses in each pair of nodes determining the edges. This explicit network representation allows network-analysis approaches to be applied to the characterization of functional connections within the brain. Much recent research in complex networks has focused on methods to identify community structure, i.e. cohesive clusters of strongly interconnected nodes. One class of such algorithms determines a partition of a network into 'sub-networks' based on the optimization of a modularity parameter, thus also providing a measure of the degree of segregation versus integration in the full network. Here, we demonstrate that a community structure algorithm based on the maximization of modularity, applied to a functional connectivity network calculated from the responses to acute fluoxetine challenge in the rat, can identify communities whose distributions correspond to anatomically meaningful structures and include compelling functional subdivisions in the brain. We also discuss the biological interpretation of the modularity parameter in terms of segregation and integration of brain function.     

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.     

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.     

考虑边聚类与扩散特性的信息传播网络结构优化算法

优化网络结构以促进信息在网络中传播一直是复杂网络研究的重点,网络中边的聚类特性和扩散特性对信息传播具有重要作用. K-truss分解算法是一种利用边的聚类特性识别网络关键节点的算法,然而K-truss算法会受到网络中局部聚类结果 (即相互连接的假核结构)的影响,而这些假核结构里的节点对信息扩散能力通常较弱.为此,本文提出一种衡量边扩散特性的指标,研究发现一些位于网络边缘的边具有很好的扩散性,但这类边的聚类很低,并不利于信息传播.通过同时考虑边的聚类特性和扩散特性之间的制约关系,提出一种信息传播网络结构优化算法.为了验证所提算法的有效性,使用该算法对四个真实的网络进行结构优化,并使用经典的独立级联模型来验证网络结构优化前后信息传播的有效范围.结果表明:使用提出的算法优化后的网络拓扑可以有效提高信息传播范围;并且,优化后的网络其叶子节点数目降低、聚类系数降低以及平均路径长度降低.     

Optimal synchronizability of networks

We numerically investigate how to enhance synchronizability of coupled identical oscillators in complex networks with research focus on the roles of the high level of clustering for a given heterogeneity in the degree distribution. By using the edge-exchange method with the fixed degree sequence, we first directly maximize synchronizability measured by the eigenratio of the coupling matrix, through the use of the so-called memory tabu search algorithm developed in applied mathematics. The resulting optimal network, which turns out to be weakly disassortative, is observed to exhibit a small modularity. More importantly, it is clearly revealed that the optimally synchronizable network for a given degree sequence shows a very low level of clustering, containing much fewer small-size loops than the original network. We then use the clustering coefficient as an object function to be reduced during the edge exchanges, and find it a very efficient way to enhance synchronizability. We thus conclude that under the condition of a given degree heterogeneity, the clustering plays a very important role in the network synchronization.     

Semi-supervised clustering algorithm for community structure detection in complex networks

Discovering a community structure is fundamental for uncovering the links between structure and function in complex networks. In this paper, we discuss an equivalence of the objective functions of the symmetric nonnegative matrix factorization (SNMF) and the maximum optimization of modularity density. Based on this equivalence, we develop a new algorithm, named the so-called SNMF-SS, by combining SNMF and a semi-supervised clustering approach. Previous NMF-based algorithms often suffer from the restriction of measuring network topology from only one perspective, but our algorithm uses a semi-supervised mechanism to get rid of the restriction. The algorithm is illustrated and compared with spectral clustering and NMF by using artificial examples and other classic real world networks. Experimental results show the significance of the proposed approach, particularly, in the cases when community structure is obscure.     

A local fuzzy method based on “p-strong” community for detecting communities in networks

In this paper,we propose a local fuzzy method based on the idea of "p-strong" community to detect the disjoint and overlapping communities in networks.In the method,a refined agglomeration rule is designed for agglomerating nodes into local communities,and the overlapping nodes are detected based on the idea of making each community strong.We propose a contribution coefficient b_v~(ci)to measure the contribution of an overlapping node to each of its belonging communities,and the fuzzy coefficients of the overlapping node can be obtained by normalizing the b_v~(ci) to all its belonging communities.The running time of our method is analyzed and varies linearly with network size.We investigate our method on the computergenerated networks and real networks.The testing results indicate that the accuracy of our method in detecting disjoint communities is higher than those of the existing local methods and our method is efficient for detecting the overlapping nodes with fuzzy coefficients.Furthermore,the local optimizing scheme used in our method allows us to partly solve the resolution problem of the global modularity.     

Community detection based on network communicability

We propose a new method for detecting communities based on the concept of communicability between nodes in a complex network. This method, designated as N-ComBa K-means, uses a normalized version of the adjacency matrix to build the communicability matrix and then applies K-means clustering to find the communities in a graph. We analyze how this method performs for some pathological cases found in the analysis of the detection limit of communities and propose some possible solutions on the basis of the analysis of the ratio of local to global densities in graphs. We use four different quality criteria for detecting the best clustering and compare the new approach with the Girvan-Newman algorithm for the analysis of two "classical" networks: karate club and bottlenose dolphins. Finally, we analyze the more challenging case of homogeneous networks with community structure, for which the Girvan-Newman completely fails in detecting any clustering. The N-ComBa K-means approach performs very well in these situations and we applied it to detect the community structure in an international trade network of miscellaneous manufactures of metal having these characteristics. Some final remarks about the general philosophy of community detection are also discussed.     

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.     

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.     

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

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