Top-$L$ Most Influential Community Detection Over Social Networks (Technical Report)

Nan Zhang, Yutong Ye, Xiang Lian, Mingsong Chen

In many real-world applications such as social network analysis and online marketing/advertising, the \textit{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 \textit{seed communities} and their influential effects that result in the \textit{influenced communities}. We propose a novel problem, named \textit{\underline{Top-$L$} most \underline{I}nfluential \underline{C}ommunity \underline{DE}tection} (Top$L$-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 Top$L$-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 Top$L$-ICDE answering algorithm by traversing the index and applying our proposed pruning strategies. We also formulate and tackle a variant of Top$L$-ICDE, named \textit{diversified top-$L$ most influential community detection} (DTop$L$-ICDE), which returns a set of $L$ diversified communities with the highest diversity score (i.e., collaborative influences by $L$ communities). We prove that DTop$L$-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 Top$L$-ICDE and DTop$L$-ICDE approaches over real/synthetic social networks under various parameter settings.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment