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 based on modularity and an improved genetic algorithm

Complex networks are widely applied in every aspect of human society, and community detection is a research hotspot in complex networks. Many algorithms use modularity as the objective function, which can simplify the algorithm. In this paper, a community detection method based on modularity and an improved genetic algorithm (MIGA) is put forward. MIGA takes the modularity Q$Q$ as the objective function, which can simplify the algorithm, and uses prior information (the number of community structures), which makes the algorithm more targeted and improves the stability and accuracy of community detection. Meanwhile, MIGA takes the simulated annealing method as the local search method, which can improve the ability of local search by adjusting the parameters. Compared with the state-of-art algorithms, simulation results on computer-generated and four real-world networks reflect the effectiveness of MIGA.     

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.     

Growth curve based label propagation algorithm for community detection

How to better and faster identify the community structure is a hot issue in complex networks. During the past decades, various attempts have been made to solve this issue. Amongst them, without doubt, label propagation algorithm (LPA) is one of the most satisfying answers, especially for large-scale networks. However, it has one major flaw that when the community structure is not clear enough, a monster community tends to form. To address this issue, we set a growth curve for communities, gradually increasing from a low capacity to a higher capacity over time. Further, we improve the mechanism of label choosing for small communities to escape from local maximum. The experimental results on both synthetic and real networks demonstrate that our algorithm not only enhances the detection ability of the traditional label propagation algorithm, but also improves the quality of the identified communities.     

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.     

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.     

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.     

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

Clustering and community detection in directed networks: A survey

Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology, neuroscience and computer science. In most of the aforementioned cases graphs are directed — in the sense that there is directionality on the edges, making the semantics of the edges nonsymmetric as the source node transmits some property to the target one but not vice versa. An interesting feature that real networks present is the clustering or community structure property, under which the graph topology is organized into modules commonly called communities or clusters. The essence here is that nodes of the same community are highly similar while on the contrary, nodes across communities present low similarity. Revealing the underlying community structure of directed complex networks has become a crucial and interdisciplinary topic with a plethora of relevant application domains. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs — with clustering being the primary method sought and the primary tool for community detection and evaluation. The goal of this paper is to offer an in-depth comparative review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications. The survey commences by offering a concise review of the fundamental concepts and methodological base on which graph clustering algorithms capitalize on. Then we present the relevant work along two orthogonal classifications. The first one is mostly concerned with the methodological principles of the clustering algorithms, while the second one approaches the methods from the viewpoint regarding the properties of a good cluster in a directed network. Further, we present methods and metrics for evaluating graph clustering results, demonstrate interesting application domains and provide promising future research directions.     

Phase transition model for community detection

Motivated by social and biological interactions, a novel type of phase transition model is provided in order to investigate the emergence of the clustering phenomenon in networks. The model has two types of interactions: one is attractive and the other is repulsive. In each iteration, the phase of a node (or an agent) moves toward the average phase of its neighbors and moves away from the average phase of its non-neighbors. The velocities of the two types of phase transition are controlled by two parameters, respectively. It is found that the phase transition phenomenon is closely related to the topological structure of the underlying network, and thus can be applied to identify its communities and overlapping groups. By giving each node of the network a randomly generated initial phase and updating these phases by the phase transition model until they reach stability, one or two communities will be detected according to the nodes’ stable phases, confusable nodes are moved into a set named _Of$O_f$. By removing the detected communities and the nodes in _Of$O_f$, another one or two communities will be detected by an iteration of the algorithm, …. In this way, all communities and the overlapping nodes are detected. Simulations on both real-world networks and the LFR benchmark graphs have verified the efficiency of the proposed scheme.     

Response of scale-free networks with community structure to external stimuli

The response of scale-free networks with community structure to external stimuli is studied. By disturbing some nodes with different strategies, it is shown that the robustness of this kind of network can be enhanced due to the existence of communities in the networks. Some of the response patterns are found to coincide with topological communities. We show that such phenomena also occur in the cat brain network which is an example of a scale-free like network with community structure. Our results provide insights into the relationship between network topology and the functional organization in complex networks from another viewpoint.     

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 structure and ethnic preferences in school friendship networks

Recently developed concepts and techniques of analyzing complex systems provide new insight into the structure of social networks. Uncovering recurrent preferences and organizational principles in such networks is a key issue to characterize them. We investigate school friendship networks from the Add Health database. Applying threshold analysis, we find that the friendship networks do not form a single connected component through mutual strong nominations within a school, while under weaker conditions such interconnectedness is present. We extract the networks of overlapping communities at the schools (c-networks) and find that they are scale free and disassortative in contrast to the direct friendship networks, which have an exponential degree distribution and are assortative. Based on the network analysis we study the ethnic preferences in friendship selection. The clique percolation method we use reveals that when in minority, the students tend to build more densely interconnected groups of friends. We also find an asymmetry in the behavior of black minorities in a white majority as compared to that of white minorities in a black majority.     

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.     

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.     

Traffic dynamics in scale-free networks with tunable strength of community structure

In this paper we systematically investigate the impact of community structure on traffic dynamics in scale-free networks based on local routing strategy. A growth model is introduced to construct scale-free networks with tunable strength of community structure, and a packet routing strategy with a parameter α is used to deal with the navigation and transportation of packets simultaneously. Simulations show that the maximal network capacity stands at α=−1 in the case of identical vertex capacity and monotonously decreases with the strength of community structure which suggests that the networks with fuzzy community structure (i.e., community strength is weak) are more efficient in delivering packets than those with pronounced community structure. To explain these results, the distribution of packets of each vertex is carefully studied. Our results indicate that the moderate strength of community structure is more convenient for the information transfer of real complex systems.     

多信息融合的模糊边缘检测技术

提出了一种有效的模糊边缘检测算法，与传统的单纯基于图像增强技术的模糊边缘检测算法不同，此算法采用像素点的多种信息作为边缘检测的特征信息，利用模糊逻辑对这些信息进行综合，使边缘检测器输出的边缘信息更加完善且有效.实验表明，对于处理实际工作环境中的高噪图像的边缘检测问题，此算法是一种实用而有效的方法. 关键词： 边缘检测 模糊算法 融合     

Modelling of weighted evolving networks with community structures

Many social and biological networks consist of communities–groups of nodes within which links are dense but among which links are sparse. It turns out that most of these networks are best described by weighted networks, whose properties and dynamics depend not only on their structures but also on the link weights among their nodes. Recently, there are considerable interests in the study of properties as well as modelling of such networks with community structures. To our knowledge, however, no study of any weighted network model with such a community structure has been presented in the literature to date. In this paper, we propose a weighted evolving network model with a community structure. The new network model is based on the inner-community and inter-community preferential attachments and preferential strengthening mechanism. Simulation results indicate that this network model indeed reflect the intrinsic community structure, with various power-law distributions of the node degrees, link weights, and node strengths.     

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.