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.     

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

基于联合矩阵分解的节点多属性网络社团检测

发现复杂网络中的社团结构在社会网络、生物组织网络和在线网络等复杂网络中具备十分重要的意义. 针对社交媒体网络的社团检测通常需要利用两种信息源: 网络拓扑结构特征和节点属性特征, 丰富的节点内容属性信息为社团检测的增加了灵活性和挑战. 传统方法是要么仅针对这两者信息之一进行单独挖掘, 或者将两者信息得到的社团结果进行线性叠加判决, 不能有效进行信息源的融合. 本文将节点的多维属性特征作为社团划分的一种有效协同学习项进行研究, 将两者信息源进行融合分析, 提出了一种基于联合矩阵分解的节点多属性网络社团检测算法CDJMF, 提高了社团检测的有效性和鲁棒性. 实验表明, 本文所提的方法能够有效利用节点的属性信息指导社团检测, 具备更高的社团划分质量.     

Detecting community structure from coherent oscillation of excitable systems

Many networks are proved to have community structures. On the basis of the fact that the dynamics on networks are intensively affected by the related topology, in this paper the dynamics of excitable systems on networks and a corresponding approach for detecting communities are discussed. Dynamical networks are formed by interacting neurons; each neuron is described using the FHN model. For noisy disturbance and appropriate coupling strength, neurons may oscillate coherently and their behavior is tightly related to the community structure. Synchronization between nodes is measured in terms of a correlation coefficient based on long time series. The correlation coefficient matrix can be used to project network topology onto a vector space. Then by the K-means cluster method, the communities can be detected. Experiments demonstrate that our algorithm is effective at discovering community structure in artificial networks and real networks, especially for directed networks. The results also provide us with a deep understanding of the relationship of function and structure for dynamical 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.     

Detecting local community structures in complex networks based on local degree central nodes

Detecting local communities in real-world graphs such as large social networks, web graphs, and biological networks has received a great deal of attention because obtaining complete information from a large network is still difficult and unrealistic nowadays. In this paper, we define the term local degree central node whose degree is greater than or equal to the degree of its neighbor nodes. A new method based on the local degree central node to detect the local community is proposed. In our method, the local community is not discovered from the given starting node, but from the local degree central node that is associated with the given starting node. Experiments show that the local central nodes are key nodes of communities in complex networks and the local communities detected by our method have high accuracy. Our algorithm can discover local communities accurately for more nodes and is an effective method to explore community structures of large 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.     

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.     

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.     

Structure profile of complex networks by a model of precipitation

The organizational structure of a network is investigated with a simulated precipitation model which does not make use of prior knowledge about the community structure of the network. The result is presented as a structure profile through which various definitions of communities can be applied for specific applications. The simulated precipitation model performs the grouping of nodes so that nodes belonging to the same “community” automatically aggregate, thereby revealing regions of the adjacency matrix with denser interconnections. The process is analogous to massive particles precipitating towards the lower potential layer. Without loss of the infrastructure information, a community structure profile of a network can be obtained as the ground state of the Hamiltonian. The method is also applicable to directed and weighted networks.     

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.     

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.     

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

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

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

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

A brief study on coevolution of Ising dynamics

Community structure appears to be an intrinsic property of many complex real-world networks. However, recent work shows that real-world networks reveal even more sophisticated modules than classical cohesive (link-density) communities. In particular, networks can also be naturally partitioned according to similar patterns of connectedness among the nodes, revealing link-pattern communities. We here propose a propagation based algorithm that can extract both link-density and link-pattern communities, without any prior knowledge of the true structure. The algorithm was first validated on different classes of synthetic benchmark networks with community structure, and also on random networks. We have further applied the algorithm to different social, information, technological and biological networks, where it indeed reveals meaningful (composites of) link-density and link-pattern communities. The results thus seem to imply that, similarly as link-density counterparts, link-pattern communities appear ubiquitous in nature and design.     

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.     

Eigenvectors of network complement reveal community structure more accurately

We propose a general spectral method to find communities of a network based on network complement and anti-community concepts. Analytical and numerical results show that the eigenspace of matrices corresponding to a network complement reveals the community structure of a network more accurately than the eigenspace of matrices corresponding to the network itself. It is shown that the Laplacian eigenspace is the best candidate for spectral community detection especially in networks with a heterogeneous community structure. The method is applied to some computer-generated and real-world networks with known community structures.     

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.     

Community detection based on network communicability

We propose a new method for detecting communities based on the concept of communicability between nodes in a complex network. This method, designated as N-ComBa K-means, uses a normalized version of the adjacency matrix to build the communicability matrix and then applies K-means clustering to find the communities in a graph. We analyze how this method performs for some pathological cases found in the analysis of the detection limit of communities and propose some possible solutions on the basis of the analysis of the ratio of local to global densities in graphs. We use four different quality criteria for detecting the best clustering and compare the new approach with the Girvan-Newman algorithm for the analysis of two "classical" networks: karate club and bottlenose dolphins. Finally, we analyze the more challenging case of homogeneous networks with community structure, for which the Girvan-Newman completely fails in detecting any clustering. The N-ComBa K-means approach performs very well in these situations and we applied it to detect the community structure in an international trade network of miscellaneous manufactures of metal having these characteristics. Some final remarks about the general philosophy of community detection are also discussed.