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.     

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.     

Community detection in social networks based on improved Label Propagation Algorithm and balanced link density

Nowadays, community detection has been raised as one of the key research areas in the online social networks mining. One of the most common algorithms in this field is label propagation algorithm (LPA). Even though the LPA method has advantages such as simplicity in understanding and implementation, as well as linear time complexity, it has an important disadvantage of the uncertainty and instability in outcomes, that is, the algorithm detects and reports different combinations of communities in each run. This problem originates from the nature of random selection in the LPA method. In this paper, a novel method is proposed based on the LPA method and the inherent structure, that is, link density feature, of the input network. The proposed method uses a sensitivity parameter (balance parameter); by choosing the appropriate values for it, the desired qualities of the identified communities can be achieved. The proposed method is called Balanced Link Density-based Label Propagation (BLDLP). In comparison with the basic LPA, the proposed method has an advantage of certainty and stability in the output results, whereas its time complexity is still comparable with the basic LPA and of course lowers than many other approaches. The proposed method has been evaluated on real-world known datasets, such as the Facebook social network and American football clubs, and by comparing it with the basic LPA, the effectiveness of the proposed method in terms of the quality of the communities found and the time complexity has been shown.     

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.     

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.     

Growing community networks with local events

The study of community networks has attracted considerable attention recently. In this paper, we propose an evolving community network model based on local processes, the addition of new nodes intra-community and new links intra- or inter-community. Employing growth and preferential attachment mechanisms, we generate networks with a generalized power-law distribution of nodes’ degrees.     

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.     

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.     

Ant colony clustering with fitness perception and pheromone diffusion for community detection in complex networks

Community structure detection in complex networks has been intensively investigated in recent years. In this paper, we propose an adaptive approach based on ant colony clustering to discover communities in a complex network. The focus of the method is the clustering process of an ant colony in a virtual grid, where each ant represents a node in the complex network. During the ant colony search, the method uses a new fitness function to percept local environment and employs a pheromone diffusion model as a global information feedback mechanism to realize information exchange among ants. A significant advantage of our method is that the locations in the grid environment and the connections of the complex network structure are simultaneously taken into account in ants moving. Experimental results on computer-generated and real-world networks show the capability of our method to successfully detect community structures.     

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.     

A fast and efficient heuristic algorithm for detecting community structures in complex networks

Community structure is an important property of complex networks. How to detect the communities is significant for understanding the network structure and to analyze the network properties. Many algorithms, such as K-L and GN, have been proposed to detect community structures in complex networks. According to daily experience, a community should have many nodes and connections. Based on these principles and existing researches, a fast and efficient algorithm for detecting community structures in complex networks is proposed in this paper. The key strategy of the algorithm is to mine a node with the closest relations with the community and assign it to this community. Four real-world networks are used to test the performance of the algorithm. Experimental results demonstrate that the algorithm proposed is rather efficient for detecting community structures in complex networks.     

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 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.     

Road traffic: A case study of flow and path-dependency in weighted directed networks

How much can we tell about flows through networks just from their topological properties? Whereas flow distributions of river basins, trees or cardiovascular systems come naturally to mind, more complex topologies are not so immediate, especially if the network is large and heterogeneously directed. Our study is motivated by the question of how the distribution of path-dependent trails in directed networks is correlated to the distribution of network flows. As an example we have studied the path-dependencies in closed trails in four metropolitan areas in England and the USA and computed their global and spatial correlations with measured traffic flows. We have found that the heterogeneous distribution of traffic intensity is mirrored by the distribution of agglomerate path-dependency and that high traffic roads are packed along corridors at short-to-medium trail lengths from the ensemble of nodes.     

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.     

Efficient algorithm based on neighborhood overlap for community identification in complex networks

Community structure is an important feature in many real-world networks. Many methods and algorithms for identifying communities have been proposed and have attracted great attention in recent years. In this paper, we present a new approach for discovering the community structure in networks. The novelty is that the algorithm uses the strength of the ties for sorting out nodes into communities. More specifically, we use the principle of weak ties hypothesis to determine to what community the node belongs. The advantages of this method are its simplicity, accuracy, and low computational cost. We demonstrate the effectiveness and efficiency of our algorithm both on real-world networks and on benchmark graphs. We also show that the distribution of link strength can give a general view of the basic structure information of graphs.     

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.     

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.     

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.