论文部分内容阅读
家庭用户市场是通信行业重点竞争的市场,运营商急需一种家庭关系识别模型,能够在海量的用户历史通话记录中准确地识别出家庭用户。随着智能手机迅速普及,通话社交网络不仅成为最大的社交网络,而且还映射了现实世界中不同用户间的亲密关系,因此通话社交网络呈现出了一定的社区结构。针对这一特征,本文提出利用社区发现算法构建通话社交网络上的家庭关系识别模型。综合考虑时间、模块度等要素,本文选择Louvain算法作为家庭关系识别模型的社区发现算法。目前,真实世界的社交网络规模早已达到亿级别,对家庭关系识别模型构建带来了严峻的计算挑战。由于通话数据集呈现出网状式图结构特征,并且Spark分布式并行计算平台提供了用于图分析和图计算的GraphX组件,所以本文在Spark平台上构建家庭关系识别模型以及重点研究基于GraphX的Louvain算法并行化,主要工作与创新点包括以下几个部分:1.基于GraphX实现Louvain算法并行化。本文分析Louvain算法的基本原理,通过GraphX的发送、聚合消息机制完成Louvain算法的核心计算步骤,在GraphX上实现Louvain算法的并行化。为了解决并行化后出现的消息滞后问题,本文实现了基于进程锁思想的PLL(Process Lock Louvain)算法和基于连通图思想的CGL(Connected Graph Louvain)算法。通过实验分析,综合考虑大规模网络社区发现的运行时间和结果精度,最终选择基于连通图思想的CGL算法。2.改进CGL算法。在社区发现算法划分社区的过程中,每个社区都有唯一的社区标签代表当前社区,每一个成员都有唯一的成员标签代表当前节点,社区标签选自社区内的成员标签。但是在并行化的应用中发现,有的社区标签并不来自社区成员标签,导致一些节点错分到同一社区。本文通过增加社区标签重分配这一步改进CGL算法,提出ICGL(Improve Connected Graph Louvain)算法。通过对实验结果分析,发现ICGL算法在与CGL算法时间差异不大的情况下,比CGL算法的模块度更高。此外,ICGL算法源于Louvain算法,都是一种自底向上的凝聚层次聚类算法,在凝聚的过程中出现社区发现的结果分辨率不足的问题。因此本文提出超大社区定义、社区分解定义以及基于ICGL算法设计和实现多个超大社区的社区并行分解算法。经实验表明,使用社区并行分解算法可以快速得到不同分辨率的社区发现结果,并且该算法在一定程度上可以提高社区划分结果的准确性。3.基于Spark分布式并行计算平台构建家庭关系识别模型。基于某市的通话数据,利用ICGL算法和社区并行分解算法,本文提出根据通话时间段、通话次数、用户属性等特征构建基于家庭亲密度网络的家庭关系识别模型和基于通话次数网络的家庭关系识别模型。对比这两种家庭关系识别模型精确率、召回率、运行时间以及模块度,实验结果表明,本文提出的基于家庭亲密度网络的家庭关系识别模型有更准确的家庭关系识别能力,进一步证明了本文提出的ICGL社区发现算法和社区并行分解算法具有重要的理论意义和实际应用价值。