经过技术调研，目前比较流行的图数据包括Neo4j、Janusgraph、HugGraph等。相关对比指标如下图所示：

技术选项

在图数据库查询方面Neo4j和Janusgraph支持的较好。但Neo4j开源不支持分布式架构而Janusgraph不支持常用的图算法库，比如中心性算法、相似性等算法、社区发现算法等。为了满足海量数据计算的诉求，我们通过Spark大数据计算社交网络指标，使用Janusgraph作为图数据查询的存储引擎。

中心性是社交网络分析中常用的一个概念，用以表达社交网络中一个点或者一个人在整个网络中所在中心的程度。测定中心性方法的不同，可以分为度中心性，接近中心性，中介中心性等，使用这些中心性指标进行价值用户的标签判别。

度中心性

度中心度顾名思义就是一个节点v与其他点直接连接的总和。对应公式为：

在社交网络中，我们可以用一个节点的度数（如社交网络中用户的好友数）来衡量中心性。对应到真实的社交网络中，度中心性高的人一般都是大V，有很大的知名度。因此通过度中心性可以快速挖掘高知名度用户。

接近中心性

接近中心性计算的是一个点到其他所有点的最近距离的总和，总和越小就说明这个点距离其他所有点越近。为了更好表示中心性，可以将接近中心性定义为节点数与距离总和的商：

（其中V代表节点数，表示节点v到节点i的最短距离。）

接近中心性体现的是一个点与其他点的近邻程度。接近中心性高的人在58部落中的具体表现为与更多的人有关系，无论是出度还是入度都很高。这类人群往往具有较高的交际能力，能够带动社区活跃度。

中介中心性

中介中心性指的是一个结点担任其它两个结点之间最短路的桥梁的次数。经过一个点的最短路径的数量越多，就说明它的中介中心性越高。对应公式表示为：

其中表示的是节点s和t之间的最短路径的数量，而是最短路径中经过节点v的数量。如果一个大的社交网络中包含了几个分群，那么中介中心度高的人就起到将这些分群连接起来的作用。挖掘中介中心性高的用户有利于社区不同分群之间的沟通串联。

从图上我们可以看到JanusGraph具备如下特点：

1. 提供OLTP图遍历查询功能；
2. 提供OLAP图计算分析功能；
3. 图存储数据的事务管理；
4. 可以兼容多种三方存储(Cassandra,HBase等)；
5. 可以兼容多种三方索引(Elasticsearch,Solr等)。

JanusGraph集群

存储后端和索引后端的选型：

为了支持海量数据存储和后期与spark结合，我们采用HBase作为存储后端；

为了提升查询效率和支持多种查询谓语，我们采用Elasticsearch作为索引后端。

系统架构图

基础数据

58部落用户数据以Userid为节点，User与User之间关注、点赞等行为作为边存放在Hive中。Graphx构建图Graph需要固定格式，所以使用Spark读取Hive数据，对原始数据类型进行转换。节点由Userid转换为自增Long类型ID，用作图节点ID。User与User关系转换为Edge类型表示节点与节点的边。

度中心性

度中心性在Spark_Graphx上的实现较为简单。Spark Graph提供degrees算法来直接获取每个节点的度中心性，还可以使用outDegrees和inDegrees来获取节点的出度中心性和入度中心性等。节点ID与用户ID关联后得出每个用户中心性指标。

接近中心性

从公式中可以看出计算接近中心性最重要的一步是计算分子：当前节点到所有节点最近距离总和。当前节点到所有节点的最近距离计算可以使用图Graph自带算法包中的ShortesPaths最短路径算法。

ShortesPaths算法底层实现为Pregel模型，执行流程如图：

ShortesPaths利用的是Dijkstra求解最短路径算法。InitialMsg初始化一个Map先将节点最短距离设为0。随后使用自定义的函数用来接收消息（vertex Program）、计算消息（Send Message）、合并消息（Merge Message），迭代计算，直到没有新的消息发送。具体操作为：选取一个距离源点s距离最短的顶点k，把k加入s中，该选定的距离就是k到s的最短路径长度。以k为新考虑的中间点，若从源点s到其他节点u的距离（经过点k）比原来距离（不经过点k）短，则修改顶点s的距离值。重复以上步骤直到所有顶点都判断完成。

从上面可以看出ShortesPaths计算最短路径需要存储源点和所有节点的中间信息用以判断。在大数据量情况下很容易导致内存占用过大，OOM等问题，最后导致程序运行失败。对此我们参考《A Graph-theoretic perspective on centrality》中对中心性的扩展和分类，其中提到可以选取部分关键节点，用所有节点到关键节点的最短距离来替代到所有节点的最短距离。在计算过程中只需要保存这部分关键节点的信息，在计算和存储压力上都减少了很大的负担。对应公式可以表示为：

（其中，V表示我们选取的关键节点数量，表示节点i到节点j的最短距离。）

在关键节点的选取上我们保证两大原则：1.节点的位置要相对分散。2.节点要具有代表性。基于这两大原则关键节点选取各58部落分类中度中心性TOP1000的用户节点，保证此种方式计算出来的接近中心性能够提到原先的接近中心性。

改造前后程序运行各个Executor内存使用及GC对比：

中介中心性

当数据量小时使用这种方法可以快速实现中介中心性的计算，但节点数量增多时会导致因为内存压力过大导致任务失败。参考另一种针对中介中心性的计算逻辑，只计算经过该节点的长度为k的最短路径数量。即我们将一个节点在所有节点的最短路径中承担的次数改为计算这个节点在其K步长内节点的最短路径中出现的次数。对应公式可以表示为：

（其中表示的是K步长中节点i和j之间的最短路径的数量，而是最短路径中经过节点k的数量。）

标签判别

58部落用户分为普通用户、作弊用户、中介用户、价值用户等。我们通过识别作弊用户和高价值用户。分别加以惩戒与引导，提升用户体验，提高社区氛围。

作弊用户：定义为疯狂的进行某单一行为，如获取粉丝或为他人点赞。其行为逻辑不符合正常58部落用户的社交行为。中心性指标表现为度中心性过高，中介中心性和接近中心性过低。

高价值用户：定义为用户经常活跃在多种社交行为上，无论是获取关注还是对他人评论的行为都经常发生。中心性指标表现为度中心性、中介中心性、接近中心性都排名较高。

JanusGraph图数据库构建

图数据schema设计

• Node Label：用户（User）
• Edge Label：关注（FOLLOW）、点赞（LIKE）、评论（COMMENT）
• Node Properties：node_id、age、name、degree、closeness、betweenness等
• Edge Properties：date、values等

JanusGraph批量导入

• 升级janusgraph版本
• 支持字符串类型的node_id等

• 直连hbase和Elasticsearch，避免使用janusgraph server进行http提交数据
• 事务批量提交，解决无法一次向janusgraph server提交过多数据问题
• 多worker并行写入，速度更快
• 支持通过配置文件自动创建Janusgraph schema和index，非常方便。

经过性能对比，使用导入工具的写入速度有了较大的提升

通过对Janusgraph与Spark GraphX结合，实现了58部落价值用户的挖掘应用。随着58部落业务的发展，社交网络关联分析在业务用的应用深度和广度也会随之增加，我们将进一步探索图计算相关算法，优化相关功能，包括社群分析、关系网络分析、链路分析、挖掘用户标签等。满足更多业务需求、提升应用效果。

1、Janusgraph官网（https://docs.janusgraph.org/）

2、Spark官网（http://spark.apache.org/）

3、中心性指标论文（https://www.researchgate.net/publication/222405203_A_Graph-Theoretic_Perspective_on_Centrality）

李天祥，58同城分析与决策支持部数据高级开发工程师

李森淼，58同城分析与决策支持部JAVA高级开发工程师

刘晓龙，58同城分析与决策支持部高级经理

推荐阅读：

单声道录音中的角色识别优化实践

开源 | WPaxos：生产级Paxos算法实现解析

沙龙干货 | 58分布式存储系列专题直播回顾集锦