Discovering the "Staring People": Balancing Authority and Sociality in Networks

TL;DR

In the era of Web 2.0, identifying "Stars"—people who aren't just experts but are also social hubs—is critical. This paper from Tsinghua University formalizes the Staring People Discovery problem, treating it as an optimization task. By applying Genetic Algorithms to co-author networks, the researchers achieved nearly 90% precision in identifying researchers who are both prolific and well-connected.

Background & Motivation: Beyond Simple Expertise

Why do we need a new definition for "Stars"?

• Expert Finding models usually stop at "who knows the most about topic X."
• Graph Summarization focuses on reducing graph size while preserving topology.

The authors argue that a "Star" must bridge these worlds. In a co-author network, a star isn't just someone with 100 papers; they must be accessible ("socially close") to others and active in their collaborations. The core challenge is: how do we mathematically define "Representative Power" in a social graph?

Methodology: The Optimization Framework

The researchers transform the discovery process into a bitwise vector optimization problem $(x_1,x_2,\dots )$, where $x_i=1$ denotes a selected Star. They propose three core rules translated into objective functions ($f_1,f_2,f_3$):

1. Cardinality ($f_1$): Ensures the number of stars matches a predefined ratio $\alpha$.
2. Proximity/Sociality ($f_2$): Minimizes the distance between "normal" people and their nearest "Star."
3. Authority & Preference ($f_3$): Mathematically enforces that people with more publications ($n$) or higher collaboration frequency ($c$) are prioritized.

Architecture: Solving the Program

The paper explores two ways to combine these objectives:

• Multi-Objective Programming (MOP): A weighted sum approach ($\sum {\lambda }_i{f}_i$).
• Multilevel Programming (MLP): A hierarchical approach where objectives are solved one by one according to priority.

Figure 1: Visual representation of a co-author network where "Staring Authors" (red nodes) are identified based on their local influence and connectivity.

To solve these NP-hard combinations, the authors utilize a Genetic Algorithm with bitwise encoding, allowing the system to evolve toward an optimal subset of stars.

Experiments & Results

The study used a robust dataset: 308 graphs generated from major CS conferences (SIGKDD, SIGMOD, VLDB) between 2003 and 2008. Ground truth was established through manual annotation by Ph.D. students.

Performance Comparison

The results clearly favor the MLP approach over MOP, suggesting that a strict hierarchy of rules better captures the nature of "stardom" than a simple weighted average.

Deep Insight & Conclusion

The "Staring People" discovery problem is a precursor to modern influence maximization and key opinion leader (KOL) identification.

• Why it works: By minimizing the distance between non-stars and stars ($f_2$), the model ensures that the selected nodes are geographically central in the network manifold, not just isolated "ivory tower" experts.
• Limitations: The Genetic Algorithm, while effective for 2009-scale graphs, may face scalability issues with today's million-node social networks. Modern implementations would likely require heuristic approximations or localized graph embeddings.
• Future Impact: This framework is highly generalizable. Beyond co-authorship, it can identify "staring" bloggers in the blogosphere or essential survey papers that act as hubs in citation networks.