Towards multi-ego-centered communities: a node similarity approach


M. Danisch, J.-L. Guillaume and B. Le Grand

Int. J. of Web Based Communities, Vol. 9, No. 3, pp. 299-322, 2012


The community structure of a graph is defined in various ways in the literature:

(i) Partition, where nodes can belong to only one community. This vision is unrealistic and may lead to poor results because most nodes belong to several communities in real-world networks.

(ii) Overlapping community structure, which is the most natural view, but is often very difficult to identify in practice due to the complex structure of real-world networks, and the huge number of such possible communities.

(iii) Ego-centered community which focuses on individual nodes' communities and seems to be a good compromise.

In this paper we investigate the third vision; we propose a new similarity measure between nodes based on opinion dynamics to unfold ego-centered communities. We call it the carryover opinion. In addition to be parameter-free, the carryover opinion can be calculated in a very time-efficient way and can thus be used in huge graphs.

We also go further in the idea of ego-centered communities by introducing the new concept of multi-ego-centered communities, i.e., focusing on the communities of a set of nodes rather than of a single node. A key idea is that, although one node generally belongs to numerous communities, a small set of appropriate nodes can fully characterize a single community.

This entry was posted in Papers and tagged , , ,