图分析在真实世界中有广泛的用处。许多算法比如社区发现,路径连通性,中心性算法都被证明在许多商业中非常有用。
GraphScope 内置了一系列算法,使得用户可以方便的在图数据上做分析。
这个教程展示了如何使用内置算法来完成图分析任务。
# Install graphscope package if you are NOT in the Playground
!pip3 install graphscope
首先,我们需要载入一张属性图。
这里我们从 Gnutella peer-to-peer network, August 31 2002 使用 peer-to-peer network 数据集,并在此基础上为点和边加入了属性。
# Import the graphscope module.
import graphscope
graphscope.set_option(show_log=False) # enable logging
# Load p2p network dataset
from graphscope.dataset import load_p2p_network
graph = load_p2p_network(directed=False)
来看一下图的数据模型。
print(graph.schema)
如上所示,我们载入了一张属性图,点标签为 "host",有两个属性 ("weight" 和 "id"),边标签为 "connect", 有三个属性,分别为 ("src_label_id", "dst_label_id", "dist")。
许多图分析算法都只能查询 简单图, 在这里我们定义 简单图 为只包含一种点和一种边,且点和边最多只有一个属性。
GraphScope
提供了一个函数 project
来将属性图投影为简单图,我们可以选择某一种点和边,以及其一个或零个属性,来获得属性图的一个 投影。
simple_graph = graph.project(vertices={"host": []}, edges={"connect": ["dist"]})
在接下来的部分,我们将运行几个算法,并查看结果。
单源最短路径算法(Single Source Shortest Path,接下来将以 sssp
代称),需要两个参数,第一个参数是 graph
,第二个参数是查询的出发点 src
。
在这里,我们将查询从 ID 为 6 的点出发到所有点的最短路径长度。
在后端,GraphScope 会生成一个兼容被查询的图的算法,编译为一个动态链接库。额外的 GraphScope 会对类型做一些检查,比如,在这里 sssp
算法要求边有一个 int
或 double
的属性作为距离。
第一次编译动态链接库时需要一些时间,但是对于同一个算法,这一步在同样类型的图上只会进行一次。
from graphscope import sssp
sssp_context = sssp(simple_graph, src=6)
完成计算后,计算结果分布式的存储到了集群上 vineyard
的实例上。
算法会返回一个 Context
对象,包含若干种取回结果的方法。
关于 Context
的更多信息,请参照 Context
在这里,结果表示从起始点出发到所有点的最短路径,我们使用返回的对象来取得一部分结果,以及取回点ID一并展示。
sssp_context.to_dataframe(
selector={"id": "v.id", "dist": "r"}, vertex_range={"begin": 1, "end": 10}
).sort_values(by="id")
另外, 我们还可以将结果输出到客户端的机器的文件系统上。
sssp_context.output_to_client("./sssp_result.csv", selector={"id": "v.id", "dist": "r"})
查看一下输出的文件。
!head ./sssp_result.csv
PageRank 是非常著名的一个图分析算法,让我们来看一下如何仅用两行计算 PageRank。
from graphscope import pagerank
pr_context = pagerank(simple_graph, delta=0.85, max_round=10)
pr_context.to_dataframe(
selector={"id": "v.id", "rank": "r"}, vertex_range={"begin": 1, "end": 10}
).sort_values(by="id")
输出结果到本地。
pr_context.output_to_client(
"./pagerank_result.csv", selector={"id": "v.id", "rank": "r"}
)
在图理论中,无向图中的一个分量,有时被称为一个联通分量,代表一个任意两个节点之间都有边的子图,且这个子图没有指向子图外的点的边。
弱联通分量算法(Weakly Connected Components, WCC)计算每个点所属的联通分量。
from graphscope import wcc
wcc_context = wcc(simple_graph)
wcc_context.to_dataframe(
selector={"id": "v.id", "cc": "r"}, vertex_range={"begin": 1, "end": 10}
).sort_values(by="id")
请查阅 Builtin algorithms 来获得更多的内置算法的信息,并欢迎试用更多的算法。