非流行边的预测 电子科技大学互联网科学中心 朱郁筱 yuxiao-zhu@hotmail.com Roger Kahn.

Presentation on theme: "非流行边的预测 电子科技大学互联网科学中心 朱郁筱 yuxiao-zhu@hotmail.com Roger Kahn."— Presentation transcript:

1 非流行边的预测 电子科技大学互联网科学中心 朱郁筱 Roger Kahn

2 问题描述 如何刻画边的流行性？（popularity） 数学角度 物理角度（乘积动力学） Roger Kahn

3 问题描述 为什么要考虑非流行边？ 实际应用（非流行边的信息量往往更大 ）
化学反应网络 基因调控网络 网络演化的观点（网络成熟后，hub节点趋近于饱和，新出现的连边往往是非流行的） 中国航空网 Roger Kahn

4 基于网络结构的相似性指标 基于相似性——两个节点之间相似性越大，它们之间存在连边的可能性也就越大。分为基于节点属性的相似和基于网络结构的相似。基于网络结构的相似性指标又分为： Node-dependent Indices Common Neighbors (CN) Salton Index Jaccard Index Roger Kahn

5 基于网络结构的相似性指标 Sorensen Index Hub promoted Index (HPI)
Hub Depressed index (HDI) Leicht-Holme-Newman-I (LHN-I) Preferencial Attachment (PA) Roger Kahn

6 基于网络结构的相似性指标 Path-dependent Indices Adamic-Adar (AA)
Resource Allocation (RA) Path-dependent Indices Local Path (LP) ：在CN的基础上考虑了三阶邻居的贡献 A：邻接矩阵 ：自由参数 Roger Kahn

7 基于网络结构的相似性指标 Katz（考虑所有路径数，且对于短路径赋予较大的权重，对长路径赋予较小的权重）
A：邻接矩阵 I ： 单位阵 ：权重衰减因子，为了保证数列的收敛性，要小于邻接矩阵A的最大特征值的倒数 Leicht-Holme-Newman-Ⅱ (LHN-Ⅱ) D ：邻接矩阵A的度矩阵 m : 边的条数 ：矩阵A的最大特征值 : 自由参数 Roger Kahn

8 基于网络结构的相似性指标 1）基于路径的相似性指标表现要好，但是它比基于节点的相似性指标需要的信息量多。 2）两种LHN指标的表现都不理想。
局限性：没有考虑这些指标对流行边和非流行的预测精度差别。 Roger Kahn

9 网络的popularity累积分布

10 网络的PA指数 PA指数： Random(PA): 同等规模随机网络的平均popularity M: 网络边的条数
N M C r H <d> <k> PA Datasets USAir PB Celegans NetScience

11 边的预测精度随popularity的变化
测试集中边的预测精度：该边的分数比网络中不存在的边分数高的概率。

12 边的预测精度随popularity的变化
大部分指标预测精度与边的popularity成反比。PA指标最为明显。 相对于其他指标，LHN指标的预测精度随popularity的波动不大，在某些网络中popularity小的边的预测精度反而要高些。 Roger Kahn

13 不同测试集时各指标的表现 数据划分： 根据原始数据计算出各边的popularity，然后对所有边按其popularity进行升序排列，并按所占比例进行5等分。分别从等分区间取出10%作为测试集。P=0.2对应的是[0, 20%]这一区间，P=1对应的是[80%, 100%]。 现象： 1、对于NS数据集，除了PA算法的预测精度与测试集中平均popularity呈正比例关系外，其他算法的预测精度都只是随P的增加有很小的波动。（NS网络的H值比较小） 2、在PB、CE、USAir三个数据集中，大部分的基于网络结构的链路预测算法的预测精度与p呈现正比例关系，尤其是PA、CN、AA、RA、LP。 3、相对于其他算法，LHN算法对popular边以及unpopular边的预测精度相差不大，有时候还会出现预测精度随P的增加还有所下降的情况。

14 不同测试集时各指标的表现 1、对于NS数据集，预测精度都只是随P的增加有很小的波动（PA指标除外）。（NS网络的H值比较小）
2、在PB、CE、USAir三个数据集中，大部分指标的预测精度与p呈现正比例关系，尤其是PA、CN、AA、RA、LP。 3、LHN的预测精度随p变化很小，有时候还会出现预测精度随P的增加还有所下降的情况。

15 Top-L-popularity Top-L-popularity: 排在前面的L条边的平均的popularity.
USAir、PB、C.elegans、NetScience四个网络中，LHN-I以及LHN-Ⅱ计算出的Top-L-popularity远小于其他指标。L越小，这种差距越明显。CN、PA、AA、RA、LP、Katz的top-100-popularity远远大于LHN指标。 结论： LHN指标更倾向于预测出非流行边。

16 Top-L-popularity 表：基于网络结构的相似性指标（PB）

17 调节节点度的影响 引入自由参数a a= -1: LHN-I指标 a=-0.5：salton a=0：CN
1）最优的参数值a大体上 与P成正比 2) 测试集边比较流行时， 最优参数a很接近0. 3) 最优参数的选取对网络 的依赖性很大。

18 下步的工作 现有的基于相似性的指标大都更倾向于预测流行的连边。LHN指标的对非流行边的预测精度比较好。但是LHN总体上的表现又不那么令人满意，能否设计一种对流行边和非流行边预测精度都比较高的相似性指标？

19 THANK YOU FOR YOUR TIME Roger Kahn