Abstract
Community detection is one of the most widely studied tasks in network analysis because community structures are ubiquitous across real-world networks. These real-world networks are often both attributed and dynamic in nature. In this paper, we propose a community detection algorithm for dynamic attributed graphs that, unlike existing community detection methods, incorporates both temporal and attribute information along with the structural properties of the graph. Our proposed algorithm handles graphs with heterogeneous attribute types, as well as changes to both the structure and the attribute information, which is essential for its applicability to real-world networks. We evaluated our proposed algorithm on a variety of synthetically generated benchmark dynamic attributed graphs, as well as on large-scale real-world networks. The results obtained show that our proposed algorithm is able to identify graph partitions of high modularity and high attribute similarity more efficiently than state-of-the-art methods for community detection.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aynaud, T., Guillaume, J.: Static community detection algorithms for evolving networks. In: Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2010, pp. 513–519 (2010)
Bello, G.A., Angus, M., Pedemane, N., Harlalka, J.K., Semazzi, F.H.M., Kumar, V., Samatova, N.F.: Response-guided community detection: application to climate index discovery. In: Appice, A., Rodrigues, P.P., Santos Costa, V., Gama, J., Jorge, A., Soares, C. (eds.) ECML PKDD 2015. LNCS (LNAI), vol. 9285, pp. 736–751. Springer, Heidelberg (2015). doi:10.1007/978-3-319-23525-7_45
Blondel, V., Guillaume, J., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theor. Exp. 2008(10), P10008 (2008)
Bothorel, C., Cruz, J., Magnani, M., Micenkova, B.: Clustering attributed graphs: models, measures and methods. Netw. Sci. 3(03), 408–444 (2015)
Combe, D., Largeron, C., Géry, M., Egyed-Zsigmond, E.: I-Louvain: an attributed graph clustering method. In: Fromont, E., Bie, T., Leeuwen, M. (eds.) IDA 2015. LNCS, vol. 9385, pp. 181–192. Springer, Heidelberg (2015). doi:10.1007/978-3-319-24465-5_16
Dang, T., Viennet, E.: Community detection based on structural and attribute similarities. In: International Conference on Digital Society, pp. 7–12 (2012)
Dinh, T., Xuan, Y., Thai, M.: Towards social-aware routing in dynamic communication networks. In: 2009 IEEE 28th IPCCC, pp. 161–168. IEEE (2009)
Elhadi, H., Agam, G.: Structure and attributes community detection: comparative analysis of composite, ensemble and selection methods. In: Proceedings of the 7th Workshop on Social Network Mining and Analysis, pp. 10:1–10:7 (2013)
Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75–174 (2010)
Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78(4), 046110 (2008)
Newman, M.: Analysis of weighted networks. Phys. Rev. E 70(5), 056131 (2004)
Newman, M., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69(2), 026113 (2004)
Peel, L.: Estimating network parameters for selecting community detection algorithms. In: 2010 13th Conference on Information Fusion, pp. 1–8. IEEE (2010)
Ruan, Y., Fuhry, D., Parthasarathy, S.: Efficient community detection in large networks using content and links. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1089–1098. ACM (2013)
Zhou, Y., Cheng, H., Yu, J.: Clustering large attributed graphs: an efficient incremental approach. In: 2010 IEEE 10th ICDM, pp. 689–698. IEEE (2010)
Acknowledgments
This material is based upon work supported in part by the Laboratory for Analytic Sciences, the U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research, and NSF grant 1029711.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Bello, G.A., Harenberg, S., Agrawal, A., Samatova, N.F. (2016). Community Detection in Dynamic Attributed Graphs. In: Li, J., Li, X., Wang, S., Li, J., Sheng, Q. (eds) Advanced Data Mining and Applications. ADMA 2016. Lecture Notes in Computer Science(), vol 10086. Springer, Cham. https://doi.org/10.1007/978-3-319-49586-6_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-49586-6_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-49585-9
Online ISBN: 978-3-319-49586-6
eBook Packages: Computer ScienceComputer Science (R0)