  Community search is a problem that seeks cohesive and connected subgraphs in
a graph that satisfy certain topology constraints, e.g., degree constraints.
The majority of existing works focus exclusively on the topology and ignore the
nodes' influence in the communities. To tackle this deficiency, influential
community search is further proposed to include the node's influence. Each node
has a weight, namely influence value, in the influential community search
problem to represent its network influence. The influence value of a community
is produced by an aggregated function, e.g., max, min, avg, and sum, over the
influence values of the nodes in the same community. The objective of the
influential community search problem is to locate the top-r communities with
the highest influence values while satisfying the topology constraints.
Existing studies on influential community search have several limitations: (i)
they focus exclusively on simple aggregation functions such as min, which may
fall short of certain requirements in many real-world scenarios, and (ii) they
impose no limitation on the size of the community, whereas most real-world
scenarios do. This motivates us to conduct a new study to fill this gap. We
consider the problem of identifying the top-r influential communities
with/without size constraints while using more complicated aggregation
functions such as sum or avg. We give a theoretical analysis demonstrating the
hardness of the problems and propose efficient and effective heuristic
solutions for our topr influential community search problems. Extensive
experiments on real large graphs demonstrate that our proposed solution is
significantly more efficient than baseline solutions.
