概述
AA 指标(Adamic-Adar Index)是一种基于网络结构信息定义的节点相似性指标,这是其与杰卡德相似度(半结构信息)的区别。AA 指标用两个节点的共同邻居节点的权重和作为这两个节点的相似度,该指标的概念由 Lada A. Adamic 和 Eytan Adar 于 2003 年提出。
相关资料如下:
- L.A. Adamic, E. Adar, Friends and Neighbors on the Web (2003)
- Adamic-Adar Index
基本概念
节点权重
AA 指标中,节点 x
的权重 w(x)
为 x
的邻居集合 N(x)
的模取以 10 为底的对数后再取倒数:
下图中黄色节点的权重为 1/(log4) = 1.6610
,绿色节点的权重为 1/(log3) = 2.0959
。
AA 指标
AA 指标用两个节点共同邻居的权重和描述它们的紧密度,计算公式为:
其中,N(x)
和 N(y)
分别是节点 x
和 y
的邻居集合,u
是节点 x
、y
的共同邻居。AA(x,y)
值越大,代表两个节点越紧密;如果值为 0 意味着两个节点不紧密。
仍以上图为例,蓝色、红色节点的 AA 相似度为黄色、绿色节点的权重和,即 1/(log4) + 1/(log3) = 3.7569
。
特殊处理
孤点、不连通图
孤点与图中任何其它节点之间没有边,本算法不计算孤点与任何节点的 AA 指标,也不计算处于不同连通分量中的两个节点的 AA 指标。
自环边
在计算邻居节点时,本算法会忽略所有自环边。
有向边
对于有向边,本算法会忽略边的方向,按照无向边进行计算。
结果和统计值
以下面的图为例,运行本算法:
算法结果:计算 3 号点与其他每个节点的 AA 指标,返回 node1
、node2
、num
三列
node1 | node2 | num |
---|---|---|
3 | 1 | 1.660964047443681 |
3 | 2 | 1.660964047443681 |
3 | 4 | 3.7568673217330657 |
3 | 5 | 3.321928094887362 |
3 | 6 | 1.660964047443681 |
3 | 7 | 2.095903274289385 |
算法统计值:无
命令和参数配置
- 命令:
algo(topological_link_prediction)
params()
参数配置项如下:
名称 |
类型 |
默认值 |
规范 | 描述 |
---|---|---|---|---|
ids 或 uuids | []_id 或 []_uuid |
/ | 必填 | 待计算的第一组节点的 ID 或 UUID;第一组的每个节点与第二组的每个节点组成点对进行计算 |
ids2 或 uuids2 | []_id 或 []_uuid |
/ | 必填 | 待计算的第二组节点的 ID 或 UUID;第一组的每个节点与第二组的每个节点组成点对进行计算 |
type | string | Adamic_Adar | Adamic_Adar 或 Common_Neighbors 或 Preferential_Attachment 或 Resource_Allocation 或 Total_Neighbors | 节点对紧密度度量方法,Adamic_Adar 或忽略代表 AA 指标,Common_Neighbors 代表共同邻居,Preferential_Attachment 代表优先连接,Resource_Allocation 代表资源分配,Total_Neighbors 代表总邻居数 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename | node1 ,node2 ,num |
示例:计算 3 号点和其他所有点的 AA 指标,将算法结果回写至名为 aa 的文件
algo(topological_link_prediction).params({
uuids: [3],
uuids2: [1,2,4,5,6,7]
}).write({
file:{
filename: "aa"
}
})
2. 属性回写
算法不支持属性回写。
3. 统计回写
算法无统计值。
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNodePair | 点对的紧密度 | node1 , node2 , num |
示例:计算 3 号点和 4 号点的 AA 指标,将算法结果定义为别名 similarity 并返回
algo(topological_link_prediction).params({
uuids: [3],
uuids2: [4],
type: "Adamic_Adar"
}) as similarity
return similarity
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNodePair | 点对的紧密度 | node1 , node2 , num |
示例:分别计算 1 号点和 5、6、7 号点的 AA 指标,返回结果并按照紧密度降序排列
algo(topological_link_prediction).params({
uuids: [1],
uuids2: [5,6,7],
type: "Adamic_Adar"
}).stream() as com
return com order by com.num desc
实时统计
算法无统计值。