论文部分内容阅读
这是一个非常有挑战的任务:在社交网络中发现一个大小为的节点集合作为初始目标种子集合来最大化影响力。这个问题被证明是一个NP-hard的问题。但是幸运的是影响力函数()具有次模属性,使得基本的贪心算法可以得到优化解的()近似。但它的速度很慢,所以首先我们提出三个算法来解决这个问题:(1)我们优化基础的贪心算法,把信息的传播限制在一个邻居区域来减少运行时间。我们使用DAG和递归方法来计算每个节点的影响力;(2)并且我们也把这个问题转化为一个不确定图中的可达概率查询的问题;(3)我们提出了一个更为精确的考虑了节点和它的一步邻居之间关系的度折扣启发式方法。然后我们使用Hadoop对于上述三个算法进行了并行化和其他优化:(a)对于集合的影响力计算分割并行化为成员节点的影响力计算;(b)对于多次独立的取样本过程进行并行化,并且将并行过程从根节点下放到左右子节点,将并行粒度进一步变细。将搜索过程从DFS改为双向的BFS过程,避免数据溢出,加快搜索速度;(c)进一步扩大步长,按照(3)的方法推算出考虑了二步邻居时的节点相对影响力,并且提出了一种可以考虑更大步长的新的可行方法。在现实世界的大规模社交网络上的集中实验显示出了:我们的优化的贪心算法和度折扣启发式算法是比基础的贪心算法和其他启发式方法更加有效的。并且并行和优化充分利用了集群的计算能力,很好的提高了算法的效率和精确性,从而使得我们的算法更加适应于大规模的社交网络图数据集。