Community detection in Attributed Network

ABSTRACT

Graph clustering techniques are very useful for detecting densely connected groups in large graphs. Many existing graph clustering methods mainly focus on the topological structure, but ignore the vertex properties. Existing graph clustering methods have been recently extended to deal with nodes attribute. First we motivate the interest in the study of this issue. Then we review the main approaches proposed to deal with this problem. We propose a comparative study of some existing attributed network community detection algorithm on both synthetic data and on real world data.

References

1. Martin Atzmueller. 2015. Subgroup and Community Analytics on Attributed Graphs. In SNAFCA@ ICFCA.
2. Vincent D Blondel, Jean-loup Guillaume, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008 (2008), P10008. arXiv:arXiv:0803.0476v2
3. Brigitte Boden. 2014. Combined clustering of graph and attribute data. Apprimus Wissenschaftsver.
4. Cecile Bothorel, Juan David Cruz, Matteo Magnani, and Barbora Micenková. 2015. Clustering attributed graphs: Models, measures and methods. Network Science January (2015), 1--37. arXiv:1501.0167
5. Hong Cheng, Yang Zhou, and Jeffrey Xu Yu. 2011. Clustering Large Attributed Graphs: A Balance between Structural and Attribute Similarities. ACM Trans. Knowl. Discov. Data 5, 2 (2011), 12:1-12:33.
6. David Combe, Christine Largeron, El\H Od Egyed-Zsigmond, and Mathias Géry. 2012. Combining relations and text in scientific network clustering. 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (2012), 1280--1285.
7. David Combe, Christine Largeron, Mathias Géry, and Eld Egyed-Zsigmond. 2015. I-Louvain: An Attributed Graph Clustering Method. In Advances in Intelligent Data Analysis XIV. Springer, 181--192.
8. Juan David Cruz, Cécile Bothorel, and François Poulet. 2011. Entropy based community detection in augmented social networks. In Computational aspects of social networks (cason), 2011 international conference on. IEEE, 163--168.
9. TA Dang and E Viennet. 2012. Community detection based on structural and attribute similarities. In International Conference on Digital Society (ICDS). 7--12.
10. Haithum Elhadi and Gady Agam. 2013. Structure and attributes community detection: comparative analysis of composite, ensemble and selection methods. Proceedings of the 7th Workshop on Social Network Mining and Analysis 13 (2013), 10:1-10:7.
11. Issam Falih, Nistor Grozavu, Rushed Kanawati, and Younès Bennani. 2017. ANCA : Attributed Network Clustering Algorithm. In Complex Networks & Their Applications VI - Proceedings of Complex Networks 2017 (The Sixth International Conference on Complex Networks and Their Applications), COMPLEX NETWORKS 2017, Lyon, France, November 29 - December 1, 2017. (Studies in Computational Intelligence), Chantal Cherifi, Hocine Cherifi, Márton Karsai, and Mirco Musolesi (Eds.), Vol. 689. Springer, 241--252.
12. B. H. Good, Y.-A. de Montjoye, and A. Clauset. 2010. The performance of modularity maximization in practical contexts. Physical Review E, 81 (2010), 046106.
13. Stephan Günnemann, Brigitte Boden, Ines Färber, and Thomas Seidl. 2013. Efficient mining of combined subspace and subgraph clusters in graphs with feature vectors. In Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 261--275.
14. Stephan Günnemann, Ines Farber, Brigitte Boden, and Thomas Seidl. 2010. Subspace clustering meets dense subgraph mining: A synthesis of two paradigms. In Data Mining (ICDM), 2010 IEEE 10th International Conference on. IEEE, 845--850.
15. David R. Karger. 1993. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-out Algorithm. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 93). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 21--30. http://dl.acm.org/citation.cfmid= 313559.313605
16. Andrea Lancichinetti and Santo Fortunato. 2011. Limits of modularity maximization in community detection. CoRR abs/1107.1 (2011).
17. Christine Largeron, Pierre-Nicolas Mougel, Reihaneh Rabbany, and Osmar R. Zaïane. 2015. Generating Attributed Networks with Communities. Plos One 10, 4 (2015), e0122777.
18. Nasif Muslim. 2016. A Combination Approach to Community Detection in Social Networks by Utilizing Structural and Attribute Data. (2016).
19. Waqas Nawaz, Kifayat-Ullah Khan, Young-Koo Lee, and Sungyoung Lee. 2015. Intra graph clustering using collaborative similarity measure. Distributed and Parallel Databases (2015), 583--603.
20. Jennifer Neville, Micah Adler, and David Jensen. 2003. Clustering relational data using attribute and link information. In Proceedings of the text mining and link analysis workshop, 18th international joint conference on artificial intelligence. 9--15.
21. Mark EJ Newman and Aaron Clauset. 2016. Structure and inference in annotated networks. Nature Communications 7 (2016), 11863.
22. M E J Newman. 2003. Mixing patterns in networks. Physical review. E, Statistical, nonlinear, and soft matter physics 67, 2 Pt 2 (2003), 026126. arXiv:cond-mat/0209450
23. M. E. J. Newman and M. Girvan. 2004. Finding and evaluating community structure in networks. Phys. Rev. E 69, 2 (Feb. 2004), 026113.
24. Leto Peel, Daniel B. Larremore, and Aaron Clauset. 2017. The ground truth about metadata and community detection in networks. Science Advances 3, 5 (2017). arXiv:http://advances.sciencemag.org/content/3/5/e1602548.full.pdf
25. Jitesh Shetty and Jafar Adibi. 2004. The Enron email dataset database schema and brief statistical report. Information sciences institute technical report, University of Southern California 4, 1 (2004), 120--128.
26. Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on 22, 8 (2000), 888-- 905.
27. Karsten Steinhaeuser and Nitesh V Chawla. 2008. Community detection in a large real-world social network. In Social computing, behavioral modeling, and prediction. Springer, 168--175.
28. A. Strehl and J. Ghosh. 2003. Cluster ensembles: a knowledge reuse framework for combining multiple partitions. The Journal of Machine Learning Research 3 (2003), 583--617.
29. Sebastian Thrun, Lawrence K Saul, and Bernhard Schölkopf (Eds.). 2004. Advances in Neural Information Processing Systems 16 {Neural Information Processing Systems, NIPS 2003, December 8--13, 2003, Vancouver and Whistler, British Columbia, Canada}. MIT Press.
30. Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, and James Cheng. 2012. A model-based approach to attributed graph clustering. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM, 505--516.
31. Zhiqiang Xu, Yiping Ke, Yi Wang, Hong Cheng, and James Cheng. 2014. GBAGC: A General Bayesian Framework for Attributed Graph Clustering. ACM Trans. Knowl. Discov. Data 9, 1 (2014), 1--43.
32. Zied Yakoubi and Rushed Kanawati. 2014. Licod: Leader-driven approaches for community detection. Vietnam Journal of Computer Science 1, 4 (2014), 241--256.
33. Jaewon Yang, Julian McAuley, and Jure Leskovec. 2013. Community detection in networks with node attributes. Proceedings - IEEE International Conference on Data Mining, ICDM (2013), 1151--1156. arXiv:1401.7267
34. Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2010. Clustering large attributed graphs: An efficient incremental approach. Proceedings - IEEE International Conference on Data Mining, ICDM (2010), 689--698.

Index Terms

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Social networks

    • Machine learning theory

      • Unsupervised learning and clustering