关键词: 社会网络分析, 影响力传播最大化, 关联影响力传播最大化, 线性阈值模型, Spark GraphX

Abstract:

Influence maximization is currently a focused problem in the research area of social networks. This paper considers the problem of correlated influence maximization (CIM) where multiple influence diffusion processes promote with each other. First, a correlated linear threshold model (CLT) is presented by extending the classic linear threshold model to model the diffusion processes of correlated influences. Then, the correlated influence maximization under CLT is proven to be NP-hard and the objective function to be submodular respectively. An algorithm which is based on the estimation of activation contributions of vertices (ACA) under CLT is proposed to solve CIM. Since the estimations of activation contribution for different nodes are independent with each other, a parallel ACA which is implemented based on Spark GraphX is furthermore presented to solve CIM. Finally, experiments are carried on real data sets of social networks to verify the feasibility and scalability of the proposed algorithms.

Key words: social networks analysis, influence maximization, correlated influence maximization, linear threshold model, Spark GraphX