Overlapping Community Detection Optimization and Nash Equilibrium
| Autor: | Michel Plantié, Michel Crampes |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Social and Information Networks (cs.SI)
FOS: Computer and information sciences Physics - Physics and Society Modularity (networks) Mathematical optimization Computer science FOS: Physical sciences Machine Learning (stat.ML) Computer Science - Social and Information Networks Physics and Society (physics.soc-ph) Function (mathematics) Directed graph Visualization Multipartite symbols.namesake Statistics - Machine Learning Nash equilibrium symbols Heuristics Focus (optics) |
| Zdroj: | WIMS |
| DOI: | 10.1145/2797115.2797131 |
| Popis: | 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. Submitted to KDD |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|