Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/adamic_adar/
Documentation version: v5.3.2

# Adamic-Adar 指标

本文介绍 Adamic-Adar 指标算法，并演示如何用 GQL 实现该算法。

## 算法介绍

Adamic-Adar 用共同邻居来判断两个点是否可能相连：共同邻居越多，且这些共同邻居本身连接的点越少，得分越高，表示两者越可能形成链路。

该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。

更多信息，请参见 [Adamic-Adar 指标](https://en.wikipedia.org/wiki/Adamic%E2%80%93Adar_index)。

## 数据模型

为了在 GQL 中实现 Adamic-Adar 指标算法，使用以下数据模型创建图类型：

- 实体由类型为`Node`的点表示，点属性包括`id`和`rating`。
- 实体间关系由类型为`Link`的边表示，边属性包括`weight`。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/adamic_adar/#1_prepare_graph_data)。

## 过程实现[]()

为了计算 Adamic-Adar 指标结果，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)。

关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/adamic_adar/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

- `left_id`：`INT64`类型。 候选链接的第一个点 ID。
- `right_id`：`INT64`类型。 候选链接的第二个点 ID。

此外，在过程内部定义了以下变量：

 | 变量名 | 变量类型 | 描述
 | `aa_score` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 查询点对的累积 Adamic-Adar 分数。
 | `degree` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 用于对数逆权重的每点总度数。
 | `seen_left` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点标志：该点是左侧查询点的邻居。
 | `seen_right` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点标志：该点是右侧查询点的邻居。

以下步骤概述了该过程的逻辑：

1. 计算每个点的（无向）`degree`。
2. 对左侧点，将其所有邻居标记为`seen_left`；对右侧点，标记为`seen_right`。
3. 对每个共同邻居（同时具有`seen_left`和`seen_right`），将`1 / log(degree)`累加到`aa_score`。
4. 返回 Adamic-Adar 得分。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建一个与数据模型匹配的图类型。

````
'''
CREATE GRAPH TYPE IF NOT EXISTS adamic_adar_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/adamic_adar/`：

  - [adamic_adar_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/adamic_adar/adamic_adar_node.csv)：点数据。
  - [adamic_adar_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/adamic_adar/adamic_adar_edge.csv)：边数据。

查看 CSV 内容

adamic_adar_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

adamic_adar_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

3. 

基于图类型创建临时图，并将数据文件加载到临时图中。

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #adamic_adar_graph TYPED adamic_adar_graph_type

````

````
'''
USE #adamic_adar_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/adamic_adar/adamic_adar_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/adamic_adar/adamic_adar_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

导入成功后，在控制台执行以下查询核对点数：

````
'''
USE #adamic_adar_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

`node_count`应为`24`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现 Adamic-Adar 指标算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/adamic_adar/#procedure_implement)。 

````
'''
CREATE OR REPLACE PROCEDURE adamic_adar_score(left_id INT64, right_id INT64)
RETURNS (query_left_id INT64, query_right_id INT64, score DOUBLE)
COMMENT "Compute the Adamic-Adar score between two nodes identified by vertex property id."
AS {
  VALUE aa_score SumAgg<DOUBLE> = 0.0

  NODE VALUE degree SumAgg<INT64> = 0
  NODE VALUE seen_left OrAgg = false
  NODE VALUE seen_right OrAgg = false

  MATCH (s)-[e]-(t)
  PER PATH {
    SET s.@degree += 1
  }

  MATCH (s)-[e]-(n)
  WHERE s.id = left_id
  PER PATH {
    SET n.@seen_left += true
  }

  MATCH (s)-[e]-(n)
  WHERE s.id = right_id
  PER PATH {
    SET n.@seen_right += true
  }

  MATCH (n)
  WHERE n.@seen_left = true
    AND n.@seen_right = true
    AND n.id <> left_id
    AND n.id <> right_id
    AND n.@degree > 1
  PER NODE (n) {
    SET @aa_score += 1.0 / ln(CAST(n.@degree AS DOUBLE))
  }

  RETURN left_id AS query_left_id, right_id AS query_right_id, @aa_score AS score
}
'''

````

### 3. 调用过程[]()

计算点`6`和点`9`的 Adamic-Adar 分数。

````
USE #adamic_adar_graph CALL adamic_adar_score(6, 9) RETURN query_left_id, query_right_id, score

````

返回：

````
+---------------+----------------+--------------------+
| query_left_id | query_right_id | score              |
+---------------+----------------+--------------------+
| 6             | 9              | 1.6743318796537416 |
+---------------+----------------+--------------------+

````

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。