Community-diversified influence maximization in social networks. (September 2020)

• Record Type: Journal Article
• Authors: Li, Jianxin; Cai, Taotao; Deng, Ke; Wang, Xinjue; Sellis, Timos; Xia, Feng
• Is Part Of: Information systems. Volume 92(2020)
• Publication Date: 2020-09
• Subjects: Social community -- Influence maximization -- Diversified influence propagation; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2020.101522
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: To meet the requirement of social influence analytics in various applications, the problem of influence maximization has been studied in recent years. The aim is to find a limited number of nodes (i.e., users) which can activate (i.e. influence) the maximum number of nodes in social networks. However, the community diversity of influenced users is largely ignored even though it has unique value in practice. For example, the higher community diversity reduces the risk of marketing campaigns as you should not put all your eggs in one basket; the diversity can also prolong the effect of a marketing campaign in the future promotion. Motivated by this observation, this paper investigates Community-diversified Influence Maximization (CDIM) problem to efficiently find k nodes such that, if a message is initiated and spread by the k nodes, the number as well as the community diversity of the activated nodes will be maximized at the end of propagation process. This work proposes a metric to measure the community-diversified influence and addresses a series of computational challenges. Two algorithms and an innovative CPSP-Tree index have been developed. This study also investigates the situation that community definition is not specified. The effectiveness and efficiency of the proposed solutions have been verified through extensive experimental studies on five real-world social network datasets. Highlights: A new problem, named community-diversified influence maximization (CDIM), is introduced in this paper. A deliberately designed metric has been proposed in this paper to evaluate the CDIM. Two algorithms ( greedy and upper bound ) are developed in this paper to solve the CDIM problem effectively.