Seed Node Distribution for Influence Maximization in Multiple Online Social Networks
Seed Node Distribution for Influence Maximization in Multiple Online Social Networks
复制标题
多个在线社交网络影响力最大化的种子节点分布
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Soham Das
中科院分区：
文献类型：
--
作者：
Soham Das
在本文中，我们研究的种子节点分布（SND）问题的影响力最大化在多个在线社交网络给定的最大数量的种子节点，比如说h，可以用来传播影响力，我们需要确定这些种子节点在多个网络的分布，以最大限度地提高d跳的影响力。以前的大多数作品都集中在单个网络中的影响力最大化，这在当今的场景中肯定是不够的，因为用户大多在不同的社交网站上拥有多个帐户。考虑到这一点，我们的工作已经在多个在线社交网络上定义。在本文中，我们表明，SND问题的目标函数是不是次模块和简单的贪婪算法可能无法产生近最优解的问题。因此，我们提出了传播阻力商（PRQ），它给我们一个估计有多少阻力信息遇到通过网络传播，并开发了一个基于PRQ的启发式。我们通过使用爬山技术HCR的解决方案。最后，我们说明了PRQ启发式和HCR的真实的数据集上的Foursquare，Twitter和其他三个合著者网络的有效性。我们的算法提供的解决方案是在2%至14%的OPT（从不同的网络的种子数量的最佳组合）的Foursquare-Twitter数据集和14%至22%的OPT的合著者网络数据集。这些解决方案可以通过使用HCR进一步改善至低至OPT的2%至5%。
In this paper, we study the Seed Node Distribution (SND) problem for influence maximization in multiple online social networks-given a maximum number of seed-nodes, say h, that can be used to propagate influence, we need to determine the distribution of these seed nodes across multiple networks to maximize the influence in d hops. Most of the previous works focused on influence maximization in single networks, which is surely not enough in the present day scenario when users mostly maintain multiple accounts on different social networking sites. Taking this into account, our work has been defined on multiple online social networks. In this paper, we show that the objective function of SND problem is not sub-modular and that the simple greedy algorithm may fail to generate near-optimal solution to the problem. Hence we propose the Propagation Resistance Quotient (PRQ) which gives us an estimate of how much resistance information encounters to propagate through a network and develop a heuristic based on PRQ. We refine the solution by using a hill-climbing technique HCR. Finally we illustrate the effectiveness of PRQ heuristic and HCR on real data-sets of Foursquare, Twitter and three other co-author networks. Our algorithm provides solutions which are within 2% to 14% of OPT (optimal combination of number of seeds from the different networks) for the Foursquare-Twitter data-sets and 14% to 22% of OPT for the coauthor network data-sets. These solutions can be further improved to as low as 2% to 5% of the OPT with the use of HCR.