Finding Skilled and Cohesive Teams in Large Scale Social Networks

Suppose you are given a large scale social network where each node represents a person, and edges between nodes represent any type of social link between two persons. Edges can be undirected (e.g. representing mutual friendships) or directed (e.g. representing willingness to work with). Additionally, suppose that each person states a list of his or her skills (e.g. {python, user interaction design, machine learning}). In this work, we are interested in algorithmically forming a socially cohesive team having all of a given list of required skills with a given number of team members. We assume socially cohesive to mean that there exists a path in the social graph connecting any two members of the team, such that all the persons in the path are in the team (connectedness property).

This is a variant of the colorful subset problem, an NP-hard search task. We develop and benchmark an algorithm based on integer-linear programming and a few heuristics for solving this problem.