江苏龙网

  1. 首页 > 人文 > >

基于Plato高性能图计算框架的社团发现算法

近年来 ， 图作为一种表示和分析大数据的有效方法 ， 因为特别适合用作社交网络、推荐系统、网络安全、文本检索和生物医疗等领域至关重要的数据分析和挖掘工具 ， 而受到广泛关注 。
【基于Plato高性能图计算框架的社团发现算法】这里的“图”并不是指普通的图像和照片 ， 而是用于表示对象之间关联关系的一种抽象数据结构 ， 图计算就是以图作为数据模型来表达问题并予以解决的过程 。 图计算可以将不同来源、不同类型的数据融合到同一个图里进行分析 ， 得到原本独立分析难以发现的结果 。 它的典型的应用有：
定期对网页进行影响力排序以提升用户的搜索体验；
分析庞大的社交网络结构以便精准地为用户推荐服务；
通过子图匹配等方式了解蛋白质间的相互作用从而研制更有效的临床医药 。
Plato是腾讯图计算TGraph整合腾讯内部图计算资源 ， 打造的业界领先的超大规模图计算平台 ， 已服务微信等腾讯内部的核心业务 。
相对于目前全球范围内其它的图计算框架 ， Plato可满足十亿级节点的超大规模图计算需求 ， 将算法计算时间从天级缩短到分钟级 ， 性能全面领先领先于其它主流分布式图计算框架 。 本文即将为大家介绍“基于Plato高性能图计算框架的社团发现算法” ， 并从中揭晓Plato高性能的秘密 。
一.Plato简介
腾讯高性能分布式图计算框架Plato架构如图1所示：
基于Plato高性能图计算框架的社团发现算法
文章图片

图1：Plato架构
Plato高性能图计算框架主要贡献有：
1.Plato能高效地支撑腾讯超大规模社交网络图数据的各类计算 ， 且性能达到了学术界和工业界的顶尖水平 ， 比SparkGraphX高出1-2个数量级 ， 使得许多按天计算的算法可在小时甚至分钟级别完成 ， 也意味着腾讯图计算全面进入了分钟级时代 。
2.Plato的内存消耗比SparkGraphX减少了1-2个数量级 ， 意味着只需中小规模的集群（10台服务器左右）即可完成腾讯数据量级的超大规模图计算 ， 打破了动辄需要上百台服务器的资源瓶颈 ， 同时也极大地节约了计算成本 。
3.Plato隶属腾讯图计算TGraph ， 起源于超大规模社交网络图数据 ， 但可以完美适配其他类型的图数据 ， 同时 ， Plato作为高性能、可扩展、易插拔的工业级图计算框架 ， 推动了业界超大规模图计算框架的技术进步 。
Plato目前已支持节点中心性指标、连通图、社团发现、图表示学习等多种图算法 。
二.社团发现算法简介
社交网络往往具有聚类效应 ， 具有相似背景或相同爱好的人 ， 更倾向于聚集在一起 ， 形成一个圈子（社团） 。 如何从一个给定的社交网络还原现实生活中的圈子 ， 在社交推荐、社交营销等领域有着非常广泛的应用 。
复杂网络中的聚类效应
复杂网络研究用图（Graph）表示网络：将网络的参与者抽象成节点（Vertex） ， 而将参与者之间的交互或联系抽象成节点之间的连边（Edge） ， 这些节点的集合V={v1,v2,···,vn}与连边的集合E={vivj|vi,vj∈V}就构成一幅图G(V,E) 。
如图2所示 ， 网络中有4簇内部连边稠密、与外部连边稀疏的节点 ， 这就是聚类效应的直观体现 。 通常把这些聚簇称为社团（Community） ， 社团发现算法的目标就是将节点准确地划分至不同的社团中 。 我们对该网络使用经典的社团发现算法 ， 计算结果如图3所示 ， 用节点颜色标记社团归属 。
基于Plato高性能图计算框架的社团发现算法
文章图片

图2：社交网络
基于Plato高性能图计算框架的社团发现算法
文章图片

图3：社团发现计算结果
模块度指标
模块度指标能较好地刻画社团划分质量[1]：
对于相同网络 ， 不同的社团划分通常对应不同的模块度 ， 以图4和图5为例 ， 若以不同的颜色区分不同的社团 ， 那么图4中的平凡划分的模块度为零 ， 图5中的非平凡划分的模块度为5/14 。 显然 ， 后者的划分更为合理 。 这说明模块度的大小能在一定程度上反映社团划分的质量 ， 其值越大 ， 划分质量越好 。
基于Plato高性能图计算框架的社团发现算法
文章图片

图4：平凡划分 ， Q=0
基于Plato高性能图计算框架的社团发现算法
文章图片

图5：非平凡划分 ，， Q=5/14
基于边介数的分裂算法
已知社团划分质量的衡量指标——模块度 ， 接下来就要找出使模块度达到最大的社团划分 。 模块度的最大化问题已被证明是一个“NP难题”[5] 。 因此 ， 为了在可接受的时间内求得社团划分 ， 往往使用贪心策略寻求次优解 ， 这与数据聚类的思想是如出一辙的 。
接下来介绍的聚类算法 ， 又可以分为分裂算法和凝聚算法 ， 首先介绍一个以去除连边达到聚类目的的分裂算法：首先把整个网络看作一个社团 ， 然后不断地去除介数最大的边 ， 使其分裂成多个社团 ， 然后通过模块度指标来控制分裂的深度 。
由于分裂算法涉及到全网边介数的计算 ， 计算复杂度过高 ， 工程实现困难 ， 接下来介绍更易工程实现的算法 。
基于模块度增益的凝聚算法
针对分裂算法无法应用于大规模网络以及无法识别小规模社团的缺点 ， 一种能够侦测到层次化社团结构的凝聚算法[2]（FastUnfolding算法）被提出：首先把每个节点分别看作一个社团 ， 然后把使模块度增益最大的邻近社团吸纳成更大的社团 ， 当模块度增益为零时停止 。
算法最终可能输出多个社团划分：每一次凝聚都对应一个层次的社团划分 。 层次越低 ， 社团规模越小 ， 从而避免了小规模社团的侦测遗漏现象 。
标签传播算法
标签传播算法[3]（简称LPA）不以目标函数为导向 ， 大体流程是：将节点所属社团的名称作为节点标签 ， 标签通过某种方式在网络中传播开来 ， 当标签的传播稳定后 ， 每个节点都有一个标识其所属社团的标签 ， 也就完成了社团划分 。
然而 ， LPA也有一个不容忽视的弱点：计算结果的高随机性 ， 重复运行两次LPA的社团划分结果往往并不一致 。 LPA用邻居标签来在更新节点标签时 ， 每个邻居的重要性是等同的、每个标签的重要性也是等同的 ， 结合到LPA在传播过程中的随机性 ， 某一次随机传播带来的误差 ， 可能被多次传播 ， 从而被不断扩散、放大 。
因此提出了HANP算法[4] ， 在采集邻居的标签时 ， 综合考虑各个邻居对节点的重要性 ， 以及各标签经过多轮传播后的衰减 ， 从而降低误差产生的概率以及控制误差放大 。
三.社团发现算法基于Plato的高性能实现
业界实现方案
在图计算发展的近些年来 ， 涌现出许多优秀的图计算框架 。
使用C/C++语言编写的GraphLab和PowerGraph系统提供了基于消息传递的编程接口以及一套图算法的高性能分布式实现 ， 但系统实现层面的COST(theConfigurationthatOutperformsaSingleThread)[6]较高 。
SparkGraphX系统结合了Spark的大数据生态环境 ， 在编程接口上相对GraphLab和PowerGraph提高了易用性 ， 同时很好的处理了计算容错问题 ， 但由于Java/Scala语言本身的开销 ， 无法达到理想的性能 。
Gemini[7]系统提供了一种低COST且可扩展的分布式图计算设计方案 。
基于Plato高性能图计算框架的社团发现算法
文章图片

图6：不同计算模式下LPA算法执行示意图
社团识别算法的计算模式多种多样 ， 对于LPA和HANP等算法 ， 已有计算模式存在很大的性能问题 ， 图6以Gemini系统为例来详细介绍：
Dense模式下 ， 节点D从邻居节点获取标签 ， 并尝试合并为一个消息（包含两个元素(La,1),(Lb,1)分别表示A和B的标签值） 。 由于无法合并为定长消息 ， 因此D和E的消息总长度为5 。
Sparse模式下 ， A将自己的标签发送到A的镜像节点中 ， 因此ABC三个节点发送消息总长度为3 ， 相比dense模式减少了不错的通信量 。 但Sparse模式下ABC三个节点通过push的方式将消息传递到DE两个节点 ， 需要加锁避免写冲突 ， 同时D和E需要维护长度为5的变长buffer来保存标签 。
从上述例子我们发现：发送的消息不可以被合并为定长消息 ， 内存占用过多 ， 无法在有限资源内高效的完成计算 。
Plato高性能实现方案
Plato借鉴并简化了Cyclops[8]论文中的方法 ， 使用MPI的高性能通讯原语来实现 。 如图6所示 ， ABC三点首先将自己的状态（标签值）同步至server-1中 ， 在这个过程中产生3个单位的通信量 ， 相比Dense模式通信更少 。 之后 ， 节点D和E使用Pull的方式访问周围所有节点的标签来确定自己的标签值 。
通过以上方式 ， 可以极大的减少计算过程中的内存消耗以及通信开销 ， 能够做到在有限资源内 ， 迅速完成LPA和HANP等消息不可合并为定长数据类型的图算法计算 。
Plato算法示例
上述FastUnfolding、LPA和HANP等社团发现算法已在github开源 ， 感兴趣的读者可通过如下地址获取算法介绍和源代码：
开源地址：
https://github.com/Tencent/plato
算法介绍：
https://github.com/Tencent/plato/wiki
代码示例：
https://github.com/Tencent/plato/tree/master/example
四.总结
腾讯高性能分布式图计算框架Plato ， 已集成了最常用的FastUnfolding、LPA和HANP等社团发现算法的高性能实现 ， 可以在分钟级完成超大规模网络的社团发现 ， 期待能为业界图计算的技术进步贡献一份绵薄之力 。
参考文献：
[1]M.E.J.Newman,M.Girvan.FindingandEvaluatingCommunityStructureinNetworks[J].PhysicalReviewE,2004,69(2):026113.
[2]V.D.Blondel,J.L.Guillaume,R.Lambiotter,etal.FastUnfoldingofCommunityHierarchiesinLargeNetworks[J].JournalofStatisticalMachanics:TheoryandExperiment,2008,10:10008.
[3]U.N.Raghavan,R.Albert,S.Kumara.NearLinearTimeAlgorithmtoDetectCommunityStructuresinLarge-ScaleNetworks[J/OL].EprintarXiv,2007,0709:2938.[2012-6-18].http://www.arXiv.org.
[4]IanX.Y.Leung,PanHui,PietroLi`o,etal.Towardsreal-timecommunitydetectioninlargenetworks[J/OL].EprintarXiv,2009,0808:2633.[2019-12-18].http://www.arXiv.org.
[5]S.Fortunato.CommunityDetectioninGraphs[J/OL].EprintarXiv.2009,0906:0612.[2012-12-24].http://www.arXiv.org.
[6]McSherry,Frank,MichaelIsard,andDerekG.Murray."Scalability!Butatwhat{COST}?."15thWorkshoponHotTopicsinOperatingSystems(HotOS{XV}).2015.
[7]Zhu,Xiaowei,etal."Gemini:Acomputation-centricdistributedgraphprocessingsystem."12th{USENIX}SymposiumonOperatingSystemsDesignandImplementation({OSDI}16).2016.
[8]Chen,Rong,etal."Computationandcommunicationefficientgraphprocessingwithdistributedimmutableview."Proceedingsofthe23rdinternationalsymposiumonHigh-performanceparallelanddistributedcomputing.ACM,2014.


    推荐阅读


    上一篇：央视新闻、中央广电总台中国之声终于找到你！这一声“妈”，她等了11528天

    下一篇：2020年6月1日起！严查不戴头盔、不系安全带的行为