4.1 rank API 概述

HugeGraphServer 除了上一节提到的遍历(traverser)方法,还提供了一类专门做推荐的方法,我们称为rank API, 可在图中为一个点推荐与其关系密切的其它点。

4.2 rank API 详解

4.2.1 Personal Rank API

4.2.1.0 数据准备

这里以MovieLens的 1M 数据集为例,用户需 下载该数据集,然后使用 HugeGraph-Loader 导入到 HugeGraph 中,为简单起见,数据中顶点 user 和 movie 的属性都忽略,仅使用 id 字段即可,边 rating 的具体评分值也忽略。loader 使用的元数据 文件和输入源映射文件内容如下:

  1. ////////////////////////////////////////////////////////////
  2. // UserID::Gender::Age::Occupation::Zip-code
  3. // MovieID::Title::Genres
  4. // UserID::MovieID::Rating::Timestamp
  5. ////////////////////////////////////////////////////////////
  6. // Define schema
  7. schema.propertyKey("id").asInt().ifNotExist().create();
  8. schema.propertyKey("rate").asInt().ifNotExist().create();
  9. schema.vertexLabel("user")
  10. .properties("id")
  11. .primaryKeys("id")
  12. .ifNotExist()
  13. .create();
  14. schema.vertexLabel("movie")
  15. .properties("id")
  16. .primaryKeys("id")
  17. .ifNotExist()
  18. .create();
  19. schema.edgeLabel("rating")
  20. .sourceLabel("user")
  21. .targetLabel("movie")
  22. .properties("rate")
  23. .ifNotExist()
  24. .create();
  1. {
  2. "vertices": [
  3. {
  4. "label": "user",
  5. "input": {
  6. "type": "file",
  7. "path": "users.dat",
  8. "format": "TEXT",
  9. "delimiter": "::",
  10. "header": ["UserID", "Gender", "Age", "Occupation", "Zip-code"]
  11. },
  12. "ignored": ["Gender", "Age", "Occupation", "Zip-code"],
  13. "mapping": {
  14. "UserID": "id"
  15. }
  16. },
  17. {
  18. "label": "movie",
  19. "input": {
  20. "type": "file",
  21. "path": "movies.dat",
  22. "format": "TEXT",
  23. "delimiter": "::",
  24. "header": ["MovieID", "Title", "Genres"]
  25. },
  26. "ignored": ["Title", "Genres"],
  27. "mapping": {
  28. "MovieID": "id"
  29. }
  30. }
  31. ],
  32. "edges": [
  33. {
  34. "label": "rating",
  35. "source": ["UserID"],
  36. "target": ["MovieID"],
  37. "input": {
  38. "type": "file",
  39. "path": "ratings.dat",
  40. "format": "TEXT",
  41. "delimiter": "::",
  42. "header": ["UserID", "MovieID", "Rating", "Timestamp"]
  43. },
  44. "ignored": ["Timestamp"],
  45. "mapping": {
  46. "UserID": "id",
  47. "MovieID": "id",
  48. "Rating": "rate"
  49. }
  50. }
  51. ]
  52. }

注意将映射文件中input.path的值修改为自己本地的路径。

4.2.1.1 功能介绍

适用于二分图,给出所有源顶点相关的其他顶点及其相关性组成的列表。

二分图:也称二部图,是图论里的一种特殊模型,也是一种特殊的网络流。其最大的特点在于,可以将图里的顶点分为两个集合,两个集合之间的点有边相连,但集合内的点之间没有直接关联。

假设有一个用户和物品的二分图,基于随机游走的 PersonalRank 算法步骤如下:

  1. 选定一个起点用户 u,其初始权重为 1.0,从 Vu 开始游走(有 alpha 的概率走到邻居点,1 - alpha 的概率停留);
  2. 如果决定游走: 2.1. 那就从当前节点的邻居节点中按照均匀分布随机选择一个,并且按照均匀分布划分权重值; 2.2. 给源顶点补偿权重 1 - alpha; 2.3. 重复步骤2;
  3. 达到一定步数后收敛,得到推荐列表。
Params
  • source: 源顶点 id,必填项
  • label: 边的类型,必须是连接两类不同顶点的边,必填项
  • alpha:每轮迭代时从某个点往外走的概率,与 PageRank 算法中的 alpha 类似,必填项,取值区间为 (0, 1]
  • max_degree: 查询过程中,单个顶点遍历的最大邻接边数目,选填项,默认为 10000
  • max_depth: 迭代次数,必填项,取值区间为 (0, 50]
  • with_label:筛选结果中保留哪些结果,选填项,可选值为 [SAME_LABEL, OTHER_LABEL, BOTH_LABEL], 默认为 BOTH_LABEL
    • SAME_LABEL:保留与源顶点相同类别的顶点
    • OTHER_LABEL:保留与源顶点不同类别(二分图的另一端)的顶点
    • BOTH_LABEL:保留与源顶点相同和相反类别的顶点
  • limit: 返回的顶点的最大数目,选填项,默认为 10000000
  • sorted:返回的结果是否根据 rank 排序,为 true 时降序排列,反之不排序,选填项,默认为 true
4.2.1.2 使用方法
Method & Url
  1. POST http://localhost:8080/graphs/hugegraph/traversers/personalrank
Request Body
  1. {
  2. "source": "1:1",
  3. "label": "rating",
  4. "alpha": 0.6,
  5. "max_depth": 15,
  6. "with_label": "OTHER_LABEL",
  7. "sorted": true,
  8. "limit": 10
  9. }
Response Status
  1. 200
Response Body
  1. {
  2. "2:2858": 0.0005014026017816927,
  3. "2:1196": 0.0004336708357653617,
  4. "2:1210": 0.0004128083140214213,
  5. "2:593": 0.00038117341069881513,
  6. "2:480": 0.00037005373269728036,
  7. "2:1198": 0.000366641614652057,
  8. "2:2396": 0.0003622362410538888,
  9. "2:2571": 0.0003593312457300953,
  10. "2:589": 0.00035922123055598566,
  11. "2:110": 0.0003466135844390885
  12. }
4.2.1.3 适用场景

两类不同顶点连接形成的二分图中,给某个点推荐相关性最高的其他顶点,例如:

  • 商品推荐中,查找最应该给某人推荐的商品列表

4.2.2 Neighbor Rank API

4.2.2.0 数据准备
  1. public class Loader {
  2. public static void main(String[] args) {
  3. HugeClient client = new HugeClient("http://127.0.0.1:8080", "hugegraph");
  4. SchemaManager schema = client.schema();
  5. schema.propertyKey("name").asText().ifNotExist().create();
  6. schema.vertexLabel("person")
  7. .properties("name")
  8. .useCustomizeStringId()
  9. .ifNotExist()
  10. .create();
  11. schema.vertexLabel("movie")
  12. .properties("name")
  13. .useCustomizeStringId()
  14. .ifNotExist()
  15. .create();
  16. schema.edgeLabel("follow")
  17. .sourceLabel("person")
  18. .targetLabel("person")
  19. .ifNotExist()
  20. .create();
  21. schema.edgeLabel("like")
  22. .sourceLabel("person")
  23. .targetLabel("movie")
  24. .ifNotExist()
  25. .create();
  26. schema.edgeLabel("directedBy")
  27. .sourceLabel("movie")
  28. .targetLabel("person")
  29. .ifNotExist()
  30. .create();
  31. GraphManager graph = client.graph();
  32. Vertex O = graph.addVertex(T.label, "person", T.id, "O", "name", "O");
  33. Vertex A = graph.addVertex(T.label, "person", T.id, "A", "name", "A");
  34. Vertex B = graph.addVertex(T.label, "person", T.id, "B", "name", "B");
  35. Vertex C = graph.addVertex(T.label, "person", T.id, "C", "name", "C");
  36. Vertex D = graph.addVertex(T.label, "person", T.id, "D", "name", "D");
  37. Vertex E = graph.addVertex(T.label, "movie", T.id, "E", "name", "E");
  38. Vertex F = graph.addVertex(T.label, "movie", T.id, "F", "name", "F");
  39. Vertex G = graph.addVertex(T.label, "movie", T.id, "G", "name", "G");
  40. Vertex H = graph.addVertex(T.label, "movie", T.id, "H", "name", "H");
  41. Vertex I = graph.addVertex(T.label, "movie", T.id, "I", "name", "I");
  42. Vertex J = graph.addVertex(T.label, "movie", T.id, "J", "name", "J");
  43. Vertex K = graph.addVertex(T.label, "person", T.id, "K", "name", "K");
  44. Vertex L = graph.addVertex(T.label, "person", T.id, "L", "name", "L");
  45. Vertex M = graph.addVertex(T.label, "person", T.id, "M", "name", "M");
  46. O.addEdge("follow", A);
  47. O.addEdge("follow", B);
  48. O.addEdge("follow", C);
  49. D.addEdge("follow", O);
  50. A.addEdge("follow", B);
  51. A.addEdge("like", E);
  52. A.addEdge("like", F);
  53. B.addEdge("like", G);
  54. B.addEdge("like", H);
  55. C.addEdge("like", I);
  56. C.addEdge("like", J);
  57. E.addEdge("directedBy", K);
  58. F.addEdge("directedBy", B);
  59. F.addEdge("directedBy", L);
  60. G.addEdge("directedBy", M);
  61. }
  62. }
4.2.2.1 功能介绍

在一般图结构中,找出每一层与给定起点相关性最高的前 N 个顶点及其相关度,用图的语义理解就是:从起点往外走, 走到各层各个顶点的概率。

Params
  • source: 源顶点 id,必填项
  • alpha:每轮迭代时从某个点往外走的概率,与 PageRank 算法中的 alpha 类似,必填项,取值区间为 (0, 1]
  • steps: 表示从起始顶点走过的路径规则,是一组 Step 的列表,每个 Step 对应结果中的一层,必填项。每个 Step 的结构如下:
    • direction:表示边的方向(OUT, IN, BOTH),默认是 BOTH
    • labels:边的类型列表,多个边类型取并集
    • max_degree:查询过程中,单个顶点遍历的最大邻接边数目,默认为 10000 (注: 0.12版之前 step 内仅支持 degree 作为参数名, 0.12开始统一使用 max_degree, 并向下兼容 degree 写法)
    • top:在结果中每一层只保留权重最高的前 N 个结果,默认为 100,最大值为 1000
  • capacity: 遍历过程中最大的访问的顶点数目,选填项,默认为10000000
4.2.2.2 使用方法
Method & Url
  1. POST http://localhost:8080/graphs/hugegraph/traversers/neighborrank
Request Body
  1. {
  2. "source":"O",
  3. "steps":[
  4. {
  5. "direction":"OUT",
  6. "labels":[
  7. "follow"
  8. ],
  9. "max_degree":-1,
  10. "top":100
  11. },
  12. {
  13. "direction":"OUT",
  14. "labels":[
  15. "follow",
  16. "like"
  17. ],
  18. "max_degree":-1,
  19. "top":100
  20. },
  21. {
  22. "direction":"OUT",
  23. "labels":[
  24. "directedBy"
  25. ],
  26. "max_degree":-1,
  27. "top":100
  28. }
  29. ],
  30. "alpha":0.9,
  31. "capacity":-1
  32. }
Response Status
  1. 200
Response Body
  1. {
  2. "ranks": [
  3. {
  4. "O": 1
  5. },
  6. {
  7. "B": 0.4305,
  8. "A": 0.3,
  9. "C": 0.3
  10. },
  11. {
  12. "G": 0.17550000000000002,
  13. "H": 0.17550000000000002,
  14. "I": 0.135,
  15. "J": 0.135,
  16. "E": 0.09000000000000001,
  17. "F": 0.09000000000000001
  18. },
  19. {
  20. "M": 0.15795,
  21. "K": 0.08100000000000002,
  22. "L": 0.04050000000000001
  23. }
  24. ]
  25. }
4.2.2.3 适用场景

为给定的起点在不同的层中找到最应该推荐的顶点。

  • 比如:在观众、朋友、电影、导演的四层图结构中,根据某个观众的朋友们喜欢的电影,为这个观众推荐电影;或者根据这些电影是谁拍的,为其推荐导演。