Worst-case test network optimization for community detection method

ABSTRACT

Network community detection finds communities/clusters of densely connected nodes with few edges outside the cluster. It is applied in a variety of domains, from e-commerce in social networks or web graphs, up to analysis of biochemical networks or control and automation tasks. Hi-consequence risk applications range from black-start recovery of power systems, truss structure manufacturing, neural motor control, water distribution, to image segmentation for finding cracks in bridges. For such important technical applications, it is necessary to know the limits of the used methods, how much they can deviate from optimum. The robustness of the community detection methods was already compared using a number of test networks, both real world and artificial. However, these test networks were implicitly average cases. Here, we evolve networks, which produce a maximum error of modularity measure for selected methods of community detection. This worst-case test networks were evolved for Edge betweenness, Fast greedy, Infomap, Louvain, and Walktrap modularity detection. Such a comparison provides a tougher test of robustness than previous approaches. A bit surprisingly, after the Blondel's Louvain method, the next best result was provided by fast greedy, while otherwise favored Infomap fared rather poorly.

References

1. M. Newman, Networks: An Introduction. Oxford University Press, 2010.
2. A.-L. Barabási, M. Pósfai, Network Science. Cambridge University Press, 2016, see also http://barabasi.com/networksciencebook, last visit 7.4.2017
3. P.A. Duijn, P.P. Klerks, "Social network analysis applied to criminal networks: Recent developments in Dutch law enforcement", inNetworks and network analysis for defence and security, A.J. Masys, ed. Springer International Publishing, 2014, pp. 121--159.
4. M. Korytarand D. Gabriska, "Integrated security levels and analysis of their implications to the maintenance," J. of Applied Mathematics, Statistics and Informatics, vol. 10(2), pp. 33--42, 2014.
5. M. Šimon, L. Huraj, M. Čerňanský, "Performance Evaluations of IPTables Firewall Solutions under DDoS attacks," J. of Applied Mathematics, Statistics and Informatics, vol. 11(2), pp. 35--45, 2015.
6. L. Huraj and V. Siládi, "Authorization through trust chains in ad hoc grids.," in Proceedings of the 2009 Euro American Conference on Telematics and Information Systems: New Opportunities to increase Digital Citizenship, p. 13. ACM, 2009.
7. Y. Liu, T. Liu, Q. Li, and X. Hu, "Chapter 33. Power system black-start recovery subsystems partition based on improved CNM community detection algorithm," in Proceedings of the 2015 International Conference on Electric, Electronic and Control Engineering (ICEECE 2015), F. Shao, W. Shu, and T. Tian, Eds. CRC Press, 2015, pp. 183--189.
8. H. Cao, R. Mo, N. Wan, F. Shang, C. Li, and D. Zhang, "A subassembly identification method for truss structures manufacturing based on community detection," Assembly Automation, vol. 35(3), pp. 249--258, 2015.
9. A. Büschgesand A. Borgmann, "Network modularity: back to the future in motor control," Current Biology, vol. 23(20), pp. R936--R938, 2013.
10. O. Giustolisiand L. Ridolfi, "A novel infrastructure modularity index for the segmentation of water distribution networks," Water Resources Research, vol. 50(10), pp. 7648--7661, 2014.
11. H. Hu, Y. van Gennip, B. Hunter, A.L. Bertozzi, and MA. Porter, "Multislice modularity optimization in community detection and image segmentation," in Data Mining Workshops (ICDMW), 2012 IEEE 12th International Conference on Data Mining, pp. 934--936, IEEE, December 2012.
12. CM. Yeumand S.J. Dyke, "Vision-Based Automated Crack Detection for Bridge Inspection," Computer-Aided Civil and Infrastructure Engineering, vol. 30(10), pp. 759--770, 2015.
13. R. Kannan, S. Vempala, and A. Vetta, "On clusterings: Good, bad and spectral," Journal of the ACM (JACM), vol. 51(3), pp. 497--515, 2004.
14. S.E. Schaeffer, "Graph clustering," Computer science review, vol. 1(1), pp. 27--64, 2007.
15. M. Newman and M. Girvan, "Finding and evaluating community structure in networks," Phys. Rev. E vol. 69, p. 026113, 2004.
16. M. Chen, K. Kuzmin, B. K. Szymanski, "Community detection via maximization of modularity and its variants," IEEE Transactions on Computational Social Systems, vol. 1(1), pp. 46--65, 2014.
17. N.P. Nguyen, T.N. Dinh, Y. Shen, and M.T. Thai, "Dynamic social community detection and its applications," PloS one, vol. 9(4), p. e91431, 2014.
18. L. Danon, A. Diaz-Guilera, J. Duch, and A. Arenas, "Comparing community structure identification," J. of Statistical Mechanics: Theory and Experiment, vol. 2005(09), p. P09008, 2005.
19. B. H. Good, Y. A. de Montjoye, and A.Clauset, "Performance of modularity maximization in practical contexts," Physical Review E, vol. 81(4), 046106,2010.
20. S. Harenberg, G. Bello, L. Gjeltema, S. Ranshous, J. Harlalka, R. Seay, K. Padmanabhan, and N. Samatova, "Community detection in large-scale networks: a survey and empirical evaluation," Wiley Interdisciplinary Reviews: Computational Statistics, vol. 6(6), pp. 426--439, 2014.
21. J. Leskovec, K.J. Lang, and M. Mahoney, "Empirical comparison of algorithms for network community detection," in Proceedings of the 19th international conference on World wide web, pp. 631--640. ACM, April 2010.
22. A. Lancichinetti, S. Fortunato, and F. Radicchi, "Benchmark graphs for testing community detection algorithms," Physical review E, vol. 78(4), p. 046110, 2008.
23. A. Lancichinetti, "Evaluating the performance of clustering algorithms in networks," in Dynamics On and Of Complex Networks, vol. 2.Springer: New York, 2013, pp. 143--158.
24. G.K. Ormanand V. Labatut, "A comparison of community detection algorithms on artificial networks," in International Conference on Discovery Science. Springer: Berlin Heidelberg, 2009, pp. 242--256.
25. G. Orman, V. Labatut, and H. Cherifi, "Qualitative comparison of community detection algorithms," arXiv preprint arXiv:1207.3603, 2012.
26. Y. Zhao, R. Algesheimer, and C.J. Tessone, "A Comparative Analysis of Community Detection Algorithms on Artificial Networks," Scientific Reports, vol. 6, 2016.
27. S. Wandeltand X. Sun, "Complex network analysis: The need for speed.," in Control Conference (CCC), 35th Chinese, pp. 1213--1218. IEEE, July 2016.
28. G. Csardiand T. Nepusz, "The igraph software package for complex network research," InterJournal, Complex Systems 1695, URL http://igraph.org (2006).
29. M. Girvan and M.E. Newman, "Community structure in social and biological networks," Proceedings of the National Academy of Sciences, vol. 99, pp. 7821--7826, 2002.
30. L.C. Freeman, "Centrality in social networks conceptual clarification," Social Networks, vol. 1, pp. 215--239, 1979.
31. A. Clauset, M.E. Newman, and C. Moore, "Finding community structure in very large networks," Physical Review E, vol. 70, p. 066111, 2004.
32. M. Rosvalland C.T. Bergstrom, "An information-theoretic framework for resolving community structure in complex networks," Proceedings of the National Academy of Sciences, vol. 104, pp. 7327--7331, 2007.
33. M. Rosvall, D. Axelsson, and C. T. Bergstrom, "The map equation," The European Physical Journal Special Topics, vol. 178, pp. 13--23, 2010.
34. A. Mukherjee, M. Choudhury, F. Peruani, N. Ganguly, and B. Mitra, "Dynamics On and Of Complex Networks, Volume 2: Applications to Time-Varying Dynamical Systems," Springer Science & Business Media, 2013.
35. U.N. Raghavan, R. Albert, and S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Physical Review E, vol. 76, p. 036106, 2007.
36. M.E. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical Review E, vol. 74, p. 036104, 2006.
37. V.D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks", Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, p. P10008, 2008.
38. U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, and D. Wagner, "On modularity clustering," IEEE transactions on knowledge and data engineering, vol. 20(2), pp. 172--188, 2008.
39. J. Reichardtand S. Bornholdt, "Statistical mechanics of community detection," Physical Review E, vol. 74, p. 016110, 2006.
40. P. Pons and M. Latapy, "Computing communities in large networks using random walks," in Computer and Information Sciences-ISCIS 2005, pp. 284--293Springer, 2005.
41. J. Xieand B.K. Szymanski, "Community detection using a neighborhood strength driven label propagation algorithm," in Network Science Workshop, pp. 188--195. IEEE, 2011

Index Terms

• Information systems

  • Information storage systems

    • Storage management

  • Information systems applications

    • Data mining

• Mathematics of computing

  • Discrete mathematics

    • Graph theory