Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach

Details Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach

2011-12-08

arxiv.org/abs/1112.1831v1

Computer Science

Social and Information Networks

19 pages

Scientific paper

A "community" in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. This is an important concept in most domains where networks arise: social, technological, biological, etc. For many years algorithms for finding communities implicitly assumed communities are nonoverlapping (leading to use of clustering-based approaches) but there is increasing interest in finding overlapping communities. A barrier to finding communities is that the solution concept is often defined in terms of an NP-complete problem such as Clique or Hierarchical Clustering. This paper seeks to initiate a rigorous approach to the problem of finding overlapping communities, where "rigorous" means that we clearly state the following: (a) the object sought by our algorithm (b) the assumptions about the underlying network (c) the (worst-case) running time. Our assumptions about the network lie between worst-case and average-case. An average case analysis would require a precise probabilistic model of the network, on which there is currently no consensus. However, some plausible assumptions about network parameters can be gleaned from a long body of work in the sociology community spanning five decades focusing on the study of individual communities and ego-centric networks. Thus our assumptions are somewhat "local" in nature. Nevertheless they suffice to permit a rigorous analysis of running time of algorithms that recover global structure. Our algorithms use random sampling similar to that in property testing and algorithms for dense graphs. However, our networks are not necessarily dense graphs, not even in local neighborhoods. Our algorithms explore a local-global relationship between ego-centric and socio-centric networks that we hope will provide a fruitful framework for future work both in computer science and sociology.

Affiliated with

Also associated with

No associations

Rating

Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-547967