Overlapping Community Detection Optimization and Nash Equilibrium
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Systemic Risk Models for Disjoint and Overlapping Groups with Equilibrium Strategies
We analyze the systemic risk for disjoint and overlapping groups (e.g., central clearing counterparties (CCP)) by proposing new models with realistic game features. Specifically, we generalize the systemic risk measure p…
Optimisation dans la détection de communautés recouvrantes et équilibre de Nash
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-communit…
Community DetectionAttacking and Securing Community Detection: A Game-Theoretic Framework
It has been demonstrated that adversarial graphs, i.e., graphs with imperceptible perturbations, can cause deep graph models to fail on classification tasks. In this work, we extend the concept of adversarial graphs to t…
Community DetectionGANs May Have No Nash Equilibria
Generative adversarial networks (GANs) represent a zero-sum game between two machine players, a generator and a discriminator, designed to learn the distribution of data. While GANs have achieved state-of-the-art perform…
Differentiable Arbitrating in Zero-sum Markov Games
We initiate the study of how to perturb the reward in a zero-sum Markov game with two players to induce a desirable Nash equilibrium, namely arbitrating. Such a problem admits a bi-level optimization formulation. The low…
Multi-agent Reinforcement Learningreinforcement-learningReinforcement Learning (RL)