Finding low-tension communities

Esther Galbrun, Behzad Golshan, Aristides Gionis, Evimaria Terzi

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Citations (Scopus)
104 Downloads (Pure)


Motivated by applications that arise in online social media and collaboration networks, there has been a lot of work on community-search. In this class of problems, the goal is to find a subgraph that satisfies a certain connectivity requirement and contains a given collection of seed nodes. In this paper, we extend the community-search problem by associating each individual with a profile. The profile is a numeric score that quantifies the position of an individual with respect to a topic. We adopt a model where each individual starts with a latent profile and arrives to a conformed profile through a dynamic conformation process, which takes into account the individual's social interaction and the tendency to conform with one's social environment. In this framework, social tension arises from the differences between the conformed profiles of neighboring individuals as well as from the differences between individuals' conformed and latent profiles. Given a network of individuals, their latent profiles and this conformation process, we extend the community- search problem by requiring the output subgraphs to have low social tension. From the technical point of view, we study the complexity of this problem and propose algorithms for solving it effectively. Our experimental evaluation in a number of social networks reveals the efficacy and efficiency of our methods.
Original languageEnglish
Title of host publicationProceedings of the 17th SIAM International Conference on Data Mining, SDM 2017
EditorsNitesh Chawla, Wei Wang
Number of pages9
ISBN (Electronic)978-1-611974-87-4
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventSIAM International Conference on Data Mining - Houston, United States
Duration: 27 Apr 201729 Apr 2017
Conference number: 17

Publication series

NameProceedings of the SIAM International Conference on Data Mining
PublisherSociety for Industrial and Applied Mathematics (SIAM)
ISSN (Electronic)2167-0099


ConferenceSIAM International Conference on Data Mining
Abbreviated titleSDM
Country/TerritoryUnited States


Dive into the research topics of 'Finding low-tension communities'. Together they form a unique fingerprint.

Cite this