  In many real-world applications such as social network analysis and online
marketing/advertising, the community detection is a fundamental task to
identify communities (subgraphs) in social networks with high structural
cohesiveness. While previous works focus on detecting communities alone, they
do not consider the collective influences of users in these communities on
other user nodes in social networks. Inspired by this, in this paper, we
investigate the influence propagation from some seed communities and their
influential effects that result in the influenced communities. We propose a
novel problem, named Top-L most Influential Community DEtection (TopL-ICDE)
over social networks, which aims to retrieve top-L seed communities with the
highest influences, having high structural cohesiveness, and containing
user-specified query keywords. In order to efficiently tackle the TopL-ICDE
problem, we design effective pruning strategies to filter out false alarms of
seed communities and propose an effective index mechanism to facilitate
efficient Top-L community retrieval. We develop an efficient TopL-ICDE
answering algorithm by traversing the index and applying our proposed pruning
strategies. We also formulate and tackle a variant of TopL-ICDE, named
diversified top-L most influential community detection (DTopL-ICDE), which
returns a set of L diversified communities with the highest diversity score
(i.e., collaborative influences by L communities). We prove that DTopL-ICDE is
NP-hard, and propose an efficient greedy algorithm with our designed diversity
score pruning. Through extensive experiments, we verify the efficiency and
effectiveness of our proposed TopL-ICDE and DTopL-ICDE approaches over
real/synthetic social networks under various parameter settings.
