Overlapping Community Detection Optimization and Nash Equilibrium
This work addresses the challenge of finding optimal community structures in social networks, which is incremental as it builds on existing modularity optimization methods.
The paper tackles the NP-complete problem of community detection in graphs by introducing a new algorithm that uses a potential function to optimize solutions and ensure they reach a Nash Equilibrium, successfully demonstrating its effectiveness on real datasets of various types and sizes.
Community detection using both graphs and 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 partitioning and overlapping communities, two detection and visualization modes of great value in revealing interesting features of 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.