PaperlayerView exact revision on arXiv

Source-linked AI summary

Capacitated Team Formation Problem on Social Networks

Samik Datta, Anirban Majumder, KVM Naidu

arXiv:1205.3643v1cs.SIphysics.soc-ph

TL;DR

The paper asks how to form effective collaborative teams on social networks when members must remain socially close while sharing work without exceeding individual capacities. It formulates this NP-hard problem, develops approximation algorithms with provable guarantees, and evaluates them on large-scale GitHub and DBLP data. The experiments show that the techniques outperform naive strategies, scale to hundreds of thousands of users, and improve the collaboration cost of existing GitHub teams.

  • Problem

    The paper studies how to select socially close team members and divide collaborative tasks without overloading any user.

  • Method

    The paper formulates capacity-constrained team formation on social networks and develops efficient approximation algorithms for its NP-hard variants.

  • Results

    The algorithms outperform naive strategies by a significant margin, with experiments reporting 20–40% improvement or cost reduction across real-world datasets.

  • Takeaways & Limitations

    The techniques provide a scalable approach for forming socially effective teams under capacity constraints and improve the collaboration cost of existing GitHub teams.

  • Takeaways & Limitations

    In approximately 5% of projects, the algorithms produced higher cost than the actual teams, which the authors attribute to imprecise input-parameter modeling.

Abstract

from arXiv · show

In a team formation problem, one is required to find a group of users that can match the requirements of a collaborative task. Example of such collaborative tasks abound, ranging from software product development to various participatory sensing tasks in knowledge creation. Due to the nature of the task, team members are often required to work on a co-operative basis. Previous studies have indicated that co-operation becomes effective in presence of social connections. Therefore, effective team selection requires the team members to be socially close as well as a division of the task among team members so that no user is overloaded by the assignment. In this work, we investigate how such teams can be formed on a social network. Since our team formation problems are proven to be NP-hard, we design efficient approximate algorithms for finding near optimum teams with provable guarantees. As traditional data-sets from on-line social networks (e.g. Twitter, Facebook etc) typically do not contain instances of large scale collaboration, we have crawled millions of software repositories spanning a period of four years and hundreds of thousands of developers from GitHub, a popular open-source social coding network. We perform large scale experiments on this data-set to evaluate the accuracy and efficiency of our algorithms. Experimental results suggest that our algorithms achieve significant improvement in finding effective teams, as compared to naive strategies and scale well with the size of the data. Finally, we provide a validation of our techniques by comparing with existing software teams in GitHub.

1. INTRODUCTION

The paper formulates team formation on social networks as selecting socially close users and dividing tasks without exceeding capacities. It introduces approximation algorithms and evaluates them on large-scale GitHub and DBLP data.

  • Problem formulation: The problem selects socially close users and assigns task portions so that no team member exceeds their capacity.This differs from traditional resource-allocation formulations that omit social-network information.
  • Novelty: Capacity constraints make this a novel team-formation problem that the authors identify as previously unstudied.The contribution explicitly combines social-network structure with user capacities.
  • Algorithms: Because the team-formation problems are NP-hard, the paper presents two efficient approximation algorithms with provable guarantees.The algorithms are also described as adaptable to important problem extensions.
  • Evaluation: The evaluation uses large-scale collaboration traces from hundreds of thousands of users and nearly a million software repositories collected from GitHub.The paper also includes experiments on the DBLP dataset to demonstrate generality.
  • Results: The algorithms achieve up to 40% cost reduction compared with other strategies and improve the collaboration cost of existing GitHub teams.The paper reports additional experiments on DBLP for generality.

2. TEAM FORMATION PROBLEM

The paper formulates capacitated team formation on weighted social networks: select socially close users and assign task items without exceeding capacities. It defines three collaboration-cost objectives and establishes hardness for two variants.

  • 2.1 Notation: Users are vertices in a weighted undirected social network, where edge costs represent collaboration difficulty and shortest paths extend costs to non-neighbors.
  • 2.1 Notation: Each user has skills I_v and capacity c_v, while a task is a set of required items assignable only to users possessing the corresponding skills.
  • 2.2 Feasibility Constraints: A feasible team must cover every task item with a valid skill-compatible assignment and obey each user's capacity limit.
  • 2.3 Social Collaboration Cost: The paper evaluates diameter, Steiner, and bottleneck collaboration costs, respectively limiting pairwise distance, aggregate connection cost, or the largest tree-edge cost.
  • 2.4 Problem Formulation: The team-formation problem selects users who join task initiator v so the resulting team is feasible while minimizing one of these social costs.
  • 2.4 Problem Formulation: The search can be restricted to users within a maximum hop length h, with common settings of 1, 2, or infinity hops.
  • 2.4 Problem Formulation: The formulation guarantees that the task initiator belongs to the team, although the algorithms can be adapted when this requirement is removed.
  • 2.5 Hardness Result: MinDiamTeam and MinAggrTeam are NP-hard, extending hardness results from the infinite-capacity specialization.

3. ALGORITHMS

The paper develops approximation algorithms for the NP-hard diameter and aggregate-cost variants, alongside feasibility procedures based on capacity-aware assignment and graph transformations.

  • The MinMaxTeam problem is polynomially solvable, unlike the two NP-hard variants addressed by approximation algorithms.
  • A maximum-flow network decides feasibility by assigning task-item nodes to skilled users without exceeding user capacities.A flow value of k certifies that all k task items can be assigned.
  • MinDiamSol finds the smallest radius around the initiating user whose reachable users can feasibly cover all task items.Feasibility is tested through maximum item assignment under user capacities.
  • 2-factor approximation: MinDiamSol achieves a 2-factor approximation for MinDiamTeam.
  • For MinDiamSol, binary search over graph diameter yields a worst-case complexity expressed using O(log n_h) feasibility calls, although practice is faster.
  • MinAggrSol transforms the social network into an augmented one-level graph, greedily selecting users by marginal coverage benefit per shortest-path cost.It then connects selected users using a minimum-cost Steiner tree.
  • O(k log k) factor: MinAggrSol approximates MinAggrTeam within a factor depending on the number k of required task items.The transformed graph's optimum cost is at most O(k) times the original optimum.
  • MinAggrSol has stated running time O(k^3 log k + n_hk^2 + m) before Steiner-tree computation, with additional O(m+n log n) time for that computation.

4. EXTENSIONS

The paper extends its framework to user prices and multi-unit task items by modifying graph costs and capacity-aware flow computations.

  • User prices are incorporated by minimizing a weighted combination αΣ_{u∈U}π_u + βf(U) of participation prices and social collaboration cost.
  • The price extension adds a priced auxiliary node for each user, scales original social-edge costs by β, and transfers skills and capacities to the auxiliary node.
  • For multi-unit tasks, each item i has multiplicity n_i, and users may receive multiple units subject to skill and total-capacity constraints.
  • The modified flow network assigns capacity n_i to item-related edges and certifies feasibility when maximum flow reaches Σ_{i∈T} n_i.
  • Under multi-unit demands, MinDiamSol retains a factor-2 approximation, while MinAggrSol has approximation ratio O(log kP).

5. EXPERIMENTS

The experiments use large GitHub collaboration data because conventional social-network datasets lack large-scale collaboration evidence. They examine dataset construction and the relationship between team social structure and project activity.

  • 5.1 Dataset: GitHub was selected for its explicit social links, richer API-accessible data, and rapid growth relative to alternative social coding sites.
  • 5.1 Dataset: The crawl collected users, projects, contributors, commit logs, bug reports, programming languages, followers, and project participation information.
  • 5.1 Dataset: Dataset D1 contains 1,35,346 users and 9,05,000 software projects for estimating algorithm parameters, while D2 contains 470 later projects for testing.
  • 5.2 Social Activity: Across 10k projects, teams with more social edges were more active, showing positive correlations between edge count and project commits across almost all team sizes.
  • 5.2 Social Activity: Teams with more connected components were less active, showing negative correlations between fragmentation and project commits across almost all team sizes.

5.3 Preprocessing

The preprocessing converts GitHub data into social-network, item, task, and capacity inputs for the team-formation algorithms. It also estimates collaboration cost from users’ prior co-work and uses activity logs to characterize capacities.

  • Social Network: GitHub’s social network is built from follower links treated as undirected, with relationship strength proportional to the fraction of shared projects.The collaboration cost is then defined as w(u, v) = 100 · (1 − σ_u,v).
  • Evaluation preparation: The preprocessing documentation notes that comparing commit counts across different team sizes would be unfair, so teams are grouped by size.
  • Items: The dataset represents items as 52 programming languages, with each user’s item set consisting of languages required by her projects.
  • Tasks: Tasks are project requirements from dataset D2, whose programming-language requirements are kept separate from parameter estimation to avoid bias.Additional synthetic requirements are generated from item cooccurrences rather than uniform random sampling.
  • Capacity: User capacities are estimated from one month of commit logs for approximately 2k active users and their listed projects.A project is counted as active for a user when she makes at least one commit during that month; active contributions are often fewer than listed projects.

5.4 Results

The experiments evaluate solution quality, scalability, and feasibility on GitHub and DBLP data. The proposed algorithms generally reduce collaboration cost and scale to large networks, while performance varies with task size and modeling conditions.

  • Comparison with existing GitHub teams: For nearly 40% of GitHub projects, MinDiamSol and MinAggrSol reduce collaboration cost by 10%−35% relative to the actual teams.For the remaining projects, improvements are minor, while approximately 5% have higher-cost algorithmic solutions.
  • Scalability: On networks of 135k nodes, MinMaxSol and MinDiamSol take approximately 30 seconds, whereas MinAggrSol takes nearly 6 minutes and scales almost linearly with network size.
  • Feasibility: At h = 3, the input tasks have feasible solutions, whereas GreedyDiam and GreedySteiner require h = 5; experiments therefore use h = 5 thereafter.
  • Comparison with Baseline: MinDiamSol reduces real-task cost by at least 25% versus GreedyDiam, while its steiner-cost improvement over GreedySteiner is at least 40%.The text attributes GreedySteiner’s higher cost to ignoring user capacities and adding many steiner nodes.
  • Comparison with Baseline: On synthetic tasks, the algorithms achieve a 30% cost reduction, with comparable performance for three-skill tasks and larger gains for larger tasks.
  • Feasibility: MinDiamSol returns disconnected teams for 18% of tasks, while GreedySteiner returns disconnected teams substantially more often than MinAggrSol.MinDiamSol and GreedyDiam return approximately the same fraction of disconnected teams.

5.5 Experiments on DBLP data

The DBLP experiments evaluate the algorithms on a co-authorship-derived social network with capacity estimates based on publication activity. The proposed methods improve over baseline heuristics, though gains are smaller than on GitHub because DBLP is denser and has higher-capacity users.

  • Dataset construction: Authors’ capacities are estimated as their average number of co-authored publications per year.
  • Dataset construction: The DBLP social network is generated from co-authorship, with edge costs estimated from authors’ article-set overlap.The cost is scaled by an arbitrary factor of 100 to avoid rounding errors.
  • Results: MinDiamSol and MinAggrSol achieve approximately 20% improvement over the baseline heuristics.Because DBLP is slightly denser than GitHub, baseline algorithms find feasible teams within four hops, so h is set to 4.
  • Results: The denser DBLP network and users with larger capacities slightly reduce the gains relative to the GitHub experiments.

6. RELATED WORK

Prior work addresses team selection through task allocation, social proximity, load balance, or bounded collaboration cost, but differs from this paper’s capacitated social-network formulation. The paper positions capacity constraints as a structural distinction from existing approaches.

  • Operations Research: Operations Research team-selection methods allocate tasks to satisfy project requirements but ignore social relationships among users.The paper states that these techniques cannot be applied directly to its problem.
  • Social-network team formation: Lappas et al. minimize communication cost for expert teams on social networks but do not model user capacities.Their formulation is characterized as an uncapacitated version of this problem.
  • Load balance: Load-balancing work considers the number of projects assigned to individuals but overlooks social collaboration cost.
  • Load balance: Anagnostopoulos et al. combine load balance with bounded social collaboration cost, but their formulation differs from the one studied here.
  • Scope: Methods for estimating relationship strength are treated as an orthogonal research direction beyond this paper’s scope.

7. CONCLUSION

The paper presents a capacitated team-formation problem on social networks and algorithms for multiple social-collaboration models. Experiments on real-life datasets show that these techniques outperform naive strategies by a significant margin.

  • Contribution: The proposed problem jointly seeks socially close teams and task divisions that prevent users from being overloaded.
  • Contribution: The paper presents algorithms for the problem under different models of social collaboration and analyzes their performance.
  • Empirical findings: Experiments with real-life datasets show that the techniques outperform naive strategies by a significant margin.

A. PROOF OF LEMMA 4

The proof establishes submodularity of MaxItems by combining its monotonicity with an inequality over arbitrary user subsets. It first handles disjoint subsets, then extends the argument to overlapping subsets.

  • Monotonicity: MaxItems is monotone because enlarging the user set cannot decrease the maximum number of assignable items.
  • Disjoint subsets: For disjoint subsets A and B, the proof bounds assigned items by MaxItems(A) and MaxItems(B), while MaxItems(A ∩ B) equals zero.
  • Overlapping subsets: For arbitrary subsets, the proof writes MaxItems(A ∪ B) as nA + nB − nA∩B and applies analogous bounds.
  • Overlapping subsets: The remaining step is to show that an allocation for A ∪ B can attain MaxItems(A ∩ B) on the intersection.
Loading 1205.3643v1…