关于图数据库:GraphX-在图数据库-Nebula-Graph-的图计算实践

不同起源的异构数据间存在着千头万绪的关联，这种数据之间暗藏的关联关系和网络结构个性对于数据分析至关重要，图计算就是以图作为数据模型来表白问题并予以解决的过程。

一、背景

随着网络信息技术的飞速发展，数据逐步向多源异构化方向倒退，且不同起源的异构数据之间也存在的千头万绪的关联，这种数据之间暗藏的关联关系和网络结构个性对于数据分析至关重要。但传统关系型数据库在剖析大规模数据关联个性时存在性能缺点、表白无限等问题，因而有着更弱小表达能力的图数据受到业界极大器重，图计算就是以图作为数据模型来表白问题并予以解决的过程。图能够交融多源多类型的数据，除了能够展现数据动态根底个性之外，还可通过图计算展现暗藏在数据之间的图构造个性和点对关联关系，成为社交网络、举荐零碎、常识图谱、金融风控、网络安全、文本检索等畛域重要的剖析伎俩。

二、算法利用

为了撑持大规模图计算的业务需要，Nebula Graph 基于 GraphX 提供了 PageRank 和 Louvain 社区发现的图计算算法，容许用户通过提交 Spark 工作的模式执行算法利用。此外，用户也能够通过 Spark Connector 编写 Spark 程序调用 GraphX 自带的其余图算法，如 LabelPropagation、ConnectedComponent 等。

PageRank

PageRank 是谷歌提出的用于解决链接剖析中网页排名问题的算法，目标是为了对互联网中数以亿计的网页进行排名。

PageRank 简介

美国斯坦福大学的 Larry Page 和 Sergey Brin 在钻研网页排序问题时采纳学术界评判论文重要性的办法，即看论文的援用量以及援用该论文的论文品质，对应于网页的重要性有两个假如：

1. 数量假如：如果一个网页 A 被很多其余网页链接到，则该网页比拟重要；
2. 品质假如：如果一个很重要的网页链接到网页 A，则该网页的重要性会被进步。

并基于这两个假如提出 PageRank 算法。

PageRank 利用场景

社交利用的类似度内容举荐

在对微博、微信等社交平台进行社交网络分析时，能够基于 PageRank 算法依据用户通常浏览的信息以及停留时间实现基于用户的类似度的内容举荐；

剖析用户社交影响力

在社交网络分析时依据用户的 PageRank 值进行用户影响力剖析；

文献重要性钻研

依据文献的 PageRank 值评判该文献的品质，PageRank 算法就是基于评判文献品质的想法来实现设计。

此外 PageRank 在数据分析和开掘中也有很多的利用。

算法思路

GraphX 的 PageRank 算法是基于 Pregel 计算模型的，该算法流程包含 3 步骤：

1. 为图中每个节点（网页）设置一个同样的初始 PageRank 值；
2. 第一次迭代：沿边发送音讯，每个节点收到所有关联边上对点的信息，失去一个新的 PageRank 值；
3. 第二次迭代：用这组新的 PageRank 按不同算法模式对应的公式造成节点本人新的 PageRank。

Louvain 社区发现

Louvain 是用来进行社会网络开掘的社区发现算法，属于图的聚类算法。

Louvain 算法介绍

Louvain 是基于模块度（Modularity）的社区发现算法，通过模块度来掂量一个社区的严密水平。如果一个节点退出到某一社区中会使得该社区的模块度相比其余社区有最大水平的减少，则该节点就该当属于该社区。如果退出其它社区后没有使其模块度减少，则留在本人以后社区中。

模块度

模块度公式

模块度 Q 的物理意义：社区内节点的连边数与随机状况下的边数之差，定义函数如下：

其中

：节点 i 和节点 j 之间边的权重
：所有与节点 i 相连的边的权重之和
：节点 i 所属的社区
：图中所有边的权重之和

模块度公式变形

在此公式中，只有节点 i 和节点 j 属于同一社区，公式才有意义，所以该公式是掂量的某一社区内的紧密度。对于该公式的简化变形如下：

示意：社区 c 内的边的权重之和
示意：所有与社区 c 内节点相连的边的权重之和（因为 i 属于社区 c）包含社区内节点与节点 i 的边和社区外节点与节点 i 的边。
示意：所有与社区 c 内节点相连的边的权重之和（因为 j 属于社区 c）包含社区内节点与节点 j 的边和社区外节点与节点 j 的边。
代替 和 。（即社区 c 内边权重和 + 社区 c 与其余社区连边的权重和）

求解模块度变动

在 Louvain 算法中不需要求每个社区具体的模块度，只须要比拟社区中退出某个节点之后的模块度变动，所以须要求解 △Q。

将节点 i 调配到某一社区中，社区的模块度变动为：

其中

：社区内所有节点与节点 i 连边权重之和（对应新社区的理论外部权重和乘以 2，因为 对于社区内所有的顶点 i，每条边其实被计算了两次）
：所有与节点 i 相连的边的权重之和
故实现算法时只需要 即可。

Louvain 利用场景

• 金融风控

在金融风控场景中，能够依据用户行为特色进行团伙辨认；

• 社交网络

能够基于网络关系中点对之间关联的广度和强度进行社交网络划分；对简单网络分析、电话网络分析人群之间的分割亲密度；

• 举荐零碎

基于用户兴趣爱好的社区发现，能够依据社区并联合协同过滤等举荐算法进行更准确无效的个性化举荐。

Louvain 算法思路

Louvain 算法包含两个阶段，其流程就是这两个阶段的迭代过程。

阶段一：一直地遍历网络图中的节点，通过比拟节点给每个街坊社区带来的模块度的变动，将单个节点退出到可能使 Modularity 模块度有最大增量的社区中。
（比方节点 v 别离退出到社区 A、B、C 中，使得三个社区的模块度增量为 -1，1，2，则节点 v 最终应该退出到社区 C 中）

阶段二：对第一阶段进行解决，将属于同一社区的顶点合并为一个大的超点从新结构网络图，即一个社区作为图的一个新的节点。此时两个超点之间边的权重是两个超点内所有原始顶点之间相连的边权重之和，即两个社区之间的边权重之和。

上面是对第一二阶段的实例介绍。

​

第一阶段遍历图中节点退出到其所属社区中，失去两头的图，造成四个社区；

第二节点对社区内的节点进行合并成一个超级节点，社区节点有自连边，其权重为社区外部所有节点间相连的边的权重之和的 2 倍，社区之间的边为两个社区间顶点跨社区相连的边的权重之和，如红色社区和浅绿色社区之间通过（8,11）、（10，11）、（10,13）相连，所以两个社区之间边的权重为 3。

注：社区内的权重为所有外部结点之间边权重的两倍，因为 Kin 的概念是社区内所有节点与节点 i 的连边和，在计算某一社区的 Kin 时，实际上每条边都被其两端的顶点计算了一次，一共被计算了两次。

整个 Louvain 算法就是一直迭代第一阶段和第二阶段，直到算法稳固（图的模块度不再变动）或者达到最大迭代次数。

三、算法实际

演示环境

• 三台虚拟机，环境如下：

  • Cpu name：Intel(R) Xeon(R) Platinum 8260M CPU @ 2.30GHz
  • Processors：32
  • CPU Cores：16
  • Memory Size：128G

• 软件环境

  • Spark：spark-2.4.6-bin-hadoop2.7 三个节点集群
  • yarn V2.10.0：三个节点集群
  • Nebula Graph V1.1.0：分布式部署，默认配置

测试数据

1. 创立图空间

CREATE SPACE algoTest(partition_num=100, replica_factor=1);

1. 创立点边 Schema

CREATE TAG PERSON()
CREATE EDGE FRIEND(likeness double);

1. 导入数据

利用 Exchange 工具将数据离线导入 Nebula Graph。

1. 测试后果

Spark 工作的资源分配为 --driver-memory=20G --executor-memory=100G --executor-cores=3

• PageRank 在一亿数据集上的执行工夫为 21min（PageRank 算法执行工夫）
• Louvain 在一亿数据集上的执行工夫为 1.3h（Reader + Louvain 算法执行工夫）

如何应用 Nebula Graph 的算法

1. 下载 nebula-algorithm 我的项目并打成 jar 包

$ git clone git@github.com:vesoft-inc/nebula-java.git
$ cd nebula-java/tools/nebula-algorithm
$ mvn package -DskipTests

1. 配置我的项目中的 src/main/resources/application.conf 

{
  # Spark relation config
  spark: {
    app: {
        # not required, default name is the algorithm that you are going to execute.
        name: PageRank

        # not required
        partitionNum: 12
    }

    master: local

    # not required
    conf: {
        driver-memory: 8g
        executor-memory: 8g
        executor-cores: 1g
        cores-max:6
    }
  }

  # Nebula Graph relation config
  nebula: {
    # metadata server address
    addresses: "127.0.0.1:45500"
    user: root
    pswd: nebula
    space: algoTest
    # partition specified while creating nebula space, if you didn't specified the partition, then it's 100.
    partitionNumber: 100
    # nebula edge type
    labels: ["FRIEND"]

    hasWeight: true
    # if hasWeight is true，then weightCols is required，and weghtCols' order must be corresponding with labels.
    # Noted: the graph algorithm only supports isomorphic graphs,
    #        so the data type of each col in weightCols must be consistent and all numeric types.
    weightCols: [“likeness”]
  }

  algorithm: {# the algorithm that you are going to execute，pick one from [pagerank, louvain]
    executeAlgo: louvain
    # algorithm result path
    path: /tmp

    # pagerank parameter
    pagerank: {
        maxIter: 20
        resetProb: 0.15  # default 0.15

    }

    # louvain parameter
    louvain: {
        maxIter: 20
        internalIter: 10
        tol: 0.5
   }
  }
}

1. 确保用户环境已装置 Spark 并启动 Spark 服务
2. 提交 nebula-algorithm 应用程序：

spark-submit --master xxx --class com.vesoft.nebula.tools.algorithm.Main /your-jar-path/nebula-algorithm-1.0.1.jar -p /your-application.conf-path/application.conf

如果你对上述内容感兴趣，欢送用 nebula-algorithm 试试 ^^

References

• Nebula Graph：https://github.com/vesoft-inc/nebula
• GraphX：https://github.com/apache/spark/tree/master/graphx
• Spark-connector：https://github.com/vesoft-inc/nebula-java/tree/master/tools/nebula-spark
• Exchange：https://github.com/vesoft-inc/nebula-java/blob/master/doc/tools/exchange/ex-ug-toc.md
• nebula-algorithm：https://github.com/vesoft-inc/nebula-java/tree/master/tools/nebula-algorithm

作者有话说：Hi，我是安祺，Nebula Graph 研发工程师，如果你对本文有任何疑难，欢送来论坛和我交换：https://discuss.nebula-graph.com.cn/

举荐浏览

• 用图机器学习摸索 A 股个股相关性变动
• 用 NetworkX + Gephi + Nebula Graph 剖析 < 势力的游戏 > 人物关系（上篇）