HDC 分布式
概述
PageRank（网页排名）最初是在万维网（WWW）的背景下提出的，它利用WWW的链接结构来产生全局、客观的网页“重要性”排名供搜索引擎使用。该算法由Google联合创始人Larry Page和Sergey Brin于1997-1998年提出：
- L. Page, S Brin, R. Motwani, T. Winograd, The PageRank Citation Ranking: Bringing Order to The Web (1998)
随着技术的发展与大量关联性数据的产生，PageRank也被许多其他领域采用。
基本概念
链接结构与PageRank
在WWW中，网页中包含的超文本在网页之间创建链接。每个网页（节点）都可以有一些前链（通过出边连接）和后链（通过入边连接）。在下图中，A和B是C的后链，D是C的前链。
不同网页在后链数量方面差异很大。在自然状态下，那些重要、权威或高质量的网页会获得更多或更重要的后链。
PageRank的核心思想是：一个网页的后链的排名总和越高，则该网页的排名就越高。这同时涵盖了两种情况，一是网页有大量的后链，二是网页的后链尽管数量不多但排名很高。
排名传递
所有网页的排名（分值）是以递归的方式计算的，所有网页的初始排名分值可以是任意的，然后进行迭代计算直至收敛。在每次迭代中，每个网页均匀地将其自身的排名分值传递给其所有的前链；同时，每个网页都从其所有后链获得排名分值。因此，网页u在一次迭代后的排名分值为：
其中Bu是网页u的后链集合。
以下是一组网页间的排名传递达到稳定的状态：
阻尼系数
考虑以下几种类型的网页：
- 没有后链的网页。它们获得的排名是0，但它们仍需被浏览到。
- 没有前链的网页。它们的排名分值会从系统中消失。
- 对于一组网页，它们只指向组内的网页，而不指向任何组外的网页。
为了克服这些问题，我们引入阻尼系数（Damping Factor），其值介于0和1之间。它为每个网页提供一个保底排名分值，同时削弱从后链传递过来的排名分值。一次迭代后网页u的排名变为：
其中d是阻尼系数。例如，当d=0.7时，如果一个网页从后链接收到的排名总和为8，则该网页在本轮的排名为0.7*8 + (1-0.7) = 5.9。
阻尼系数也可以理解为浏览者随机跳转到不是当前网页的前链之一的其他网页的概率。
特殊说明
- 孤点的排名将为(1-d)。
- 自环边被视为一条入边和一条出边，网页会通过自环边会将一部分排名传递给自身。有大量自环边的图通常需要较多次的迭代才能趋于稳定。
示例图集
创建示例图集：
// 在空图集中逐行运行以下语句
create().node_schema("account").edge_schema("follow")
insert().into(@account).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}, {_id:"H"}, {_id:"I"}, {_id:"J"}, {_id:"K"}, {_id:"L"}, {_id:"M"}, {_id:"N"}])
insert().into(@follow).edges([{_from:"A", _to:"E"}, {_from:"B", _to:"E"}, {_from:"C", _to:"A"}, {_from:"C", _to:"H"}, {_from:"D", _to:"J"}, {_from:"E", _to:"G"}, {_from:"E", _to:"G"},{_from:"E", _to:"I"}, {_from:"E", _to:"N"}, {_from:"F", _to:"L"}, {_from:"F", _to:"B"}, {_from:"H", _to:"C"}, {_from:"H", _to:"E"}, {_from:"I", _to:"E"}, {_from:"J", _to:"E"}, {_from:"K", _to:"E"}, {_from:"K", _to:"M"}, {_from:"L", _to:"E"}, {_from:"L", _to:"F"}, {_from:"L", _to:"N"}, {_from:"M", _to:"E"}, {_from:"N", _to:"F"}])
在HDC图集上运行算法
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_pagerank：
CALL hdc.graph.create("hdc-server-1", "hdc_pagerank", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_pagerank", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名：page_rank
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
init_value |
Float | >0 | 0.2 |
是 | 所有点的初始排名 |
loop_num |
Integer | ≥1 | 5 |
是 | 最大迭代轮数。算法将在完成所有轮次后停止 |
damping |
Float | (0,1) | 0.8 |
是 | 阻尼系数 |
weaken |
Integer | 1, 2 |
1 |
是 | 设置为1时计算PageRank；设置为2时计算ArticleRank |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据rank分值对结果排序 |
文件回写
CALL algo.page_rank.write("hdc_pagerank", {
params: {
return_id_uuid: "id",
init_value: 1,
loop_num: 50,
damping: 0.8,
weaken: 1,
order: 'desc'
},
return_params: {
file: {
filename: "rank"
}
}
})
algo(page_rank).params({
projection: "hdc_pagerank",
return_id_uuid: "id",
init_value: 1,
loop_num: 50,
damping: 0.8,
weaken: 1,
order: 'desc'
}).write({
file: {
filename: "rank"
}
})
结果：
_id,rank
E,2.3906
G,1.15624
F,1.03774
N,0.842146
I,0.67812
B,0.615097
L,0.615097
J,0.36
C,0.333333
A,0.333333
H,0.333333
M,0.28
K,0.2
D,0.2
数据库回写
将结果中的rank值写入指定点属性。该属性类型为float。
CALL algo.page_rank.write("hdc_pagerank", {
params: {
loop_num: 50,
weaken: 1
},
return_params: {
db: {
property: "rank"
}
}
})
algo(page_rank).params({
projection: "hdc_pagerank",
loop_num: 50,
weaken: 1
}).write({
db:{
property: 'rank'
}
})
完整返回
CALL algo.page_rank("hdc_pagerank", {
params: {
return_id_uuid: "id",
init_value: 1,
loop_num: 50,
damping: 0.8,
weaken: 1,
order: 'desc',
limit: 5
},
return_params: {}
}) YIELD PR
RETURN PR
exec{
algo(page_rank).params({
return_id_uuid: "id",
init_value: 1,
loop_num: 50,
damping: 0.8,
weaken: 1,
order: 'desc',
limit: 5
}) as PR
return PR
} on hdc_pagerank
结果：
| _id | rank |
|---|---|
| E | 2.390599 |
| G | 1.15624 |
| F | 1.037742 |
| N | 0.842146 |
| I | 0.67812 |
流式返回
CALL algo.page_rank("hdc_pagerank", {
params: {
return_id_uuid: "id",
loop_num: 50,
damping: 0.8,
weaken: 1,
order: 'desc',
limit: 5
},
return_params: {
stream: {}
}
}) YIELD PR
RETURN PR
exec{
algo(page_rank).params({
return_id_uuid: "id",
loop_num: 50,
damping: 0.8,
weaken: 1,
order: 'desc',
limit: 5
}).stream() as PR
return PR
} on hdc_pagerank
结果：
| _id | rank |
|---|---|
| E | 2.390599 |
| G | 1.15624 |
| F | 1.037742 |
| N | 0.842146 |
| I | 0.67812 |
在分布式投影上运行算法
创建分布式投影
将图集全部投影到shard服务器上并命名为dist_pagerank：
create().projection("dist_pagerank", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true
})
参数
算法名：page_rank
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
init_value |
Float | >0 | 0.2 |
是 | 所有点的初始排名 |
loop_num |
Integer | ≥1 | 10 |
是 | 最大迭代轮数。算法将在完成所有轮次后停止 |
damping |
Float | (0,1) | 0.8 |
是 | 阻尼系数 |
weaken |
Integer | 1, 2 |
1 |
是 | 设置为1时计算PageRank；设置为2时计算ArticleRank |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据rank分值对结果排序 |
文件回写
CALL algo.page_rank.write("dist_pagerank", {
params: {
init_value: 1,
loop_num: 50,
damping: 0.8,
weaken: 1,
order: "desc"
},
return_params: {
file: {
filename: "rank"
}
}
})
algo(page_rank).params({
projection: "dist_pagerank",
init_value: 1,
loop_num: 50,
damping: 0.8,
weaken: 1,
order: "desc"
}).write({
file: {
filename: "rank"
}
})
结果：
_id,rank
E,2.4451734081316898184
G,1.1753836278518499103
F,1.072201237069960067
N,0.86041240546502095743
I,0.68769181392592604318
B,0.62905439446913602453
L,0.62905439446913602453
J,0.35999999999999998668
H,0.33350809599999997612
A,0.33350809599999997612
C,0.33350809599999997612
M,0.28000000000000002665
D,0.2000000000000000111
K,0.2000000000000000111
数据库回写
将结果中的rank值写入指定点属性。该属性类型为double。
CALL algo.page_rank.write("dist_pagerank", {
params: {
loop_num: 50,
weaken: 1
},
return_params: {
db: {
property: "rank"
}
}
})
algo(page_rank).params({
projection: "dist_pagerank",
loop_num: 50,
weaken: 1
}).write({
db:{
property: 'rank'
}
})