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.     

Robust network community detection using balanced propagation

Label propagation has proven to be an extremely fast method for detecting communities in large complex networks. Furthermore, due to its simplicity, it is also currently one of the most commonly adopted algorithms in the literature. Despite various subsequent advances, an important issue of the algorithm has not yet been properly addressed. Random (node) update orders within the algorithm severely hamper its robustness, and consequently also the stability of the identified community structure. We note that an update order can be seen as increasing propagation preferences from certain nodes, and propose a balanced propagation that counteracts for the introduced randomness by utilizing node balancers. We have evaluated the proposed approach on synthetic networks with planted partition, and on several real-world networks with community structure. The results confirm that balanced propagation is significantly more robust than label propagation, when the performance of community detection is even improved. Thus, balanced propagation retains high scalability and algorithmic simplicity of label propagation, but improves on its stability and performance.     

Community detection with consideration of non-topological information

In a network described by a graph, only topological structure information is considered to determine how the nodes are connected by edges. Non-topological information denotes that which cannot be determined directly from topological information. This paper shows, by a simple example where scientists in three research groups and one external group form four communities, that in some real world networks non-topological information (in this example, the research group affiliation) dominates community division. If the information has some influence on the network topological structure, the question arises as to how to find a suitable algorithm to identify the communities based only on the network topology. We show that weighted Newman algorithm may be the best choice for this example. We believe that this idea is general for real-world complex networks.     

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.     

A class of improved algorithms for detecting communities in complex networks

Detecting communities in complex networks is of considerable importance for understanding both the structure and function of the networks. Here, we propose a class of improved algorithms for community detection, by combining the betweenness algorithm of Girvan and Newman with the edge weight defined by the edge-clustering coefficient. The improved algorithms are tested on some artificial and real-world networks, and the results show that they can detect communities of networks more effectively in both unweighted and weighted cases. In addition, the technique for improving the betweenness algorithm in this paper, thanks to its compatibility, can directly be applied to various detection algorithms.     

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.     

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.     

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.     

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.     

Adjusting from disjoint to overlapping community detection of complex networks

The investigation of community structures is one of the most important problems in the field of complex networks and has countless applications in different disciplines: biology, computer, social sciences, etc. Many community detection algorithms have been developed in various fields recently. The vast majority of these algorithms only find disjoint communities; however, in many real-world networks communities often overlap to some extent. In this paper, we propose an efficient method for adjusting these classical algorithms to match the requirement for discovering overlapping communities in complex networks, which is based on a local definition of community strength. The method can in principle be applied with any clustering algorithm. Tests on a set of computer generated and real-world networks give excellent results. In particular, we show that the method can also allow one to availably analyze the problem of unstable nodes in community detection, which is very helpful for understanding the structural properties of the networks correctly and comprehensively.     

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.     

Ordered community structure in networks

Community structure in networks is often a consequence of homophily, or assortative mixing, based on some attribute of the vertices. For example, researchers may be grouped into communities corresponding to their research topic. This is possible if vertex attributes have unordered discrete values, but many networks exhibit assortative mixing by some ordered (discrete or continuous) attribute, such as age or geographical location. In such cases, the identification of discrete communities may be difficult or impossible. We consider how the notion of community structure can be generalized to networks that have assortative mixing by ordered attributes. We propose a method of generating synthetic networks with ordered communities and investigate the effect of ordered community structure on the spread of infectious diseases. We also show that current community detection algorithms fail to recover community structure in ordered networks, and evaluate an alternative method using a layout algorithm to recover the ordering.     

Detecting communities by the core-vertex and intimate degree in complex networks

In this paper, we present a new approach to extract communities in the complex networks with considerable accuracy. We introduce the core-vertex and the intimate degree between the community and its neighboring vertices. First, we find the core-vertices as the initial community. These core-vertices are then expanded using intimate degree function during extracting community structure from the given network. In addition, our algorithm successfully finds common nodes between communities. Experimental results using some real-world networks data shows that the performance of our algorithm is satisfactory.     

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.     

A validity index approach for network partitions

The validity index has been used to evaluate the fitness of partitions produced by clustering algorithms for points in Euclidean space. In this paper, we propose a new validity index for network partitions, which can provide a measure of goodness for the community structure of networks. It is defined as a product of two factors, and involves the compactness and separation for each partition. The simulated annealing strategy is used to minimize such a validity index function in coordination with our previous k-means algorithm based on the optimal reduction of a random walker Markovian dynamics on the network. It is demonstrated that the algorithm can efficiently find the community structure during the cooling process. The number of communities can be automatically determined without any prior knowledge of the community structure. Moreover, the algorithm is successfully applied to three real-world networks.     

Clustering coefficient and community structure of bipartite networks

Many real-world networks display natural bipartite structure, where the basic cycle is a square. In this paper, with the similar consideration of standard clustering coefficient in binary networks, a definition of the clustering coefficient for bipartite networks based on the fraction of squares is proposed. In order to detect community structures in bipartite networks, two different edge clustering coefficients LC₄ and LC₃ of bipartite networks are defined, which are based on squares and triples respectively. With the algorithm of cutting the edge with the least clustering coefficient, communities in artificial and real world networks are identified. The results reveal that investigating bipartite networks based on the original structure can show the detailed properties that is helpful to get deep understanding about the networks.     

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.     

A thermal flux-diffusing model for complex networks and its applications in community structure detection

We introduce a thermal flux-diffusing model for complex networks. Based on this model, we propose a physical method to detect the communities in the complex networks. The method allows us to obtain the temperature distribution of nodes in time that scales linearly with the network size. Then, the local community enclosing a given node can be easily detected for the reason that the dense connections in the local communities lead to the temperatures of nodes in the same community being close to each other. The community structure of a network can be recursively detected by randomly choosing the nodes outside the detected local communities. In the experiments, we apply our method to a set of benchmarking networks with known pre-determined community structures. The experiment results show that our method has higher accuracy and precision than most existing globe methods and is better than the other existing local methods in the selection of the initial node. Finally, several real-world networks are investigated.     

Overlapping Community Detection Based on Attribute Augmented Graph

There is a wealth of information in real-world social networks. In addition to the topology information, the vertices or edges of a social network often have attributes, with many of the overlapping vertices belonging to several communities simultaneously. It is challenging to fully utilize the additional attribute information to detect overlapping communities. In this paper, we first propose an overlapping community detection algorithm based on an augmented attribute graph. An improved weight adjustment strategy for attributes is embedded in the algorithm to help detect overlapping communities more accurately. Second, we enhance the algorithm to automatically determine the number of communities by a node-density-based fuzzy k-medoids process. Extensive experiments on both synthetic and real-world datasets demonstrate that the proposed algorithms can effectively detect overlapping communities with fewer parameters compared to the baseline methods.     

Overlapping community detection using weighted consensus clustering

Many overlapping community detection algorithms have been proposed. Most of them are unstable and behave non-deterministically. In this paper, we use weighted consensus clustering for combining multiple base covers obtained by classic non-deterministic algorithms to improve the quality of the results. We first evaluate a reliability measure for each community in all base covers and assign a proportional weight to each one. Then we redefine the consensus matrix that takes into account not only the common membership of nodes, but also the reliability of the communities. Experimental results on both artificial and real-world networks show that our algorithm can find overlapping communities accurately.