摘 要: 为了改善社交网络中影响最大化问题的算法的效率。我们针对社交网络中幂率分布的现象,提出了二分图模型。在模型中对影响的传播过程进行了限制，将社交网络划分为二分图，使得候选的种子集合大幅减小。此模型能够计算精确的影响力的同时避免了蒙特卡洛多次模拟，降低了复杂度。我们通过在一个真实数据集合上的测试,验证了二分图模型可以得到不错的结果。
关键词: 社交网络；影响最大化；幂率分布；二分图
Optimization of Social Network Influence Maximization Algorithm Based on Power-rate Distribution
Zhang Ning1, Cheng Yaokai2, Ma Yukun3
1(Computer Science and Technology, 2015 , Honors School, Harbin Institute of Technology)
2(Computer Science and Technology, 2015, School of Computer Science and Technology，Harbin Institute of Technology)
3(Computer Science and Technology, 2015 , Honors School, Harbin Institute of Technology)
Abstract: In order to improve the efficiency of algorithms in social networks that Influence Maximization problem. We propose a binary graph model for the phenomenon of Power rate distribution in social networks. In the model, the propagation process of the influence is limited, and the social network is divided into binary graph, so that the Seed node candidate set is greatly reduced. This model can calculate accurate influences while avoiding Monte Carlo simulations for many times, reducing complexity. We tested a real data sets to verify that the binary model yields good results.
Key words: Social network; maximum impact; power distribution; binary graph
引言
随着互联网的快速发展，网络空间出现了许多社交网络,譬如腾讯QQ，Facebook，新浪微博等等。不同的社交网络由于拓扑结构不同而各有特点。在腾讯公司的即时通讯app微信中各个用户和好友关系组成的社交网络几乎不会有节点的度超过一万,并且每个节点和与其相连的大多数节点都是线下的朋友，联系紧密。IC模型最初就是用来在这样的社交网络上寻找有影响力的节点的。
但是随着新型社交网站的发展,出现了一些非传统的社交网络,这些社交网络在结构上与传统社交网络有很大不同。例如，在微博上的很多用户拥有上百万的粉丝量，而另一方面大量的用户的粉丝数目只有一百个左右。在youtube中一个视频会有百万次的点击率,另一方面大量的视频却无人问津。在这样的网络中之中,幂率分布(长尾效应)很明显,也就是说极少数个体对应极高的值，而拥有极低值的个体，数量却占总体的绝大多数。形象地描述可称曲线靠近纵轴的部份为tall head，而靠近横轴的部份则是所谓的long tail。如图1所示。
在幂率分布明显的社交网络之上解决影响最大化问题的话,根据经验,我们只需要在tall head之中选择我们需要的种子节点即可。 在此基础上我们对贪心算法进行了改进,通过对原始图形进行一些删减。并且在一个数据集合上进行了实验验证。证明了算法的高效。
本文主要贡献如下:(1)本文首次将幂率分布的特性应用到影响最大化问题之中进行问题求解。(2)本文对贪心算法进行改进得到了newgreedy算法,并且在幂率分布明显的图形上进行影响最大化问题的求解。(3)我们对贪心算法的改进和某些基于贪心算法的改进是兼容的。我们将celf算法的思想运用到了newgreedy算法得到了greedy++算法。
引言
Kempe, Kleinberg, and Tardos首先将这个问题形式化描述为离散最优化问题(Discrete Optimization Problem), 证明在常用随机级联模型(Stochastic Cascade Model)类的信息扩散模型 IC、LT 模型下求解影响力最大化问题最优解是一个 NP-hard 问题，然后给出了有证明保证(Provable Guarantee)的可求得 （1-1/e）≈63%最优的贪婪算法。但是 Kempe 所提出的近似算法十分耗时,在其论文的试验部分处理 15000 结点网络需要几天的时间,之后的研究主要关注于最优化近似算法的效率提高上。
针对这个问题，学界的工作大多是基于Kempe等人的工作，提出近似算法，改进算法的时间复杂度，或者提出新的扩散模型，在新的模型下进行研究算法，提升算法的可并行性，提高算法在大规模数据集合上的表现。
Leskovec 等人提出的改进方法 CEFL(Cost-Effective Lazy Forward)方法是一种新的使影响力最大的择初始结点优化方法，CELF 算法利用了 IC 模型的子模性(submodularity)，网络中加入一个结点到集合中得到的边际收益，要大于等于加入同一个结点到集合的父集所得到的边际收益。利用子模性大大减少了计算结点影响力传播效果的次数，减少选择初始有影响力结点的计算量。实验表明，CELF 算法结果接近贪心策略近似算法，但算法运算时间要快 700倍。在 CEFL 的基础上，Amit Goyal 等人利用子模性进一步优化了 CELF 算法，又提出了更高效的 CEFL++算法， 算法效率再次提高了 35-55%。
相关阅读
赞助商广告
