Influence Maximization for Cascade Model with Diffusion Decay in Social Networks  

作　　者：Zhijian Zhang Hong Wu Kun Yue Jin Li Weiyi Liu 

机构地区：[1]School of Information Science and Engineering,Yunnan University,Kunming,China [2]College of Science,Kunming University of Science and Technology,Kunming,China [3]College of Computer Science and Engineering,Qujing Normal University,Qujing,China [4]School of Software,Yunnan University,Kunming,China

出　　处：《国际计算机前沿大会会议论文集》2016年第1期106-108,共3页International Conference of Pioneering Computer Scientists, Engineers and Educators（ICPCSEE）

基　　金：This paper was supported by the National Natural Science Foundation of China (61562091), Natural Science Foundation of Yunnan Province (2014FA023,201501CF00022), Program for Innovative Research Team in Yunnan University (XT412011), and Program for Excellent Young Talents of Yunnan University (XT412003).

摘　　要：Maximizing the spread of influence is to select a set of seeds with specified size to maximize the spread of influence under a certain diffusion model in a social network. In the actual spread process, the activated probability of node increases with its newly increasing activated neighbors, which also decreases with time. In this paper, we focus on the problem that selects k seeds based on the cascade model with diffusion decay to maximize the spread of influence in social networks. First, we extend the independent cascade model to incorporate the diffusion decay factor, called as the cascade model with diffusion decay and abbreviated as CMDD. Then, we discuss the objective function of maximizing the spread of influence under the CMDD, which is NP-hard. We further prove the monotonicity and submodularity of this objective function. Finally, we use the greedy algorithm to approximate the optimal result with the ration of 1 ? 1/e.

关 键 词：Social networks INFLUENCE MAXIMIZATION Cascade model DIFFUSION DECAY SUBMODULARITY GREEDY algorithm 

分 类 号：C5[社会学]