SOCIAL NETWORKS COMMUNITY DETECTION USING THE SHAPLEY VALUE

10.22099/ijste.2013.1760

Abstract

As a result of the increasing popularity of social networking websites like Facebook
and Twitter, analysis of the structure of these networks has received significant attention. The most
important part of these analyses is towards detecting communities. The aforementioned structures
are usually known with extremely high inter-connections versus few intra-connections in the
graphs. In this paper, in spite of most approaches being optimization based, we have addressed the
community detection problem (CDP) by a novel framework based on Information Diffusion
Model and Shapley Value Concept. Here, each node of the underlying graph is attributed to a
rational agent trying to maximize its Shapley Value in the form of information it receives. Nash
equilibrium of the game corresponds to the community structure of the graph. Compared with the
other methods, our approach demonstrates promising results on the well-known real world and
synthetic graphs.

Keywords