An improved game-theoretic approach to uncover overlapping communities

Hong Liang Sun, Eugene Ch'Ng, Xi Yong, Jonathan M. Garibaldi, Simon See, Duan Bing Chen

Research output: Journal PublicationArticlepeer-review

11 Citations (Scopus)

Abstract

How can we uncover overlapping communities from complex networks to understand the inherent structures and functions? Chen et al. firstly proposed a community game (Game) to study this problem, and the overlapping communities have been discovered when the game is convergent. It is based on the assumption that each vertex of the underlying network is a rational game player to maximize its utility. In this paper, we investigate how similar vertices affect the formation of community game. The Adamic-Adar Index (AA Index) has been employed to define the new utility function. This novel method has been evaluated on both synthetic and real-world networks. Experimental study shows that it has significant improvement of accuracy (from 4.8% to 37.6%) compared with the Game on 10 real networks. It is more efficient on Facebook networks (FN) and Amazon co-purchasing networks than on other networks. This result implicates that "friend circles of friends" of Facebook are valuable to understand the overlapping community division.

Original languageEnglish
Article number1750112
JournalInternational Journal of Modern Physics C
Volume28
Issue number9
DOIs
Publication statusPublished - 1 Sep 2017

Keywords

  • Overlapping community detection
  • complex networks
  • game theory

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Mathematical Physics
  • Physics and Astronomy (all)
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'An improved game-theoretic approach to uncover overlapping communities'. Together they form a unique fingerprint.

Cite this