2006/08/31 by Pascal Pons, Matthieu Latapy · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Artificial intelligence #Cluster analysis #Community structure #Complex Network Analysis Techniques #Complex network #Computer science #Data mining #Function (biology) #Hierarchical clustering of networks #Mathematics #Modularity (biology) #Opinion Dynamics and Social Influence #Partition (number theory) #Quality (philosophy) #Scale (ratio) #Set (abstract data type) #Similarity (geometry) #Theoretical computer science #cond-mat.dis-nn #cs.DS #physics.soc-ph
paper · pdf · doi:10.1016/j.tcs.2010.11.041
published as Theoretical Computer Science, volume 412, issues 8-10, 4 March 2011, pages 892-900
openalex publication_date 2010/12/05 · arxiv created 2021/01/12 · arxiv updated 2021/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Dense sub-graphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Most existing community detection algorithms produce a hierarchical structure of community and seek a partition into communities that optimizes a given quality function. We propose new methods to improve the results of any of these algorithms. First we show how to optimize a general class of additive quality functions (containing the modularity, the performance, and a new similarity based quality function we propose) over a larger set of partitions than the classical methods. Moreover, we define new multi-scale quality functions which make it possible to detect the different scales at which meaningful community structures appear, while classical approaches find only one partition.