An Incremental Approach for Identifying Communities in Dynamic Social Networks Based on Coalition Formation Game Theory

Lihua Zhou and Kevin Lu
Additional contact information
Lihua Zhou: Yunnan University, China
Kevin Lu: Brunel University, United Kingdom

from ToKnowPress

Abstract: Community detection is a fundamental task in network analysis. Approaches for detecting communities have largely focused on identifying communities in static networks. However, most real-world social networks are usually dynamic (evolve over time), thus communities are constantly changing in memberships and topology structures. Applications on massive dynamic networks require more efficient solutions and lead to incremental community detection, which revises the community assignments of new or changed nodes during network updates. In this paper, we propose an incremental approach based on the coalition formation game theory to identify communities in dynamic social networks. We represent a dynamic network as a sequence of network snapshots evolving over time, and model the community evolution as the problem of transformations of stable coalition structures. We propose and prove the conditions needed for the existence of an approximate Dc-stable coalition structure, analyze how a community structure is affected by changes of a network, and introduce algorithms for updating coalitions. The proposed algorithms adaptively update network communities from the previous known structures and the change of topological structures of networks, rather than re-computing in the snapshots network at different time steps, such that the computational cost and processing time can be significantly reduced. Furthermore, this incremental manner naturally traces the evolution of community structure over time. Extensive experiments have been conducted to evaluate the effectiveness and efficiency of the proposed approach.

Keywords: Dynamic social network; incremental community detection; coalition formation game theory; approximate Dc-stable partitioning (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.toknowpress.net/ISBN/978-961-6914-23-9/papers/ML2018-134.pdf full text (application/pdf)
http://www.toknowpress.net/ISBN/978-961-6914-23-9/MakeLearn2018.pdf Conference Programme (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:tkp:mklp18:525

Access Statistics for this chapter

More chapters in Integrated Economy and Society: Diversity, Creativity and Technology; Proceedings of the MakeLearn and TIIM International Conference 2018 from ToKnowPress
Bibliographic data for series maintained by Miha Jezovnik ().