TY - CHAP

T1 - On connected two communities

AU - Estivill-Castro, V.

AU - Parsa, M.

PY - 2013

Y1 - 2013

N2 - We say that there is a community structure in a graph when the nodes of the graph can be partitioned into groups (communities) such that each group is internally more densely connected than with the rest of the graph. However, the challenge is to specify what is to be dense, and what is relatively more connected (there seems to exist an analogous situation to what is a cluster in unsupervized learning). Recently, Olsen (2012) provided a general definition that seemed to be significantly more generic that others. We make two observations regarding such definition. (1) First, we show that finding a community structure with two equal size communities is NP-complete (Uniform 2-Communities). The first implication of this is that finding a large community seems intractable. The second implication is that, since this is a hardness result for k = 2, the Uniform k-Communities problem is not fixed-parameter tractable when k is the parameter. (2) The second observation is that communities are not required to be connected in Olsen (2012)'s definition. However, we indicate that our result holds as well as the results by Olsen (2012) when we require communities to be connected, and we show examples where using connected communities seems more natural.

AB - We say that there is a community structure in a graph when the nodes of the graph can be partitioned into groups (communities) such that each group is internally more densely connected than with the rest of the graph. However, the challenge is to specify what is to be dense, and what is relatively more connected (there seems to exist an analogous situation to what is a cluster in unsupervized learning). Recently, Olsen (2012) provided a general definition that seemed to be significantly more generic that others. We make two observations regarding such definition. (1) First, we show that finding a community structure with two equal size communities is NP-complete (Uniform 2-Communities). The first implication of this is that finding a large community seems intractable. The second implication is that, since this is a hardness result for k = 2, the Uniform k-Communities problem is not fixed-parameter tractable when k is the parameter. (2) The second observation is that communities are not required to be connected in Olsen (2012)'s definition. However, we indicate that our result holds as well as the results by Olsen (2012) when we require communities to be connected, and we show examples where using connected communities seems more natural.

KW - community detection

KW - graph partitioning

KW - parameterized complexity theory

UR - http://acsw2013.cis.unisa.edu.au/

UR - http://crpit.com/confpapers/CRPITV135Estivill-Castro.pdf

UR - http://dl.acm.org/citation.cfm?id=2525404&CFID=545608526&CFTOKEN=59679928

M3 - Chapter (peer-reviewed)

SN - 978-1-921770-20-3

VL - 135

T3 - Conferences in Research and Practice in Information Technology

SP - 23

EP - 30

BT - ACSC '13 Proceedings of the Thirty-Sixth Australasian Computer Science Conference - Volume 135

A2 - Thomas, Bruce

CY - Adelaide, Australia

ER -