Plato简介腾讯高性能图计算框架Platograph作为大数据表示和分析的有效方式，已经成为生物医药和生物医学等领域的关键数据分析和挖掘工具。其他领域。例如，定期按影响力对网页进行排名，以改善用户的搜索体验；分析庞大的社交网络结构，为用户精准推荐服务；通过子图匹配等方法了解蛋白质之间的相互作用，以开发更有效的临床医学。Plato是腾讯图计算TGraph打造的业界领先的超大规模图计算平台，整合了腾讯内部图计算资源。Plato针对亿级节点的超大规模图计算，将算法的计算时间从几天缩短到分钟，性能提升数十倍，达到行业领先水平，打破了经常出现的资源瓶颈需要数百台服务器。需要十台服务器才能完成计算。柏拉图赋能腾讯内部包括微信在内的多项核心业务，创造了巨大的商业价值。图1：Plato架构Plato开源地址：https://github.com/tencent/platoPlato的高性能图计算框架有以下主要贡献：Plato可以高效支持腾讯超大规模社交网络的各类计算图数据，其性能达到了学术界和工业界的顶级水平，比SparkGraphX高出1-2个数量级，使得很多按天计算的算法可以在小时甚至分钟级别完成，这也意味着腾讯图计算全面进入分钟级时代。Plato的内存消耗比SparkGraphX低1-2个数量级，意味着仅需中小型集群（约10台服务器）即可完成腾讯的数据级超大规模图计算，打破了动不动就需要数百台服务器。资源瓶颈，也大大节省了计算成本。Plato属于腾讯图计算TGraph。它起源于超大规模的社交网络图数据，但可以完美适配其他类型的图数据。同时，Plato作为一个高性能、可扩展、可插拔的工业级图计算框架，推动了超大规模图计算框架的技术进步。Plato算法应用Plato目前支持节点中心性指标、连通图、社区发现、图表示学习等多种图算法。这一次，我们将重点介绍基于柏拉图的社区发现算法。社交网络往往具有集群效应，具有相似背景或相同爱好的人往往聚集在一起形成一个圈子（社区）。如何从给定的社交网络中还原现实生活中的圈子，在社交推荐、社交营销等领域有着广泛的应用。社区发现算法简介复杂网络中的聚类效应复杂网络研究使用图来表示网络：将网络参与者抽象为节点（Vertex），将参与者之间的交互或连接抽象为节点Edge，这些节点的集合V={v1,v2,...,vn}和边集E={vivj|vi,vj∈V}构成图G(V,E)。如图2所示，网络中有4个内部连接密集、外部连接稀疏的节点簇，是集群效应的直观体现。这些集群通常被称为社区，社区发现算法的目标是将节点准确划分为不同的社区。我们对该网络使用经典的社区发现算法，计算结果如图3所示，社区隶属关系用节点颜色标记。图2：社会网络图3：社区发现计算结果模块化指数模块化指数可以更好地描述社区划分的好坏[1]：对于同一个网络，不同的社区划分通常对应不同的模块化，如图4和图以图5为例，如果用不同的颜色来区分不同的社区，则图4中平凡划分的模块度为零，图5中非平凡划分的模块度为5/14。显然，后一种划分更为合理。这说明模数的大小在一定程度上可以反映社区划分的质量，值越大，划分质量越好。基于边介数的分裂算法我们找到了衡量社区划分质量的一个指标——模块化，下一步就是寻找最大化模块化的社区划分。最大化模块化的问题已被证明是一个“NP-hard问题”[5]。因此，为了在可接受的时间内获得社区划分，我们往往采用贪心策略寻找次优解，这与数据聚类的思想如出一辙。在接下来介绍的聚类算法中，又可以分为分裂算法和聚类算法。首先引入分裂算法，通过去除相连的边来达到聚类的目的：首先将整个网络看成一个社区，然后不断去除介数。最大的边使其分裂成多个社区，然后分裂的深度由模块化指数控制。由于分裂算法涉及整个网络介数的计算，计算复杂度过高，工程实现难度大。接下来介绍一个比较容易实现的算法。基于模块化增益的集聚算法针对分裂算法不能应用于大规模网络和无法识别小规模社区的缺点，提出了一种可以检测层次社区结构的集聚算法[2]（FastUnfoldingAlgorithm）：首先将每个节点视为一个社区，然后将模块性增益最大的相邻社区吸收为更大的社区，当模块性增益为零时停止。该算法最终可能会输出多个社区划分：每个内聚度对应一个级别的社区划分。级别越低，社区规模越小，从而避免了小规模社区的检测遗漏。标签传播算法标签传播算法[3]（简称LPA）不受目标函数的指导。大致过程是：以节点所属社区的名称作为节点标签，标签以一定的方式在网络中传播。稳定后，每个节点都有一个标识其所属社区的标签，社区划分完成。但是，LPA也有一个不容忽视的弱点：计算结果的随机性高，两次运行LPA的社区划分结果往往不一致。当LPA使用邻居标签更新节点标签时，每个邻居的重要性是相等的，每个标签的重要性也是相等的。结合LPA在传播过程中的随机性，某种随机传播引起的误差，可能会传播多次，从而不断扩散放大。因此，提出了HANP算法[4]。在收集邻居的标签时，综合考虑每个邻居对节点的重要性以及每个标签经过多轮传播后的衰减情况，以降低错误产生的概率，控制错误放大。基于柏拉图的高性能社区发现算法在业界的实现近年来在图计算的发展过程中，涌现出了很多优秀的图计算框架。用C/C++语言编写的GraphLab和PowerGraph系统提供了基于消息传递的编程接口和一组图算法的高性能分布式实现，但是COST（TheConfigurationthatOutperformsaSingleThread）[6]在系统执行水平比较高。SparkGraphX系统结合了Spark的大数据生态环境，在编程接口方面相比GraphLab和PowerGraph提高了易用性，很好的处理了计算容错的问题，但是由于Java/Scala的开销语言本身，它无法达到理想的性能。Gemini[7]系统提供了一种低成本和可扩展的分布式图计算设计。图6：LPA算法在不同计算模式下的执行示意图。社区识别算法的计算方式多种多样。对于LPA、HANP等算法，现有的计算方式存在很大的性能问题。图6以Gemini系统为例详细介绍：在Dense模式下，节点D从邻居节点获取标签，并尝试将它们组合成一条消息（包括两个元素（La，1），（Lb，1）代表分别是A和B的标签值）。由于不能合并成一条定长消息，所以D和E的消息总长度为5。在稀疏模式下，A将自己的标签发送给A的镜像节点，所以发送的消息总长度由ABC的三个节点组成的为3，相比密集模式减少了流量。但是在稀疏模式下，ABC的三个节点通过push的方式将消息传递给DE的两个节点，需要加锁，避免写入冲突。同时，D和E需要维护一个长度为5的变长缓冲区来存放标签。从上面的例子中，我们发现发送的消息无法合并成定长消息，而且内存占用过大，无法在有限的资源内高效完成计算。Plato的高性能实现方案Plato借鉴并简化了Cyclops[8]论文中的方法，利用MPI的高性能通信原语实现。如图6所示，ABC三点首先将自己的状态（标签值）同步到server-1，在这个过程中，产生了3个单位的通信流量，比Dense模式通信要少。之后，节点D和E使用Pull访问周围所有节点的标签，以确定自己的标签值。通过以上方法，可以大大降低计算过程中的内存消耗和通信开销，在有限的资源内快速完成LPA、HANP等不能组合成定长数据类型的报文的图算法计算。柏拉图算法示例前面提到的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等社区发现算法的高性能实现可以在几分钟内完成超大规模网络的社区发现。有望为业界图计算的技术进步做出贡献。参考文献M.E.J.纽曼，M.格文。网络群落结构的发现与评价[J].物理评论E,2004,69(2):026113.V.D.Blondel、J.L.Guillaume、R.Lambiotter等人。大型网络中社区层次结构的快速展开[J]．统计力学杂志：理论与实验,2008,10:10008.U.N.Raghavan、R.Albert、S.Kumara。大型网络中社区结构检测的近线性时间算法[J/OL]。EprintarXiv，2007，0709：2938。[2012-6-18]。http://www.arXiv.org.IanX.Y.Leung、PanHui、PietroLi`o等。面向大型网络中的实时社区检测[J/OL]。EprintarXiv,2009,0808:2633.[2019-12-18].http://www.arXiv.org.S。福尔图纳托。图中的社区检测[J/OL]。电子打印arXiv。2009,0906:0612。[2012-12-24]。http://www.arXiv.org.McSherry、Frank、MichaelIsard和DerekG.Murray。“可扩展性！但{COST}是多少？”第十五届操作系统热点研讨会(HotOS{XV})。2015.朱晓薇，等。“Gemini：一个以计算为中心的分布式图形处理系统。”第12届{USENIX}操作系统设计与实现研讨会({OSDI}16)。2016.Chen,Rong,etal.“具有分布式不可变视图的计算和通信高效图形处理。”第23届国际高性能并行和分布式计算研讨会论文集。美国计算机学会，2014年。
