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.     

A weight’s agglomerative method for detecting communities in weighted networks based on weight’s similarity

This paper proposes the new definition of the community structure of the weighted networks that groups of nodes in which the edge's weights distribute uniformly but at random between them. It can describe the steady connections between nodes or some similarity between nodes' functions effectively. In order to detect the community structure efficiently, a threshold coefficient κ to evaluate the equivalence of edges' weights and a new weighted modularity based on the weight's similarity are proposed. Then, constructing the weighted matrix and using the agglomerative mechanism, it presents a weight's agglomerative method based on optimizing the modularity to detect communities. For a network with n nodes, the algorithm can detect the community structure in time O(n²log₂ⁿ). Simulations on networks show that the algorithm has higher accuracy and precision than the existing techniques. Furthermore, with the change of κ the algorithm discovers a special hierarchical organization which can describe the various steady connections between nodes in groups.     

Refinement of the community detection performance by weighted relationship coupling

The complexity of many community detection algorithms is usually an exponential function with the scale which hard to uncover community structure with high speed. Inspired by the ideas of the famous modularity optimization, in this paper, we proposed a proper weighting scheme utilizing a novel k-strength relationship which naturally represents the coupling distance between two nodes. Community structure detection using a generalized weighted modularity measure is refined based on the weighted k-strength matrix. We apply our algorithm on both the famous benchmark network and the real networks. Theoretical analysis and experiments show that the weighted algorithm can uncover communities fast and accurately and can be easily extended to large-scale real networks.     

加权网络权重自相似评判函数及其社团结构检测

提出了权重自相似性加权网络社团结构评判函数,并基于该函数提出一种谱分析算法检测社团结构,结果表明算法能将加权网络划分为同一社团内边权值分布均匀,而社团间边权值分布随机的社团结构.通过建立具有社团结构的加权随机网络分析了该算法的准确性,与WEO和WGN算法相比,在评判权重自相似的阈值系数取较小时,该算法具有较高的准确性.对于一个具有n个节点和c个社团的加权网络,社团结构检测的复杂度为O(cn2/2).通过设置评判权重自相似的阈值系数,可检测出能反映节点联系稳定性的层化性社团结构.这与传统意义上只将加权网络划分为社团中边权值较大而社团间边权值较小的标准不同,从另一个角度更好地提取了加权网络的结构信息.     

Epidemic outbreaks in growing scale-free networks with local structure

The class of generative models has already attracted considerable interest from researchers in recent years and much expanded the original ideas described in BA model. Most of these models assume that only one node per time step joins the network. In this paper, we grow the network by adding n interconnected nodes as a local structure into the network at each time step with each new node emanating m new edges linking the node to the preexisting network by preferential attachment. This successfully generates key features observed in social networks. These include power-law degree distribution p_k∼k^−(3+μ), where μ=(n−1)/m is a tuning parameter defined as the modularity strength of the network, nontrivial clustering, assortative mixing, and modular structure. Moreover, all these features are dependent in a similar way on the parameter μ. We then study the susceptible-infected epidemics on this network with identical infectivity, and find that the initial epidemic behavior is governed by both of the infection scheme and the network structure, especially the modularity strength. The modularity of the network makes the spreading velocity much lower than that of the BA model. On the other hand, increasing the modularity strength will accelerate the propagation velocity.     

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.     

Detection of community structure in networks based on community coefficients

Determining community structure in networks is fundamental to the analysis of the structural and functional properties of those networks, including social networks, computer networks, and biological networks. Modularity function Q$Q$, which was proposed by Newman and Girvan, was once the most widely used criterion for evaluating the partition of a network into communities. However, modularity Q$Q$ is subject to a serious resolution limit. In this paper, we propose a new function for evaluating the partition of a network into communities. This is called community coefficient C$C$. Using community coefficient C$C$, we can automatically identify the ideal number of communities in the network, without any prior knowledge. We demonstrate that community coefficient C$C$ is superior to the modularity Q$Q$ and does not have a resolution limit. We also compared the two widely used community structure partitioning methods, the hierarchical partitioning algorithm and the normalized cuts (Ncut) spectral partitioning algorithm. We tested these methods on computer-generated networks and real-world networks whose community structures were already known. The Ncut algorithm and community coefficient C$C$ were found to produce better results than hierarchical algorithms. Unlike several other community detection methods, the proposed method effectively partitioned the networks into different community structures and indicated the correct number of communities.     

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.     

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.     

Detecting communities in clustered networks based on group action on set

In this paper, we propose a well targeted algorithm (GAS algorithm) for detecting communities in high clustered networks by presenting group action technology on community division. During the processing of this algorithm, the underlying community structure of a clustered network emerges simultaneously as the corresponding partition of orbits by the permutation groups acting on the node set are achieved. As the derivation of the orbit partition, an algebraic structure r-cycle can be considered as the origin of the community. To be a priori estimation for the community structure of the algorithm, the community separability is introduced to indicate whether a network has distinct community structure. By executing the algorithm on several typical networks and the LFR benchmark, it shows that this GAS algorithm can detect communities accurately and effectively in high clustered networks. Furthermore, we compare the GAS algorithm and the clique percolation algorithm on the LFR benchmark. It is shown that the GAS algorithm is more accurate at detecting non-overlapping communities in clustered networks. It is suggested that algebraic techniques can uncover fresh light on detecting communities in complex networks.     

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

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

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.     

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.     

Detecting the optimal number of communities in complex networks

To obtain the optimal number of communities is an important problem in detecting community structures. In this paper, we use the extended measurement of community detecting algorithms to find the optimal community number. Based on the normalized mutual information index, which has been used as a measure for similarity of communities, a statistic Ω(c) is proposed to detect the optimal number of communities. In general, when Ω(c) reaches its local maximum, especially the first one, the corresponding number of communities c is likely to be optimal in community detection. Moreover, the statistic Ω(c) can also measure the significance of community structures in complex networks, which has been paid more attention recently. Numerical and empirical results show that the index Ω(c) is effective in both artificial and real world networks.     

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.     

The effect of weight on community structure of networks

The effect of weight on community structures is investigated in this paper. We use weighted modularity Q^w$Q^w$ to evaluate the partitions and weighted extremal optimization algorithm to detect communities. Starting from empirical and idealized weighted networks, the matching between weights and edges are disturbed. Then using similarity function S to measure the difference between community structures, it is found that the redistribution of weights does strongly affect the community structure especially in dense networks. This indicates that the community structure in networks is a suitable property to reflect the role of weight.     

S-matrix regularities of two-dimensional σ-models of stiefel manifolds

The S-matrices of the two-dimensional nonlinear O(n+m)/O(n) and O(n+m)/O(n) XO(m) σ-models corresponding to Stiefel and Grassmann manifolds, respectively, are compared in leading order in $\text{1}\text{n}$. It is shown, that after averaging over O(m) labels of the incoming and outgoing particles, the S-matrices of both models become identical. This result explains why commonly expected regularities of the Grassmann models, in particular absence of particle production, are found, modulo an O(m) average, also in Stiefel models.     

Quantum inspired evolutionary algorithm for community detection in complex networks

Community structure is indispensable to discover the potential property of complex network systems. In this paper we propose two algorithms (QIEA-net and iQIEA-net) to discover communities in social networks by optimizing modularity. Unlike many existing methods, the proposed algorithms adopt quantum inspired evolutionary algorithm (QIEA) to optimize a population of solutions and do not need to give the number of community beforehand, which is determined by optimizing the value of modularity function and needs no human intervention. In order to accelerate the convergence speed, in iQIEA-net, we apply the result of classical partitioning algorithm as a guiding quantum individual, which can instruct other quantum individuals' evolution. We demonstrate the potential of two algorithms on five real social networks. The results of comparison with other community detection algorithms prove our approaches have very competitive performance.     

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.     

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.