×

Importance of numerical implementation and clustering analysis in force-directed algorithms for accurate community detection. (English) Zbl 1510.91129

Summary: Real-world networks show community structures – groups of nodes that are densely intra-connected and sparsely inter-connected to other groups. Nevertheless, Community Detection (CD) is non-trivial, since identifying these groups of nodes according to their local connectivity can hold many plausible solutions, leading to the creation of different methods. In particular, CD has recently been achieved by Force-Directed Algorithms (FDAs), which originally were designed as a way to visualize networks. FDAs map the network nodes as particles in a \(D\)-dimensional space that are affected by forces acting in accordance to the connectivity. However, the literature on FDA-based methods for CD has grown in parallel from the classical methods, leaving several open questions, such as how accurately FDAs can recover communities compared to classical methods. In this work, we start to fill these gaps by evaluating different numerical implementations of 5 FDA methods and different clustering analyses on state-of-the-art network benchmarks – including networks with or without weights and networks with a hierarchical organisation. We also compare these results with 8, well-known, classical CD methods. Our findings show that FDA methods can achieve higher accuracy than classical methods, albeit their effectiveness depends on the chosen setting – with optimisation techniques leading over numerical integration and distance-based clustering algorithms leading over density-based ones. Overall, our work provides detailed information for any researcher aiming to apply FDAs for community detection.

MSC:

91D30 Social networks; opinion dynamics
68R10 Graph theory (including graph drawing) in computer science
62H30 Classification and discrimination; cluster analysis (statistical aspects)
05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C85 Graph algorithms (graph-theoretic aspects)

Software:

JIGGLE; Scikit
Full Text: DOI

References:

[1] Aggarwal, C. C.; Reddy, C. K., Data clustering, Algorithms and applications. Chapman&Hall/CRC Data mining and Knowledge Discovery series, Londra (2014) · Zbl 1331.62026
[2] Barnes, J.; Hut, P., A hierarchical o (n log n) force-calculation algorithm, Nature, 324, 446-449 (1986)
[3] Blondel, V. D.; Guillaume, J. L.; Lambiotte, R.; Lefebvre, E., Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment, 2008, P10008 (2008) · Zbl 1459.91130
[4] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D. U., Complex networks: Structure and dynamics, Physics Reports, 424, 175-308 (2006) · Zbl 1371.82002
[5] Brandes, U., Drawing on physical analogies, Drawing graphs, 71-86 (2001), Springer · Zbl 0981.68593
[6] Cai, Y.; Morales, J. A.; Wang, S.; Pimentel, P.; Casey, W.; Volkmann, A., Pheromone model based visualization of malware distribution networks, International Conference on Computational Science, 55-68 (2018), Springer
[7] Cheong, S. H.; Si, Y. W., Force-directed algorithms for schematic drawings and placement: A survey, Information Visualization, 19, 65-91 (2020)
[8] Clauset, A.; Newman, M. E.; Moore, C., Finding community structure in very large networks, Physical review E, 70, 066111 (2004)
[9] Coleman, M. K.; Parker, D. S., Aesthetics-based graph layout for human consumption, Software: Practice and Experience, 26, 1415-1438 (1996)
[10] Crippa, A.; Cerliani, L.; Nanetti, L.; Roerdink, J. B., Heuristics for connectivity-based brain parcellation of sma/pre-sma through force-directed graph layout, NeuroImage, 54, 2176-2184 (2011)
[11] Danon, L.; Diaz-Guilera, A.; Duch, J.; Arenas, A., Comparing community structure identification, Journal of Statistical Mechanics: Theory and Experiment, 2005, P09008 (2005)
[12] Dao, V. L.; Bothorel, C.; Lenca, P., Community structure: A comparative evaluation of community detection methods, Network Science, 8, 1-41 (2020)
[13] Davidson, R.; Harel, D., Drawing graphs nicely using simulated annealing, ACM Transactions on Graphics, 15, 301-331 (1996)
[14] Duch, J.; Arenas, A., Community detection in complex networks using extremal optimization, Physical review E, 72, 027104 (2005)
[15] Ester, M.; Kriegel, H. P.; Sander, J.; Xu, X., A density-based algorithm for discovering clusters in large spatial databases with noise, KDD-96 Proceedings, 226-231 (1996)
[16] B.S. Everitt, S. Landau, M. Leese, D. Stahl, Cluster analysis 5th ed, 2011, (????). · Zbl 1274.62003
[17] Fortunato, S., Community detection in graphs, Physics Reports, 486, 75-174 (2010)
[18] Fortunato, S.; Barthelemy, M., Resolution limit in community detection, Proceedings of the National Academy of Sciences, 104, 36-41 (2007)
[19] Fortunato, S.; Hric, D., Community detection in networks: A user guide, Physics Reports, 659, 1-44 (2016)
[20] Fruchterman, T. M.; Reingold, E. M., Graph drawing by force-directed placement, Software: Practice and Experience, 21, 1129-1164 (1991)
[21] Girvan, M.; Newman, M. E., Community structure in social and biological networks, Proceedings of the National Academy of Sciences, 99, 7821-7826 (2002) · Zbl 1032.91716
[22] Gouvêa, M. M.M. A.; Silva, S. T.; Macau, E. E.N.; Quiles, M., Force-directed algorithms as a tool to supportcommunity detection: A review, The European Physical Journal Special Topics, 19, 65-91 (2020)
[23] Granell, C.; Darst, R. K.; Arenas, A.; Fortunato, S.; Gómez, S., Benchmark model to assess community structure in evolving networks, Physical Review E, 92, 012805 (2015)
[24] Gupta, M.; Aggarwal, C. C.; Han, J.; Sun, Y., Evolutionary clustering and analysis of bibliographic networks, 2011 International Conference on Advances in Social Networks Analysis and Mining (2011), IEEE,63-70
[25] Han, J.; Kamber, M.; Pei, J., Data mining concepts and techniques third edition, The Morgan Kaufmann Series in Data Management Systems, 5, 83-124 (2011)
[26] Hartigan, J. A., Clustering algorithms (1975), John Wiley & Sons, Inc. · Zbl 0372.62040
[27] Javed, M. A.; Younis, M. S.; Latif, S.; Qadir, J.; Baig, A., Community detection in networks: A multidisciplinary review, Journal of Network and Computer Applications, 108, 87-111 (2018)
[28] Jiang, S.; Li, X.; Chen, X.; Wang, Z.; Perc, M.; Gao, C., Multi-objective optimization for community detection in multilayer networks, Europhysics Letters, 135, 18001 (2021)
[29] Kaufmann, M.; Wagner, D., Drawing graphs: methods and models (2003), Springer
[30] Lancichinetti, A.; Fortunato, S., Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities, Physical Review E, 80, 016118 (2009)
[31] Lancichinetti, A.; Fortunato, S.; Radicchi, F., Benchmark graphs for testing community detection algorithms, Physical review E, 78, 046110 (2008)
[32] Li, H. J.; Wang, L.; Zhang, Y.; Perc, M., Optimization of identifiability for efficient community detection, New Journal of Physics, 22, 063035 (2020)
[33] Lim, S.; Kim, J.; Lee, J. G., Blackhole: Robust community detection inspired by graph drawing, IEEE 32nd International Conference on Data Engineering (ICDE), 25-36 (2016), IEEE
[34] Liu, T.; Ahmed, D. B.; Bouali, F.; Venturini, G., Visual and interactive exploration of a large collection of open datasets, 17th International Conference on Information Visualisation (2013), IEEE,285-290
[35] Luce, R. D.; Perry, A. D., A method of matrix analysis of group structure, Psychometrika, 14, 95-116 (1949)
[36] Maia, D. M.; de Oliveira, J. E.; Quiles, M. G.; Macau, E. E., Community detection in complex networks via adapted kuramoto dynamics, Communications in Nonlinear Science and Numerical Simulation, 53, 130-141 (2017) · Zbl 1510.91135
[37] McSweeney, P. J.; Mehrotra, K.; Oh, J. C., A force-directed layout for community detection with automatic clusterization, Simulating Interacting Agents and Social Phenomena (2010), Springer,49-63
[38] Mohamed, E. M.; Agouti, T.; Tikniouine, A.; El Adnani, M., A comprehensive literature review on community detection: Approaches and applications, Procedia Computer Science, 151, 295-302 (2019)
[39] Newman, M. E., Fast algorithm for detecting community structure in networks, Physical review E, 69, 066133 (2004)
[40] Newman, M. E., Finding community structure in networks using the eigenvectors of matrices, Physical review E, 74, 036104 (2006)
[41] Newman, M. E., Modularity and community structure in networks, Proceedings of the National Academy of Sciences, 103, 8577-8582 (2006)
[42] Noack, A., An energy model for visual graph clustering, International Symposium on Graph Drawing (2003), Springer,425-436 · Zbl 1215.05119
[43] Noack, A., Energy models for drawing clustered small-world graphs, Technical Report. Fachgebiet Praktische Informatik. (2004)
[44] Noack, A., Energy-based clustering of graphs with nonuniform degrees, International Symposium on Graph Drawing, 309-320 (2005), Springer · Zbl 1171.68636
[45] Noack, A., Energy models for graph clustering, J. Graph Algorithms Appl., 11, 453-480 (2007) · Zbl 1161.68691
[46] Noack, A., Unified quality measures for clusterings, layouts, and orderings of graphs, and their application as software design criteria, Ph.D. thesis. Naturwissenschaften und Informatik der Brandenburgischen Technischen Universitt Cottbus (2007)
[47] Noack, A., Modularity clustering is force-directed layout, Physical Review E, 79, 026102 (2009)
[48] Palmer, A.; Sinnen, O., Scheduling algorithm based on force directed clustering, 9th International Conference on Parallel and Distributed Computing, Applications and Technologies (2008), IEEE,311-318
[49] 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., Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12, 2825-2830 (2011) · Zbl 1280.68189
[50] Pons, P.; Latapy, M., Computing communities in large networks using random walks, International Symposium on Computer and Information Sciences (2005), Springer,284-293
[51] Quigley, A. J., Large scale relational information visualization, clustering, and abstraction Ph.D. thesis. University of Newcastle (2001)
[52] M. Quiles, Particle community: A dynamical model for detecting communities in complex networks, 2016, (????).
[53] Quiles, M. G.; Macau, E. E.; Rubido, N., Dynamical detection of network communities, Scientific Reports, 6, 25570 (2016)
[54] Radicchi, F.; Castellano, C.; Cecconi, F.; Loreto, V.; Parisi, D., Defining and identifying communities in networks, Proceedings of the National Academy of Sciences, 101, 2658-2663 (2004)
[55] Raghavan, U. N.; Albert, R.; Kumara, S., Near linear time algorithm to detect community structures in large-scale networks, Physical Review E, 76, 036106 (2007)
[56] Ravasz, E.; Barabási, A. L., Hierarchical organization in complex networks, Physical review E, 67, 026112 (2003)
[57] Reichardt, J.; Bornholdt, S., Statistical mechanics of community detection, Physical review E, 74, 016110 (2006)
[58] Rossetti, G.; Cazabet, R., Community discovery in dynamic networks: a survey, ACM Computing Surveys, 51, 1-37 (2018)
[59] Rosvall, M.; Bergstrom, C. T., Maps of random walks on complex networks reveal community structure, Proceedings of the National Academy of Sciences, 105, 1118-1123 (2008)
[60] Rosvall, M.; Delvenne, J. C.; Schaub, M. T.; Lambiotte, R., Different approaches to community detection, Advances in network clustering and blockmodeling, 105-119 (2019)
[61] Seidman, S. B.; Foster, B. L., A graph-theoretic generalization of the clique concept, Journal of Mathematical Sociology, 6, 139-154 (1978) · Zbl 0386.92015
[62] Song, Y.; Bressan, S., Force-directed layout community detection, International Conference on Database and Expert Systems Applications (2013), Springer,419-427
[63] Tan, P. N.; Steinbach, M.; Kumar, V., Introduction to data mining (2016), Pearson Education India
[64] Tandon, A.; Albeshri, A.; Thayananthan, V.; Alhalabi, W.; Radicchi, F.; Fortunato, S., Community detection in networks using graph embeddings, Physical Review E, 103, 022316 (2021)
[65] Tunkelang, D., Jiggle: Java interactive graph layout environment, International Symposium on Graph Drawing (1998), Springer,413-422
[66] Tunkelang, D.; Sleator, D.; Heckbert, P.; Maggs, B., A numerical optimization approach to general graph drawing, Ph.D. thesis. Carnegie Mellon’s School of Computer Science (1999)
[67] Udrescu, M.; Udrescu, L., A drug repurposing method based on drug-drug interaction networks and using energy model layouts, Computational Methods for Drug Repurposing (2019), Springer,185-201
[68] Yang, B.; Liu, D. Y., Force-based incremental algorithm for mining community structure in dynamic network, Journal of Computer Science and Technology, 21, 393-400 (2006) · Zbl 1190.68053
[69] Yang, Z.; Perotti, J. I.; Tessone, C. J., Hierarchical benchmark graphs for testing community detection algorithms, Physical review E, 96, 052311 (2017)
[70] Zabiniako, V., Using force-based graph layout for clustering of relational data, East European Conference on Advances in Databases and Information Systems (2009), Springer,193-201
[71] Zachary, W. W., An information flow model for conflict and fission in small groups, Journal of Anthropological Research, 33, 452-473 (1977)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.