Community Detection for Clustered Attributed Graphs via a Variational EM Algorithm

ABSTRACT

Community detection for attributed graphs, also called attributed graph clustering, is a new challenging issue in data mining due to the increasing emergence of different kinds of real-word networks with rich attributes. The existing works for the attributed graph clustering can be divided into two classes, namely distanced-based approaches and model-based approaches. In this paper, we focus on a model-based approach called clustered attributed graph model proposed by Xu et al. [12]. Instead of the original variational Bayes EM algorithm (VBEM) for solving this model, we propose a new variational EM algorithm (VEM). Comparing with the VBEM algorithm, our proposed VEM algorithm can reduce the number of parameters when fitting the model, which brings the lower computational complexity and easier implementation in practice. Additionally, a good model selection criterion ICL can be easily derived under the VEM framework. Our proposed VEM algorithm is demonstrated to perform competitively over the existing state of the art VBEM algorithm in terms of the extensive simulations and the real data.

References

1. L. A. Adamic and N. Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pages 36--43. ACM, 2005.
2. C. Biernacki, G. Celeux, and G. Govaert. Assessing a mixture model for clustering with the integrated completed likelihood. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 22(7):719--725, 2000.
3. H. Cheng, Y. Zhou, and J. X. Yu. Clustering large attributed graphs: A balance between structural and attribute similarities. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(2):12, 2011.
4. J.-J. Daudin, F. Picard, and S. Robin. A mixture model for random graphs. Statistics and computing, 18(2):173--183, 2008.
5. S. Fortunato. Community detection in graphs. Physics Reports, 486(3):75--174, 2010.
6. P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109--137, 1983.
7. Z. G. Matthew J Beal. The Variational Bayesian EM Algorithm for Incomplete Data: with Application to Scoring Graphical Model Structures, volume 7. Oxford University Press, Oxford, 2003.
8. M. E. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113, 2004.
9. J. Scott and P. J. Carrington. The SAGE handbook of social network analysis. SAGE publications, 2011.
10. J. Shi and J. Malik. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 22(8):888--905, 2000.
11. Y. Wang, X. Chang, R. Li, and Z. Xu. Sparse k-means with the ℓq(0 < q < 1) constraint for high-dimensional data clustering. In Data Mining (ICDM), 2013 IEEE 13th International Conference on, pages 797--806. IEEE, 2013.
12. Z. Xu, Y. Ke, Y. Wang, H. Cheng, and J. Cheng. A model-based approach to attributed graph clustering. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 505--516. ACM, 2012.
13. H. Zanghi, S. Volant, and C. Ambroise. Clustering based on random graph model embedding vertex features. Pattern Recognition Letters, 31(9):830--836, 2010.
14. Y. Zhou, H. Cheng, and J. X. Yu. Graph clustering based on structural/attribute similarities. Proceedings of the VLDB Endowment, 2(1):718--729, 2009.
15. Y. Zhou, H. Cheng, and J. X. Yu. Clustering large attributed graphs: An efficient incremental approach. In Data Mining (ICDM), 2010 IEEE 10th International Conference on, pages 689--698. IEEE, 2010.

Index Terms

• Information systems

  • Information systems applications

• Mathematics of computing

  • Discrete mathematics

    • Graph theory