Clique-Based Locally Consistent Latent Space Clustering for Community Detection
Community structure is one of the most important properties of complex networks and a keypoint to understanding and exploring real-world networks. One popular technique for community detection is matrix-based algorithms. However, existing matrix-based com
- PDF / 1,977,618 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 66 Downloads / 211 Views
School of Computer Science and Technology, Anhui University, Hefei 230601, People’s Republic of China {dingzhuanlian,sundengdi,luobinahu}@163.com, [email protected] 2 Key Lab of Industrial Image Processing & Analysis of Anhui Province, Hefei 230039, People’s Republic of China
Abstract. Community structure is one of the most important properties of complex networks and a keypoint to understanding and exploring real-world networks. One popular technique for community detection is matrix-based algorithms. However, existing matrix-based community detection models, such as nonnegative matrix factorization, spectral clustering and their variants, fit the data in a Euclidean space and have ignored the local consistency information which is crucial when discovering communities. In this paper, we propose a novel framework of latent space clustering to cope with community detection, by incorporating the clique-based locally consistency into the original objective functions to penalize the latent space dissimilarity of the nodes within the clique. We evaluate the proposed methods on both synthetic and real-world networks and experimental results show that our approaches significantly improve the accuracy of community detection and outperform state-ofthe-art methods, especially on networks with unclear structures. Keywords: Community detection · Local consistency · Graph regularization · Nonnegative Matrix Factorization (NMF) · Spectral Clustering (SC)
1
Introduction
Community structure is a natural characteristic in many real networks, such as social networks, biological networks and technological networks [1–3]. Although no general and widely-accepted definition of community structure has been agreed upon, it is commonly believed that a community is a group of nodes with more internal than external connections [4]. For example, authors from the same institution in collaboration networks, proteins with the same functionality in biochemical networks and the collections of pages on a single topic on the Web. It’s worth noting that community structure in complex networks is often critical in understanding the natural structure of networks and revealing the network functions [5–7]. Thus, how to detect and extract these community c Springer Nature Singapore Pte Ltd. 2016 T. Tan et al. (Eds.): CCPR 2016, Part I, CCIS 662, pp. 675–689, 2016. DOI: 10.1007/978-981-10-3002-4 55
676
Z. Ding et al.
structures becomes an significant and challenging problem in the study of network systems. The identification of community structure has recently received enormous amounts of attention in various scientific fields and many methods have been proposed and applied successfully to some specific complex networks. These methods are from different perspectives, such as the hierarchical clustering [4], label propagation [8] and optimization based algorithms [9]. Besides these methods, matrix-based community detection algorithms [3,10–12] have gained great success at uncovering the community structure, such as nonnegative matrix factorization (NMF
Data Loading...
