Discovering Top-k Teams: Moving Beyond Diameter in Social Networks

TL;DR

Building an effective project team isn't just about finding people with the right skills; it's about ensuring they can actually talk to each other. This paper moves past simple metrics like "Diameter" and "MST" to propose Sum of Distances (for peer-to-peer collaboration) and Leader Distance (for managed projects). It provides a 2-approximation algorithm for the former and an exact solution for the latter, significantly outperforming previous SOTA in both communication efficiency and expertise quality.

Background: Why Connectivity Matters

In any social network (like DBLP for researchers or IMDb for actors), the "distance" between experts represents the friction of collaboration. Previous research suggested minimizing the Diameter (the longest path in a team) or the MST (the minimum skeleton to connect everyone).

However, the authors argue these are unstable. A single edge change can radically shift an MST, and Diameter only focuses on the two most "distant" people, ignoring the collaboration overhead between everyone else.

The Core Methodology: Two New Perspectives

The paper introduces two distinct communication structures:

1. Peer-to-Peer (Sum of Distances): If every skill holder ($s_i$) needs to coordinate with every other skill holder ($s_j$), the cost is the sum of all pairwise shortest paths. This is NP-hard, but the authors prove a greedy "nearest neighbor" search yields a 2-approximation.
2. Hierarchical (Leader Distance): If a project has a leader $L$, the cost is the sum of distances from $L$ to each skill holder. Surprisingly, finding the optimal team and leader is solvable in polynomial time by iterating through all potential leaders in the graph.

Figure 1: Illustration of teams for a project requiring skills {a, b, c, d}. The "Sum of Distances" captures total coordination volume better than Diameter.

The Top-k Algorithm

Real-world users rarely want just one answer. The authors adapted Lawler’s procedure to partition the search space into disjoint subspaces, allowing the system to output the "Top-k" best teams with polynomial delay. This ensures that the time between outputting the $i$-th and $(i+1)$-th team remains small and constant relative to the graph size.

Experimental Proof

The researchers tested their approach on DBLP (computer science authors) and IMDb (actors).

Performance on Communication Costs

The "Best-SumDistance" and "Best-Leader" algorithms didn't just win on their own metrics; they actually produced lower Diameter and MST costs than the algorithms specifically designed to minimize them (Rarest-First and Enhanced-Steiner).

Figure 2: Performance comparison on DBLP. Our proposed algorithms (Best-SumDistance and Best-Leader) consistently stay closer to the "Exact" optimal ground truth.

Qualitative Edge

Beyond math, the teams were objectively "better" in a professional sense:

• Smaller Cardinality: They found "multi-talented" groups that covered all skills with fewer people.
• Higher Expertise: The team members had a higher "Skill Count" (frequency of those skills in their history).
• Proven Collaboration: Teams had significantly more common publications (3 vs 0 in some cases), indicating they had successfully worked together before.

Critical Insight & Conclusion

The biggest takeaway is the robustness of the Sum of Distances metric. By trying to minimize the total communication "volume," the algorithm naturally gravitates toward dense, highly-collaborative clusters in the social graph. Unlike the Diameter metric, which is easily skewed by outliers, Sum of Distances provides a holistic view of team harmony.

Limitations: While powerful, the current model assumes edge weights are static and shortest paths are always the preferred way to communicate. In the real world, an expert's "load" (how many projects they are already on) might be just as important as their distance to a teammate.

Future Work: Incorporating constraints such as expert availability, capacity, and diverse skill proficiency levels will be the next frontier in automated team synthesis.