Community Detection in Social Networks through Community Formation Games

Chen, Wei; Liu, Zhenming; Sun, Xiaorui; Wang, Yajun

doi:10.5591/978-1-57735-516-8/IJCAI11-429

Community Detection in Social Networks through Community Formation Games

Wei Chen, Zhenming Liu, Xiaorui Sun, Yajun Wang

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2576-2580.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-429

Abstract

We introduce a game-theoretic framework to address the community detection problem based on the social networks’ structure. The dynamics of community formation is framed as a strategic game called community formation game: Given a social network, each node is selfish and selects communities to join or leave based on her own utility measurement. A community structure can be interpreted as an equilibrium of this game. We formulate the agents’ utility by the combination of a gain function and a loss function. Each agent can select multiple communities, which naturally captures the concept of “overlapping communities”. We propose a gain function based on Newman’s modularity function and a simple loss function that reflects the intrinsic costs incurred when people join the communities. We conduct extensive experiments under this framework; our results show that our algorithm is effective in identifying overlapping communities, and is often better than other algorithms we evaluated especially when many people belong to multiple communities.

Wei Chen, Zhenming Liu, Xiaorui Sun, and Yajun Wang. 2011. Community Detection in Social Networks through Community Formation Games. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2576–2580. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-429

@inproceedings{ijcai2011p429,
  title     = {Community Detection in Social Networks through Community Formation Games},
  author    = {Chen, Wei and Liu, Zhenming and Sun, Xiaorui and Wang, Yajun},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2576--2580},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-429},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-429},
}

TY  - CPAPER
TI  - Community Detection in Social Networks through Community Formation Games
AU  - Chen, Wei
AU  - Liu, Zhenming
AU  - Sun, Xiaorui
AU  - Wang, Yajun
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2576
EP  - 2580
DO  - 10.5591/978-1-57735-516-8/IJCAI11-429
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-429
ER  -