HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Overlapping Community Detection Optimization and Nash Equilibrium

Abstract : Community detection in social networks is the focus of many algorithms. Recent methods aimed at optimizing the so-called modularity function proceed by maximizing relations within communities while minimizing inter-community relations. However, given the NP-completeness of the problem, these algorithms are heuristics that do not guarantee an optimum. In this paper, we introduce a new algorithm along with a function that takes an approximate solution and modifies it in order to reach an optimum. This reassignment function is considered a `potential function' and becomes a necessary condition to asserting that the computed optimum is indeed a Nash Equilibrium. We also use this function to simultaneously show two detection and visualization modes: partitioned and overlaped communities, of great value in revealing interesting features in a social network. Our approach is successfully illustrated through several experiments on either real unipartite, multipartite or directed graphs of medium and large-sized datasets.
Document type :
Conference papers
Complete list of metadata

Contributor : Administrateur Imt - Mines Alès Connect in order to contact the contributor
Submitted on : Monday, February 21, 2022 - 3:10:39 PM
Last modification on : Wednesday, February 23, 2022 - 3:05:20 AM

Links full text




Michel Crampes, Michel Plantié. Overlapping Community Detection Optimization and Nash Equilibrium. WIMS '15 - 5th International Conference on Web Intelligence, Mining and Semantics, Jul 2015, Larnaca, Cyprus. pp.1-10, ⟨10.1145/2797115.2797131⟩. ⟨hal-03582932⟩



Record views