Abstract
Spectral clustering has exhibited a superior performance in analyzing the cluster structure of network. However, the exponentially computational complexity limits its application in analyzing large-scale social networks. To tackle this problem, many low-rank matrix approximating algorithms are proposed, of which the NystrÖm method is an approach with proved lower approximate errors. Currently, most existing sampling techniques for NystrÖm method are designed on affinity matrices, which are time-consuming to compute by some similarity metrics. Moreover, the social networks are often built on link relations, in which there is no information to construct an affinity matrix for the approximate computing of NystrÖm method for spectral clustering except for the degrees of nodes. This paper proposes a spectral clustering algorithm for large-scale social networks via a pre-coarsening sampling based NystrÖm method. By virtue of a novel triangle-based coarsening policy, the proposed algorithm first shrinks the social network into a smaller weighted network, and then does an efficient sampling for NystrÖm method to approximate the eigen-decomposition of matrix of spectral clustering. Experimental results on real large-scale social networks demonstrate that the proposed algorithm outperforms the state-of-the-art spectral clustering algorithms, which are realized by the existing sampling techniques based NystrÖm methods.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ng, A.Y., Jordan, M.I., Weiss, Y.: On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems (2002)
Bellman, R., Bellman, R.E., et al.: Introduction to Matrix Analysis (1970)
Williams, C., Seeger, M.: Using the nyström method to speed up kernel machines. In: Proceedings of the 14th Annual Conference on Neural Information Processing Systems (2001)
Drineas, P., Mahoney, M.W.: On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-based Learning. The Journal of Machine Learning Research (2005)
Wang, X., Hamilton, H.J.: DBRS: A Density-based Spatial Clustering Method with Random Sampling. Springer, Heidelberg (2003)
Zhang, K., Tsang, I.W., Kwok, J.T.: Improved nyström low-rank approximation and error analysis. In: Proceedings of the International Conference on Machine Learning (2008)
Kumpula, J.M., Kivelä, M., Kaski, K., Saramäki, J.: Sequential Algorithm for Fast Clique Percolation. Phys. Rev. (2008)
Xiang, T., et al.: Spectral Clustering with Eigenvector Selection. Pattern Recognition(2008)
Von Luxburg, U.: A Tutorial on Spectral Clustering. Statistics and Computing (2007)
Yan, D., Huang, L., Jordan, M.I.: Fast approximate spectral clustering. In: Proceedings of the ACM SIGKDD (2009)
Mall, R., Langone, R., Suykens, J.A.K.: Kernel Spectral Clustering for Big Data Networks. Entropy (2013)
Sun, Z.H., Wei, X.H., Zhou, W.H.: A Nyström-based Subtractive Clustering Method. Wavelet Active Media Technology and Information Processing (ICWAMTIP) (2012)
Fowlkes, C., Belongie, S., Chung, F., et al.: Spectral Grouping Using the Nyström Method. IEEE Transactions on Pattern Analysis and Machine Intelligence (2004)
Belabbas, M.A., Wolfe, P.J.: Spectral methods in machine learning and new strategies for very large datasets. In: Proceedings of the National Academy of Sciences (2009)
Dick, J., Kritzer, P., et al.: Lattice-Nyström Method for Fredholm Integral Equations of the Second Kind with Convolution Type kernels. Journal of Complexity (2007)
Belongie, S., Fowlkes, C., Chung, F., et al.: Spectral Partitioning with Indefinite Kernels Using the Nyström Extension. European Conference on Computer Vision (2002)
Adamic, L.A., Adar, E.: You are what you link. In: The 10th Annual International World Wide Web Conference, Hong Kong (2001)
Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature (2005)
Yang, J., Leskovec, J.: Defining and evaluating network communities based on ground-truth. In: Proceedings of ACM SIGKDD (2012)
Bengio, Y., Paiement, J.F., et al.: Out-of-Sample Extensions for Lle, Isomap, Mds, Eigen-maps and Spectral Clustering. Advances in Neural Information Processing Systems (2004)
Choromanska, A., Jebara, T., Kim, H., et al.: Fast Spectral Clustering via the Nyström Method. Algorithmic Learning Theory (2013)
Xianchao, Z., Quanzeng, Y.: Clusterability analysis and incremental sampling for nyström extension based spectral clustering. In: International Conference on Data Mining (2011)
Danon, L., Duch, J., Diaz-Guilera, A., Arenas, A.: Comparing Community Structure Identification. Stat. Mech. (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kang, Y., Yu, B., Wang, W., Meng, D. (2015). Spectral Clustering for Large-Scale Social Networks via a Pre-Coarsening Sampling based NystrÖm Method. In: Cao, T., Lim, EP., Zhou, ZH., Ho, TB., Cheung, D., Motoda, H. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2015. Lecture Notes in Computer Science(), vol 9078. Springer, Cham. https://doi.org/10.1007/978-3-319-18032-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-18032-8_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18031-1
Online ISBN: 978-3-319-18032-8
eBook Packages: Computer ScienceComputer Science (R0)