一种求解社交网络影响力最大化的置信传播算法

Belief Propagation Algorithm for Solving Social Network Influence Maximization

社交网络影响力最大化问题是一类重要的NP-难问题,在人工智能中有重要的研究价值。在实际生活中,通常需要考虑用户传播信息的成本问题,为了解决信息传播中所需成本问题,设计了一种求解社交网络影响力最大化的置信传播算法。将社交网络影响力最大化问题映射成约束可满足问题,再将约束可满足问题转化为因子图模型,用置信传播算法在因子图模型上进行信息传递,从而推断出所有节点的边缘概率。在真实网络以及人工合成网络数据集上与线性规划算法作实验对比,结果表明:该算法有效。

Social network influence maximization is an important NP-hard problem,which has important research value in artificial intelligence.In real life,it is usually necessary to consider the cost of information dissemination by users.In order to solve the cost problem of information based communication,a belief propagation algorithm is designed to solve the maximization of social network influence.Firstly,the problem of social network influence maximization is mapped into the constraint satisfaction problem,and then the constraint satisfaction problem is transformed into a factor graph model,and the belief propagation algorithm is used to carry out information transmission in the factor graph model,so as to infer the edge probability of all nodes.Experiments on real networks and artificial networks show that the proposed algorithm is effective.