Finding endogenously formed communities

Maria Florina Balcan, Christian Borgs, Mark Braverman, Jennifer Chayes, Shang Hua Teng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Scopus citations


A central problem in data mining and social network analysis is determining overlapping communities (clusters) among individuals or objects in the absence of external identification or tagging. We address this problem by introducing a framework that captures the notion of communities or clusters determined by the relative affinities among their members. To this end we define what we call an affinity system, which is a set of elements, each with a vector characterizing its preference for all other elements in the set. We define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are endogenously formed in the affinity system and are "self-determined" or "self- certified" by its members. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. We present a polynomial-time algorithm for enumerating these communities. Moreover, we obtain a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community (as opposed to the size of the network). Social networks and social interactions fit particularly naturally within the affinity system framework - if we can appropriately extract the affinities from the relatively sparse yet rich information from social networks and social interactions, our analysis then yields a set of efficient algorithms for enumerating self-determined communities in social networks. In the context of social networks we also connect our analysis with results about (α, β)-clusters introduced by Mishra, Schreiber, Stanton, and Tarjan [22, 23]. In contrast with the polynomial bound we prove on the number of communities in the affinity system model, we show that there exists a family of networks with superpolynomial number of (α, β)-clusters.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
PublisherAssociation for Computing Machinery
Number of pages17
ISBN (Print)9781611972511
StatePublished - 2013
Event24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 - New Orleans, LA, United States
Duration: Jan 6 2013Jan 8 2013

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Country/TerritoryUnited States
CityNew Orleans, LA

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Finding endogenously formed communities'. Together they form a unique fingerprint.

Cite this