论文部分内容阅读
当前社交网络成为人们获取信息和发布信息的主要交流平台。种类繁多的社交网站为用户提供多种多样的服务。用户为了满足自身的需求,往往在多个网络注册有账号。信息通过这些用户可以在多网络流通,因此从多网络出发研究影响力最大化技术具有重要意义。然而影响力最大化研究面临网络规模大、效率不高等挑战,MapReduce和BSP作为当下流行的大规模数据处理计算模型,为大规模网络的数据和处理带来了曙光。BSP计算框架在迭代式图算法处理方面较MapReduce计算框架优势显著。本文主要从以下几个方面研究多网络影响力最大化及并行化技术:1.现有多网络耦合方法没有考虑多网络用户在多网络信息传播的特性,认为用户一定会将信息传播至其他网络。针对现有方法的不合理假设,本文考虑多网络用户的特性,提出一种多网络耦合模式。2.针对影响力最大化贪心算法精度高而扩展性和效率不高的问题,本文利用并行计算的思想提高贪心算法的执行效率,基于当下流行并行计算框架BSP对贪心算法进行优化,提出并行化影响力最大化算法BSPGreedy。3.利用并行化计算框架分析大规模网络时,前提是将网络分割成多个子集,分配不同处理器并行化处理。为了充分利用大规模框架的并行计算能力,本文在经典单网络图划分算法Metis的基础上,提出基于Metis的多层次多网络协同划分算法CPMN。