Finding low-tension communities
Files
First author draft
Date
2017-11-06
Authors
Galbrun, Esther
Gionis, Aristides
Golshan, Behzad
Terzi, Evimaria
Version
First author draft
OA Version
Citation
Esther Galbrun, Aristides Gionis, Behzad Golshan, Evimaria Terzi. 2017. "Finding low-tension communities." Proceedings of the 2017 SIAM International Conference on Data Mining. pp. 336-344.
Abstract
Motivated by applications that arise in online social media and collaboration networks, there has been a lot of work on community-search and team-formation problems. In the former 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 the latter class of problems, on the other hand, the goal is to find individuals who collectively have the skills required for a task and form a connected subgraph with certain properties.
In this paper, we extend both the community-search and the team-formation problems 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 differences between individuals' conformed and latent profiles.
Given a network of individuals, their latent profiles and this conformation process, we extend the community-search and the team-formation problems by requiring the output subgraphs to have low social tension. From the technical point of view, we study the complexity of these problems and propose algorithms for solving them effectively. Our experimental evaluation in a number of social networks reveals the efficacy and efficiency of our methods.
Description
A short version of this paper appeared in the 2017 SIAM International Conference on Data Mining, SDM'17. In this extended version, we discuss the team-formation problem variant, beside the original community-search problem, and include additional experimental results