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