2013/06/18 by Rodrigo Aldecoa, Ignacio Marín · 3 citations
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Advanced Graph Neural Networks #Cluster analysis #Community structure #Complex Network Analysis Techniques #Complex network #Division (mathematics) #Power (physics) #Quality (philosophy) #Surprise #cond-mat.stat-mech #cs.SI #physics.soc-ph
paper · pdf · doi:10.1038/srep02216
published as Scientific Reports 3, 2216 (2013) · 13 pages, 8 figures, 1 table. Scientific Reports (in press)
arxiv created 2013/06/18 · openalex publication_date 2013/07/17 · arxiv updated 2013/08/02 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
The characterization of network community structure has profound implications in several scientific areas. Therefore, testing the algorithms developed to establish the optimal division of a network into communities is a fundamental problem in the field. We performed here a highly detailed evaluation of community detection algorithms, which has two main novelties: 1) using complex closed benchmarks, which provide precise ways to assess whether the solutions generated by the algorithms are optimal; and, 2) A novel type of analysis, based on hierarchically clustering the solutions suggested by multiple community detection algorithms, which allows to easily visualize how different are those solutions. Surprise, a global parameter that evaluates the quality of a partition, confirms the power of these analyses. We show that none of the community detection algorithms tested provide consistently optimal results in all networks and that Surprise maximization, obtained by combining multiple algorithms, obtains quasi-optimal performances in these difficult benchmarks.