基于LT^+模型的社交网络影响力最大化研究

Influence Maximization Based on LT^+ Model in Social Networks

影响力最大化问题的目标是寻找社交网络中一组种子结点集合,在给定的传播模型下,使得这些结点最终传播的影响范围最大。Kempe和Kleinberg提出的贪心算法可以获得很好的影响范围,但是因复杂度太高而并不适用于大型社交网络。Chen和Yuan等人基于线性阈值(LT)模型提出了构造局部有向无环图的启发式算法,但是LT模型只考虑了邻居结点的直接影响力,忽略了结点之间存在的间接影响力。因此,在LT模型的基础上,结合网络中结点之间存在的间接影响力,提出了LT+影响力模型,并利用构造局部有向无环图的启发式算法求解LT+模型的影响力最大化,称为LT+DAG算法。真实数据集上的对比实验表明,LT+DAG算法具有更好的影响范围以及较好的可扩展性。

Influence maximization is a problem of finding a small group of seed nodes in a social network, so that the in- fluence scope of spread in the network is maximized. Kempe and Kleinberg proposed a greedy algorithm which has a wide influence, but its high complexity makes it unsuitable for large social network. Chen and Yuan proposed a heuristic algorithm called local directed acyclic graphs based on linear threshold （LT） model. But LT model only considers the di- rect influence of neighbors nodes, and ignores the indirect influence between the settled nodes. Therefore, combining with the indirect influence between nodes in the network, we proposed LT＋ influence model based on LT model. We al- so used the local directed acyclic graphs （DAGs） heuristic algorithm to solve the problem of influence maximization, known as LT＋ DAG algorithm. Extensive experiments were done on real-world dataset to compare the proposed method with other influence maximization algorithms. The result shows that the proposed method can achieve better influence scope and extensihility.