2013/07/10 by Michel Crampes, Crampes, Michel, Michel Plantié +3
Decision Sciences · Mathematics · Physics and Astronomy · #Algorithm #Complex Network Analysis Techniques #Computer science #FOS: Computer and information sciences #Function (biology) #Game Theory and Applications #Heuristics #Machine Learning (stat.ML) #Mathematical optimization #Mathematics #Modularity (biology) #Multipartite #Nash equilibrium #Opinion Dynamics and Social Influence #Quantum #Theoretical computer science #stat.ML
paper · pdf · doi:10.48550/arxiv.1307.2715
published in arXiv (Cornell University) (Cornell University)
arxiv created 2013/07/10 · openalex publication_date 2013/07/10 · arxiv updated 2013/07/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Community detection in graphs has been the subject of many algorithms. Recent methods want to optimize a modularity function which shows a maximum of relationships within communities and found a minimum of inter-community relations. these algorithms are applied to unipartite, multipartite and directed graphs. However, given the NP-completeness of the problem, these algorithms are heuristics that do not guarantee an optimum. In this paper we introduce an algorithm which, based on an approximate solution obtained through a efficient detection algorithm, modifie it to achieve a local optimum based on a function. this reassignment function is a potential function and therefore the computed optimum is a Nash equilibrium. We supplement our method with an overlap function that allows to have simultaneously the two detection modes. Several experiments show the interest of our approach.