Overlapping Community Detection Optimization and Nash Equilibrium

Autor:	Crampes, Michel, Plantié, Michel
Rok vydání:	2014
Předmět:	Computer Science - Social and Information Networks Physics - Physics and Society Statistics - Machine Learning
Druh dokumentu:	Working Paper
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. Comment: Submitted to KDD
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1406.6832 Zobrazit plný text záznamu View this record from Arxiv