Introduction
In graph mining, identifying cohesive groups of nodes is a fundamental task known as community search. Traditional approaches typically focus on topological constraints, such as the $k$-core—a subgraph where every member maintains at least $k$ connections within the group. However, real-world applications often require these communities to be not just well-connected, but also "influential." This paper explores the challenge of finding the top-$r$ influential communities by incorporating node weights (influence) and flexible aggregation functions.
The Limitation of Minimum Influence
Previous research in influential community search primarily defined a group's influence based on its "weakest link"—the minimum influence value among its members. While computationally efficient, this approach is often too restrictive. For instance, when assembling a high-performance research team or a marketing cohort, the total expertise (sum) or the average impact (avg) of the group is often more relevant than the score of the least influential member.
Furthermore, existing models frequently lack the ability to impose size constraints ($|H| \le s$). In practice, users often need to find the most influential community within a specific size limit. The authors demonstrate that while the min function is solvable in polynomial time, moving to sum with size constraints or avg functions shifts the problem into the realm of NP-hardness.
Methodology
The authors categorize the problem based on the mathematical properties of the chosen aggregation function:
1. Polynomial-Time Functions
Functions like min and unconstrained sum can be solved relatively efficiently. For the sum function without size limits, the authors developed TIC-IMPROVED. This algorithm utilizes a lower-bound pruning technique to skip large portions of the graph that cannot possibly contribute to a top-$r$ result, significantly reducing the search space.
2. NP-Hard Functions and Size Constraints
When the goal is to maximize the average influence or to find a sum-based community under a size constraint, the search space becomes computationally explosive. To address this, the authors propose a suite of heuristic solutions:
- Hardness Analysis: The paper provides formal proofs establishing that finding top-$r$ communities under
avgor size-constrained functions is NP-hard. - Local Search Heuristics: Recognizing that influential communities often have small diameters, the LOCALSEARCH algorithm limits its exploration to the $s$-nearest neighbors of individual nodes. This makes the search tractable even on massive graphs.
- Greedy Strategies: Within these local neighborhoods, the authors employ
SumStrategyandAvgStrategyto iteratively construct a $k$-core that maximizes the target influence function while respecting the size limit.
Experimental Evaluation
The researchers evaluated their algorithms on six large-scale real-world datasets from the Stanford Network Analysis Platform (SNAP), including Email-EuAll, DBLP, and the massive FriendSter network (containing over 65 million vertices and 1.8 billion edges). Node influence was modeled using PageRank values.
Key Findings
- Scalability: On the FriendSter graph, the
TIC-IMPROVEDalgorithm demonstrated remarkable efficiency, completing tasks in seconds that would take hours using naive methods. - Search Effectiveness: In size-constrained scenarios, the
Greedylocal search consistently outperformed random search baselines, identifying communities with significantly higher collective influence. - Monotonicity vs. Non-Monotonicity: The authors highlight that
sumis a monotonic function (adding a positive weight node always increases the total), allowing for effective pruning. In contrast,avgis non-monotonic, presenting a greater algorithmic challenge.
Qualitative Analysis: The Aminer Case Study
Using the Aminer citation dataset, the authors illustrated how different aggregation functions yield different types of communities:
minfunction: Identifies "balanced" groups where every member meets a specific baseline of influence.avgfunction: Tends to find small, "elite" clusters of highly-cited researchers.sumfunction: Favors larger, diverse, and highly productive research clusters.
Conclusion
This research significantly broadens the scope of community search by introducing complex aggregation functions and practical size constraints. By providing both rigorous hardness proofs and efficient heuristic algorithms, the authors enable the discovery of influential communities in "web-scale" graphs. Future work may explore parallel computing frameworks to further scale these methods for even larger, dynamic datasets.
Summary updated