Detecting community structure in complex networks via node similarity

The detection of the community structure in networks is beneficial to understand the network structure and to analyze the network properties. Based on node similarity, a fast and efficient method for detecting community structure is proposed, which discovers the community structure by iteratively incorporating the community containing a node with the communities that contain the nodes with maximum similarity to this node to form a new community. The presented method has low computational complexity because of requiring only the local information of the network, and it does not need any prior knowledge about the communities and its detection results are robust on the selection of the initial node. Some real-world and computer-generated networks are used to evaluate the performance of the presented method. The simulation results demonstrate that this method is efficient to detect community structure in complex networks, and the ZLZ metrics used in the proposed method is the most suitable one among local indices in community detection.     

Detecting overlapping communities of weighted networks via a local algorithm

Identification of communities is significant in understanding the structures and functions of networks. Since some nodes naturally belong to several communities, the study of overlapping communities has attracted increasing attention recently, and many algorithms have been designed to detect overlapping communities. In this paper, an overlapping communities detecting algorithm is proposed whose main strategies are finding an initial partial community from a node with maximal node strength and adding tight nodes to expand the partial community. Seven real-world complex networks and one synthetic network are used to evaluate the algorithm. Experimental results demonstrate that the algorithm proposed is efficient for detecting overlapping communities in weighted networks.     

Detecting the community structure in complex networks based on quantum mechanics

In this paper, we develop a novel method to detect the community structure in complex networks. This approach is based on the combination of kernel-based clustering using quantum mechanics, the spectral clustering technique and the concept of the Bayesian information criterion. We test the proposed algorithm on Zachary’s karate club network and the world of American college football. Experimental results indicate that our algorithm is efficient and effective at finding both the optimal number of clusters, and the best clustering of community structures.     

Detecting overlapping communities in networks via dominant label propagation

Community detection is an important methodology for understanding the intrinsic structure and function of a realworld network.In this paper,we propose an effective and efficient algorithm,called Dominant Label Propagation Algorithm(Abbreviated as DLPA),to detect communities in complex networks.The algorithm simulates a special voting process to detect overlapping and non-overlapping community structure in complex networks simultaneously.Our algorithm is very efficient,since its computational complexity is almost linear to the number of edges in the network.Experimental results on both real-world and synthetic networks show that our algorithm also possesses high accuracies on detecting community structure in networks.     

Computing communities in complex networks using the Dirichlet processing Gaussian mixture model with spectral clustering

Community detection becomes a significant tool for the complex network analysis. The study of the community detection algorithms has received an enormous amount of attention. It is still an open question whether a highly accurate and efficient algorithm is found in most data sets. We propose the Dirichlet Processing Gaussian Mixture Model with Spectral Clustering algorithm for detecting the community structures. The combination of traditional spectral algorithm and new non-parametric Bayesian model provides high accuracy and quality. We compare the proposed algorithm with other existing community detecting algorithms using different real-world data sets and computer-generated synthetic data sets. We show that the proposed algorithm results in high modularity, and better accuracy in a wide range of networks. We find that the proposed algorithm works best for the large size of the data sets.     

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.     

Research on Community Structure in Bus Transport Networks

We abstract the bus transport networks (BTNs) to two kinds of complex networks with space L and space P methods respectively. Using improved community detecting algorithm (PKM agglomerative algorithm), we analyze the community property of two kinds of BTNs graphs. The results show that the BTNs graph described with space L method have obvious community property, but the other kind of BTNs graph described with space P method have not. The reason is that the BTNs graph described with space P method have the intense overlapping community property and general community division algorithms can not identify this kind of community structure. To overcome this problem, we propose a novel community structure called N-depth community and present a corresponding community detecting algorithm, which can detect overlapping community. Applying the novel community structure and detecting algorithm to a BTN evolution model described with space P, whose network property agrees well with real BTNs', we get obvious community property.     

Community detection in networks by using multiobjective evolutionary algorithm with decomposition

Community structure is an important property of complex networks. Most optimization-based community detection algorithms employ single optimization criteria. In this study, the community detection is solved as a multiobjective optimization problem by using the multiobjective evolutionary algorithm based on decomposition. The proposed algorithm maximizes the density of internal degrees, and minimizes the density of external degrees simultaneously. It can produce a set of solutions which can represent various divisions to the networks at different hierarchical levels. The number of communities is automatically determined by the non-dominated individuals resulting from our algorithm. Experiments on both synthetic and real-world network datasets verify that our algorithm is highly efficient at discovering quality community structure.     

Community detection in complex networks by density-based clustering

We proposed a method to find the community structure in a complex network by density-based clustering. Physical topological distance is introduced in density-based clustering for determining a distance function of specific influence functions. According to the distribution of the data, the community structures are uncovered. The method keeps a better connection mode of the community structure than the existing algorithms in terms of modularity, which can be viewed as a basic characteristic of community detection in the future. Moreover, experimental results indicate that the proposed method is efficient and effective to be used for community detection of medium and large 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.     

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.     

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.     

Overlapping community detection using a generative model for networks

Detecting overlapping communities is a challenging task in analyzing networks, where nodes may belong to more than one community. Many present methods optimize quality functions to extract the communities from a network. In this paper, we present a probabilistic method for detecting overlapping communities using a generative model. The model describes the probability of generating a network with the model parameters, which reflect the communities in the network. The community memberships of each node are determined based on a probabilistic approach using those model parameters, whose values can be obtained by fitting the model to the network. This method has the advantage that the node participation degrees in each community are also computed. The proposed method is compared with some other community detection methods on both synthetic networks and real-world networks. The experiments show that this method is efficient at detecting overlapping communities and can provide better performance on the networks where a majority of nodes belong to more than one community.     

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.     

Graph kernels,hierarchical clustering,and network community structure: experiments and comparative analysis

There has been a quickly growing interest in properties of complex networks, such as the small world property, power-law degree distribution, network transitivity, and community structure, which seem to be common to many real world networks. In this study, we consider the community property which is also found in many real networks. Based on the diffusion kernels of networks, a hierarchical clustering approach is proposed to uncover the community structure of different extent of complex networks. We test the method on some networks with known community structures and find that it can detect significant community structure in these networks. Comparison with related methods shows the effectiveness of the method.     

Detecting overlapping communities by seed community in weighted complex networks

Detection of community structures in the weighted complex networks is significant to understand the network structures and analysis of the network properties. We present a unique algorithm to detect overlapping communities in the weighted complex networks with considerable accuracy. For a given weighted network, all the seed communities are first extracted. Then to each seed community, more community members are absorbed using the absorbing degree function. In addition, our algorithm successfully finds common nodes between communities. The experiments using some real-world networks show that the performance of our algorithm is satisfactory.     

Detecting overlapping communities based on vital nodes in complex networks

Detection of community structures in the complex networks is significant to understand the network structures and analyze the network properties. However, it is still a problem on how to select initial seeds as well as to determine the number of communities. In this paper, we proposed the detecting overlapping communities based on vital nodes algorithm(DOCBVA), an algorithm based on vital nodes and initial seeds to detect overlapping communities. First, through some screening method, we find the vital nodes and then the seed communities through the pretreatment of vital nodes. This process differs from most existing methods, and the speed is faster. Then the seeds will be extended. We also adopt a new parameter of attribution degree to extend the seeds and find the overlapping communities. Finally, the remaining nodes that have not been processed in the first two steps will be reprocessed. The number of communities is likely to change until the end of algorithm. The experimental results using some real-world network data and artificial network data are satisfactory and can prove the superiority of the DOCBVA algorithm.     

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.     

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.     

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.