On Defining and Computing Communities

Oslen, M.

Inspired by the planted l-partition model, the hierarchical random graph model and observations on real networks we define a community structure of a graph as a partition of the nodes into at least two sets with the property that each node has connections to relatively many nodes in its own set compared to any other set in the partition. We refer to the sets in such a partition as communities. We show that it is NP-hard to compute a community containing a given set of nodes. On the other hand, we show how to compute a community structure in polynomial time for any connected graph containing at least four nodes except the star graph Sn.

Cite as: Oslen, M. (2012). On Defining and Computing Communities. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 97-102

(from crpit.com) (local if available)