InfraSky: Geometric Pruning for Rapid Star Discovery in Social Networks

TL;DR

In social networks, "stars" are nodes that dominate others in terms of influence (indegree) and activity (outdegree). This paper tackles the Member Promotion problem: how can we turn a regular user into a "star" with the fewest possible new connections? By introducing the Infra-skyline and Promotion Boundary, the authors transform a complex graph search problem into a 2D geometric optimization, achieving speedups of several orders of magnitude over previous SOTA methods.

Problem & Motivation: The Cost of Being Important

In any Social Network (SN), importance is rarely a single metric. A "star" must be both authoritative (high indegree) and a hub of information spreading (high outdegree). Mathematically, these influential users sit on the Skyline—the set of points that are not "dominated" by any other node in both dimensions.

The challenge arises when we want to promote a non-star member. While we can add edges to increase their degrees, the number of possible "promotion plans" is staggering. Previous attempts, such as the Index-based Dynamic Pruning (IDP) algorithm, fail to scale because they rely on checking dominance relationships that shift every time an edge is added. In large, sparse networks, these methods become computationally "intolerable."

Methodology: The Geometry of Promotion

The core insight of this paper is that the promotion process is essentially a shift of a point in a 2D coordinate system (Indegree vs. Outdegree) toward a specific contour.

1. The Infra-Skyline and Promotion Boundary

Instead of checking every node, the authors focus on the Infra-skyline—the skyline formed exclusively by the "best of the rest" (non-skyline members). They define a Promotion Boundary, a piecewise linear path that separates the current stars from the candidates.

2. The InfraSky Algorithm

The algorithm projects the problem into a Cartesian space:

• Pruning: Theoretical proofs show that only nodes on the Infra-skyline or the Boundary are eligible for "optimal" promotion. This eliminates the vast majority of nodes immediately.
• Calculation: Rather than simulating graph changes, the algorithm calculates the $L_1$ distance (Manhattan distance) to the boundary.

Fig 1: The geometric interpretation of the Promotion Boundary and Infra-skyline.

Experiments: Breaking the Complexity Barrier

The authors tested InfraSky against brute-force and IDP algorithms using the wiki-Vote dataset and synthetic Power-law graphs.

Performance Breakthrough

The results were binary: either you use InfraSky, or you wait hours.

• Scale: At 7,000 nodes, InfraSky finishes in sub-400ms.
• Comparison: When the network reached 2,000 nodes, the status-quo IDP algorithm took 10+ minutes, while InfraSky stayed well under a tenth of a second (78ms).

Fig 2: Time cost comparison on wiki-Vote dataset showing the exponential growth of IDP vs the linear/polynomial stability of InfraSky.

Quality of Promotion

Beyond speed, the algorithm proves that "randomly adding edges" to become a star is highly inefficient. On the wiki-Vote dataset, random promotion often required 13+ edges, whereas InfraSky found paths requiring only 1 edge to reach the status of a "Potential Star."

Critical Analysis & Conclusion

The InfraSky algorithm effectively settles the member promotion problem for equal-weighted networks. By using geometric boundaries, it bypasses the "re-calculation trap" that plagues graph-based pruning.

Limitations: Currently, the model assumes all edges have a weight of 1 (equal cost). In real-world marketing, the cost to connect with a celebrity is much higher than connecting with a peer.

Future Outlook: The next logical step is extending this to Arbitrary Weights and Concurrent Promotion (promoting a group of people at once). If you're building a recommendation engine or an influencer marketing platform, the concept of a "Promotion Boundary" is a powerful tool for visualising and optimizing user growth.

Takeaway: Complexity isn't always inherent to the data; sometimes, it's a by-product of the perspective. Moving from a Graph perspective to a Geometric perspective turned an NP-hard-looking problem into a millisecond-level query.