[ICDE] Anchored Vertex Exploration: Maximizing Community Engagement via Interest and Structure

TL;DR

To prevent social network decay, simply looking at "who follows whom" isn't enough. This paper introduces Anchored Vertex Exploration (AVE), a method to find the most influential "anchor" users who can bring the maximum number of interested followers into a cohesive, keyword-specific community. By combining k-core structural constraints with keyword filtering and a high-performance KAF Index, the authors provide a scalable solution for targeted marketing and crowdfunding.

Background: Beyond Simple K-Core

In social network analysis, a k-core represents a group where every member has at least $k$ neighbors. However, a person joins a community not just because their friends are there, but because the community talks about something they care about (keywords). Previous "anchoring" research focused on structure alone. This work argues that an "attributed community"—one that shares a specific interest—is the true engine of engagement.

The Challenge: NP-Hardness and Non-Submodularity

The AVE problem asks: Given a budget $l$, which $l$ users should we "anchor" (give special status) to maximize the final community size? This is harder than standard community search because:

1. Complexity: It is NP-hard once $k\ge 3$.
2. No Diminishing Returns: Unlike many optimization problems, AVE is not submodular. Adding one anchor might suddenly bridge two large clusters, causing an exponential jump in community size, which breaks simple greedy algorithms.

Methodology: The Filter-Verify Framework

The authors propose a multi-stage approach to find these anchors without checking every possible combination of users.

1. The Multiway Tree (M-tree) & KAF Index

The core innovation is the Keyword-aware Anchored & Followers (KAF) Index. It pre-calculates how a node's "core number" (its structural depth) changes if its neighbor becomes an anchor.

Figure: The CL-tree index used to manage attributed communities.

2. Pruning and Bounds

To manage the search space, the authors utilize a "Filter-Verify" framework:

• Candidate Pruning: If a node $u$ is already a follower of another node $v$, it is useless to anchor $u$ because $v$ already brings it into the fold for free.
• Upper/Lower Bounds: By calculating the theoretical maximum and minimum size an anchor set can induce, the algorithm can "short-circuit" and skip thousands of unpromising candidates.

Experimental Validation

The authors tested their method (FVA-A) against several baselines on datasets like DBLP and Tencent.

Efficiency and Scalability

While baseline algorithms (FVA-B) failed to complete on the Tencent dataset (1.1M vertices), the optimized FVA-A algorithm finished in reasonable time, proving the effectiveness of the pruning rules.

Figure: Efficiency comparison across different keyword sizes (Qw). FVA-A consistently outperforms baselines by orders of magnitude.

Effectiveness: Real-World Engagement

Using historical data from citation networks (GrQc and HepTh), the authors showed that:

1. Followers Stay: Nodes identified as "followers" by AVE were significantly more likely to actually appear in the community in future time steps compared to random nodes.
2. Higher Cohesion: Attributed communities anchored by this method had smaller diameters (better "cohesiveness") than traditional k-cores.

Deep Insight & Conclusion

The AVE approach moves community engagement from a "topology-first" perspective to a "user-centric" one. By proving that interest-based followers are more "loyal" to a community structure, the paper provides a roadmap for platform owners to identify key individuals who serve as structural and topical glue.

Limitations: The current model assumes keywords are static. In real-world scenarios, interests shift over time. Future work could integrate "keyword evolution" to see how anchors lose or gain influence as trends change.