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

摘要：

社会网络中影响力传播最大化是社会网络分析领域所关注的重要问题。针对多个影响力同时进行传播，且影响力间存在传播促进的情况，提出关联影响力传播最大化问题。首先，对经典线性阈值模型进行扩展，提出关联影响力线性阈值模型对关联影响力传播过程进行建模；其次，定义了关联影响力传播最大化问题，证明了该问题是NP-hard的，以及问题目标函数满足子模性；再次，针对该问题提出基于结点激活贡献估计的求解算法；然后，利用结点激活贡献估计存在相互独立性，进一步提出了并行化求解算法，并在Spark GraphX并行图计算框架上实现了该算法；最后，在真实的社会网络数据集上，通过实验测试验证了所提出方法的有效性。

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