Title: Finding low-tension communities,
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.