A general view on computing communities

Martin Olsen

Mathematical Social Sciences, 2013, vol. 66, issue 3, 331-336

Abstract: We define a community structure of a graph as a partition of the vertices into at least two sets with the property that each vertex has connections to relatively many vertices in its own set compared to any other set in the partition and 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 vertices. On the other hand, we show how to compute a community structure in polynomial time for any connected graph containing at least four vertices except the star graph Sn. Finally, we generalize our results and formally show that counterintuitive aspects are unavoidable for any definition of a community structure with a polynomial time algorithm for computing communities containing specific vertices.

Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489613000668
Full text for ScienceDirect subscribers only

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:eee:matsoc:v:66:y:2013:i:3:p:331-336

DOI: 10.1016/j.mathsocsci.2013.07.002

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().