Evaluating community detection algorithms for progressively evolving graphs
Cazabet R., Boudebza S., Rossetti G.
Computer Science - Machine Learning Management Science and Operations Research Computational Mathematics Control and Optimization Social and Information Networks (cs.SI) [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG] Community detection Dynamic Networks Computer Networks and Communications FOS: Physical sciences Computer Science - Social and Information Networks Network Generator [INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI] Dynamic communities Dynamic networks FOS: Computer and information sciences Community Detection Physics - Physics and Society Dynamic Communities Network generator Applied Mathematics Machine Learning (cs.LG) Physics and Society (physics.soc-ph)
Many algorithms have been proposed in the last 10 years for the discovery of dynamic communities. However, these methods are seldom compared between themselves. In this article, we propose a generator of dynamic graphs with planted evolving community structure, as a benchmark to compare and evaluate such algorithms. Unlike previously proposed benchmarks, it is able to specify any desired evolving community structure through a descriptive language, and then to generate the corresponding progressively evolving network. We empirically evaluate six existing algorithms for dynamic community detection in terms of instantaneous and longitudinal similarity with the planted ground truth, smoothness of dynamic partitions and scalability. We notably observe different types of weaknesses depending on their approach to ensure smoothness, namely Glitches, Oversimplification and Identity loss. Although no method arises as a clear winner, we observe clear differences between methods, and we identified the fastest, those yielding the most smoothed or the most accurate solutions at each step.
Source: Journal of complex networks (Print) 8 (2020). doi:10.1093/comnet/cnaa027
Publisher: Oxford University Press, Oxford, Regno Unito
[2] Bazzi, M., Jeub, L. G., Arenas, A., Howison, S. D. & Porter, M. A. (2016) Generative benchmark models for mesoscale structure in multilayer networks. arXiv preprint arXiv:1608.06196.
[3] Benyahia, O., Largeron, C., Jeudy, B. & Zaane, O. R. (2016) Dancer: Dynamic attributed network with community structure generator. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 41{44. Springer.
[4] Blondel, V. D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008) Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, P10008.
[5] Cazabet, R. & Rossetti, G. (2019) Challenges in community discovery on temporal networks. In Temporal Network Theory, pages 181{197. Springer.
[6] Chykhradze, K., Korshunov, A., Buzun, N., Pastukhov, R., Kuzyurin, N., Turdakov, D. & Kim, H. (2014) Distributed generation of billion-node social graphs with overlapping community structure. In Complex Networks V, pages 199{208. Springer.
[7] Coppens, L., De Venter, J., Mitrovi, S. & De Weerdt, J. (2019) A comparative study of community detection techniques for large evolving graphs. In LEG@ ECML: The third International Workshop on Advances in Managing and Mining Large Evolving Graphs collocated with ECML-PKDD. Springer.
[8] Falkowski, T. & Spiliopoulou, M. (2007) Data Mining for Community Dynamics. KI, 21(3), 23{29.
[9] Folino, F. & Pizzuti, C. (2013) An evolutionary multiobjective approach for community discovery in dynamic networks. IEEE Transactions on Knowledge and Data Engineering, 26(8), 1838{1852.
[10] Genois, M. & Barrat, A. (2018) Can co-location be used as a proxy for face-to-face contacts?. EPJ Data Science, 7(1), 11.
[11] Ghasemian, A., Zhang, P., Clauset, A., Moore, C. & Peel, L. (2016) Detectability thresholds and optimal algorithms for community structure in dynamic networks. Physical Review X, 6(3), 031005.
[12] Granell, C., Darst, R. K., Arenas, A., Fortunato, S. & Gomez, S. (2015) Benchmark model to assess community structure in evolving networks. Physical Review E, 92(1), 012805.
[13] Greene, D., Doyle, D. & Cunningham, P. (2010) Tracking the evolution of communities in dynamic social networks. In Advances in social networks analysis and mining (ASONAM), 2010 international conference on, pages 176{183. IEEE.
[14] Guo, C., Wang, J. & Zhang, Z. (2014) Evolutionary community structure discovery in dynamic weighted networks. Physica A: Statistical Mechanics and its Applications, 413, 565{576.
[15] Hagberg, A., Swart, P. & S Chult, D. (2008) Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
[16] Holland, P. W., Laskey, K. B. & Leinhardt, S. (1983) Stochastic blockmodels: First steps. Social networks, 5(2), 109{137.
[17] Kawadia, V. & Sreenivasan, S. (2012) Sequential detection of temporal communities by estrangement con nement. Scienti c reports, 2, 794.
[18] Kobayashi, T., Takaguchi, T. & Barrat, A. (2019) The structured backbone of temporal social ties. Nature communications, 10(1), 1{11.
[19] Lancichinetti, A., Fortunato, S. & Radicchi, F. (2008) Benchmark graphs for testing community detection algorithms. Physical review E, 78(4), 046110.
[20] Leskovec, J., Kleinberg, J. & Faloutsos, C. (2005) Graphs over time: densication laws, shrinking diameters and possible explanations. In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 177{187.
[21] Leskovec, J. & Krevl, A. (2014) SNAP Datasets: Stanford Large Network Dataset collection. http://snap.stanford.edu/data.
[22] Li, H. J., Wang, L., Zhang, Y., & Perc M. (2020). Optimization of identi ability for e cient community detection. In New Journal of Physics, 22(6).
[23] Lin, Y.-R., Chi, Y., Zhu, S., Sundaram, H. & Tseng, B. L. (2008) Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In Proceedings of the 17th international conference on World Wide Web, pages 685{694. ACM.
[24] Linhares, C. D., Travencolo, B. A., Paiva, J. G. S. & Rocha, L. E. (2017) DyNetVis: A system for visualization of dynamic networks. In Proceedings of the Symposium on Applied Computing, pages 187{194. ACM.
[25] Mucha, P. J., Richardson, T., Macon, K., Porter, M. A. & Onnela, J.-P. (2010) Community structure in time-dependent, multiscale, and multiplex networks. science, 328(5980), 876{878.
[26] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M. & Duchesnay, E. (2011) Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research, 12, 2825{2830.
[27] Perc, M. & Szolnoki, A. (2010). Coevolutionary games|a mini review. In BioSystems, 99(2) pages109-125.
[28] Rossetti, G. (2017) RDYN: graph benchmark handling community dynamics. Journal of Complex Networks, 5(6), 893{912.
[29] Rossetti, G. & Cazabet, R. (2018) Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR), 51(2), 1{37.
[30] Rossetti, G., Milli, L. & Cazabet, R. (2019) CDLIB: a python library to extract, compare and evaluate communities from complex networks. Applied Network Science, 4(1), 52.
[31] Sarzynska, M., Leicht, E. A., Chowell, G. & Porter, M. A. (2015) Null models for community detection in spatially embedded, temporal networks. Journal of Complex Networks, 4(3), 363{406.
[32] Sengupta, N., Hamann, M. & Wagner, D. (2017) Benchmark Generator for Dynamic Overlapping Communities in Networks. In Data Mining (ICDM), 2017 IEEE International Conference on, pages 415{424. IEEE.
[33] Tantipathananandh, C. & Berger-Wolf, T. Y. (2011) Finding communities in dynamic social networks. In Data Mining (ICDM), 2011 IEEE 11th International Conference on, pages 1236{1241. IEEE.
[34] Xu, K. S. & Hero, A. O. (2014) Dynamic stochastic blockmodels for timeevolving social networks. IEEE Journal of Selected Topics in Signal Processing, 8(4), 552{562.
[35] Zhang, X., Moore, C. & Newman, M. E. (2017) Random graph models for dynamic networks. The European Physical Journal B.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:454271,
title = {Evaluating community detection algorithms for progressively evolving graphs},
author = {Cazabet R. and Boudebza S. and Rossetti G.},
publisher = {Oxford University Press, Oxford, Regno Unito},
doi = {10.1093/comnet/cnaa027 and 10.48550/arxiv.2007.08635},
journal = {Journal of complex networks (Print)},
volume = {8},
year = {2020}
}
0000-0003-3373-1240ISTI Repository
DOI
10.1093/comnet/cnaa027
10.48550/arxiv.2007.08635
academic.oup.com
arXiv.org e-Print Archive
Journal of Complex Networks
Hyper Article en Ligne
BITUNAM
Bitcoin User Network Analysis and Mining
SoBigData-PlusPlus
SoBigData++: European Integrated Infrastructure for Social Mining and Big Data Analytics
