作者：
Ji, QingbinLi, DeyuJin, ZhenShanxi Univ
Sch Comp & Informat Technol Taiyuan 030006 Peoples R China Shanxi Univ
Minist Educ Key Lab Computat Intelligence & Chinese Informat Taiyuan 030006 Peoples R China Shanxi Univ
Complex Syst Res Ctr Taiyuan 030006 Peoples R China Shanxi Univ
Shanxi Key Lab Math Techn & Big Data Anal Dis Con Taiyuan 030006 Peoples R China
This paper studies the relationship between the clustering coefficient of nodes and the community structure of the network. Communities in a network are regarded as node-induced subgraphs of the network in this study....
详细信息
This paper studies the relationship between the clustering coefficient of nodes and the community structure of the network. Communities in a network are regarded as node-induced subgraphs of the network in this study. We define the border of a subgraph and the node network density of a node and present a formal definition of community from the view of examining the subgraph borders. Afterward, we analyze the relationship between the change in node clustering coefficients and in node network density and set the rule for identifying intercommunity edges. Finally, we propose a novel divisive algorithm for community detection by iteratively removing intercommunity edges. The time complexity of our algorithm is O(Nd-2), which increases linearly with the network size. Experiments on both synthetic and real-world networks show that introducing node clustering coefficients into the divisive algorithm can greatly improve the time efficiency of the algorithm while guaranteeing the accuracy of community detection.
Hierarchical analysis for network structure can point out which communities can constitute a larger group or give reasonable smaller groups within a community. Numerous methods for discovering community in networks di...
详细信息
Hierarchical analysis for network structure can point out which communities can constitute a larger group or give reasonable smaller groups within a community. Numerous methods for discovering community in networks divide networks at only one certain granularity, which does not benefit hierarchical analysis for network structure. Hierarchical clustering algorithms are the common technique that reveals the multilevel structure in the network analysis. In this work, we give a definition for scores of edges according to the basic idea of means clustering. Based on the definition, a neighbors-based divisive algorithm named neighbor-means (NM) is proposed to detect communities in networks, especially for hierarchical analysis. The divisive algorithm repeatedly removes the edge with the highest score to obtain hierarchical partitions but can recalculate the scores of edges quickly with local recalculating strategy and crucial change-rules, which makes its complexity much lower than many divisive algorithms. In addition, when the community structure is ambiguous, benefited from superiority of the defined scores, our method achieves better results than many divisive and agglomerative algorithms. Experiments with artificial and real-world networks demonstrate the superiority of neighbor-means in detecting community structure.
divisive algorithms are of great importance for community detection in complex networks. One algorithm proposed by Girvan and Newman (GN) based on an edge centrality named betweenness, is a typical representative of t...
详细信息
divisive algorithms are of great importance for community detection in complex networks. One algorithm proposed by Girvan and Newman (GN) based on an edge centrality named betweenness, is a typical representative of this field. Here we studied three edge centralities based on network topology, walks and paths respectively to quantify the relevance of each edge in a network, and proposed a divisive algorithm based on the rationale of GN algorithm for finding communities that removes edges iteratively according to the edge centrality values in a certain order. In addition, we gave a comparison analysis of these measures with the edge betweenness and information centrality. We found the principal difference among these measures in the partition procedure is that the edge centrality based on walks first removes the edge connected with a leaf vertex, but the others first delete the edge as a bridge between communities. It indicates that the edge centrality based on walks is harder to uncover communities than other edge centralities. We also tested these measures for community detection. The results showed that the edge information centrality outperforms other measures, the edge centrality based on walks obtains the worst results, and the edge betweenness gains better performance than the edge centrality based on network topology. We also discussed our method's efficiency and found that the edge centrality based on walks has a high time complexity and is not suitable for large networks. Crown Copyright (c) 2012 Published by Elsevier B.V. All rights reserved.
This paper, arising from population studies, develops clustering algorithms for identifying patterns in data. Based on the concept of geometric variability, we have developed one polythetic-divisive and three agglomer...
详细信息
This paper, arising from population studies, develops clustering algorithms for identifying patterns in data. Based on the concept of geometric variability, we have developed one polythetic-divisive and three agglomerative algorithms. The effectiveness of these procedures is shown by relating them to classical clustering algorithms. They are very general since they do not impose constraints on the type of data, so they are applicable to general (economics, ecological, genetics...) studies. Our major contributions include a rigorous formulation for novel clustering algorithms, and the discovery of new relationship between geometric variability and clustering. Finally, these novel procedures give a theoretical frame with an intuitive interpretation to some classical clustering methods to be applied with any type of data, including mixed data. These approaches are illustrated with real data on Drosophila chromosomal inversions.
We show that good community structures can be obtained by partitioning a social network in a succession of divisive sparsest cuts. A network flow algorithm based on fundamental principles of graph theory is introduced...
详细信息
We show that good community structures can be obtained by partitioning a social network in a succession of divisive sparsest cuts. A network flow algorithm based on fundamental principles of graph theory is introduced to identify the sparsest cuts and an underlying hierarchical community structure of the network via maximum concurrent flow. Matula [Matula, David W., 1985. Concurrent flow and concurrent connectivity in graphs. In: Alavi, Y., et al. (Eds.), Graph Theory and its Applications to algorithms and Computer Science. Wiley, New York, NY, pp. 543-559.] established the maximum concurrent flow problem (MCFP), and papers, on divisive vs. agglomerative average-linkage hierarchical clustering [e.g., Matula, David W., 1983. Cluster validity by concurrent chaining. In: Felsenstein, J. (Ed.), Numerical Taxonomy: Proc. of the NATO Adv. Study Inst., vol. 1. Springer-Verlag, New York, pp. 156-166 (Proceedings of NATO ASI Series G);Matula, David W., 1986. divisive vs. agglomerative average linkage hierarchical clustering. In: Gaul, W., and Schader, M. (Eds.), Classification as a Tool of Research. Elsevier, North-Holland, Amsterdam, pp. 289-301;Thompson, Byron J., 1985. A flow rerouting algorithm for the maximum concurrent flow problem with variable capacities and demands, and its application to cluster analysis. MasterThesis. School of Engineering and Applied Science, Southern Methodist University] provide the basis for partitioning a social network by way of sparsest cuts and/or maximum concurrent flow. The MCFP extends the [Ford Jr., Lester R., Fulkerson, Delbert R., 1956. Maximal flow through a network. Canadian journal of Mathematics 8, 399-404;Ford Jr., Lester R., Fulkerson, Delbert R., 1962. Flows in Networks. Princeton University Press, Princeton, NJ] source-sink max-flow problem to all-pairs maximum concurrent flow. The density of an (S, T)-cut is vertical bar(S, T)\(vertical bar S vertical bar center dot vertical bar T vertical bar) where vertical bar(S, T)vertic
The discovery of community structure in a large number of complex networks has attracted lots of interest in recent *** category of algorithms for detecting community structure,the divisive algorithms,has been propose...
详细信息
The discovery of community structure in a large number of complex networks has attracted lots of interest in recent *** category of algorithms for detecting community structure,the divisive algorithms,has been proposed and improved *** this paper,we propose an improved divisive algorithm,the basic idea of which is to take more than one parameters into consideration to describe the networks from different points of *** its basic idea appears to be a little simple,it is shown experimentally that it outperforms some other algorithms when it is applied to the networks with a relatively obscure community *** also demonstrate its effectiveness by applying it to IPv6 backbone *** communities detected by our algorithm indicate that although underdeveloped compared with IPv4 network,IPv6 network has already exhibited a preliminary community ***,our algorithm can be further extended and adapted in the *** fact,it suggests a simple yet possibly efficient way to improve algorithms.
A new divisive algorithm for multidimensional data clustering is suggested. Based on the minimization of the sum-of-squared-errors, the proposed method produces much smaller quantization errors than the median-cut and...
详细信息
A new divisive algorithm for multidimensional data clustering is suggested. Based on the minimization of the sum-of-squared-errors, the proposed method produces much smaller quantization errors than the median-cut and mean-split algorithms. It is also observed that the solutions obtained from our algorithm are close to the local optimal ones derived by the k-means iterative procedure.
暂无评论