科技创新非流行边的预测

1非流行边的预测电子科技大学互联网科学中心朱郁筱[e-mail]2问题描述如何刻画边的流行性？（popularity）数学角度,11xyxyKkk物理角度（乘积动力学）,(1)(1)xyxyKkk3为什么要考虑非流行边？实际应用（非流行边的信息量往往更大）化学反应网络基因调控网络网络演化的观点（网络成熟后，hub节点趋近于饱和，新出现的连边往往是非流行的）中国航空网问题描述4基于网络结构的相似性指标基于相似性——两个节点之间相似性越大，它们之间存在连边的可能性也就越大。分为基于节点属性的相似和基于网络结构的相似。基于网络结构的相似性指标又分为：|()()|xysxyNode-dependentIndicesCommonNeighbors(CN)SaltonIndexJaccardIndex|()()|()()xyxyskxky|()()||()()|xyxysxy5SorensenIndexHubpromotedIndex(HPI)HubDepressedindex(HDI)Leicht-Holme-Newman-I(LHN-I)PreferencialAttachment(PA)2|()()|()()xyxyskxky()()min{(),()}xyxyskxky()()max{(),()}xyxyskxky()()()()xyxyskxky()()xyskxky基于网络结构的相似性指标6基于网络结构的相似性指标Adamic-Adar(AA)ResourceAllocation(RA)()()1log()xyzxyskz()()1()xyzxyskzPath-dependentIndicesLocalPath(LP)：在CN的基础上考虑了三阶邻居的贡献23SAAA：邻接矩阵：自由参数7基于网络结构的相似性指标Katz（考虑所有路径数，且对于短路径赋予较大的权重，对长路径赋予较小的权重）1112()SmDIAD22331...()SAAAIAI：权重衰减因子，为了保证数列的收敛性，要小于邻接矩阵A的最大特征值的倒数A：邻接矩阵I：单位阵Leicht-Holme-Newman-Ⅱ(LHN-Ⅱ)D：邻接矩阵A的度矩阵m:边的条数：矩阵A的最大特征值:自由参数8基于网络结构的相似性指标1）基于路径的相似性指标表现要好，但是它比基于节点的相似性指标需要的信息量多。2）两种LHN指标的表现都不理想。局限性：没有考虑这些指标对流行边和非流行的预测精度差别。9网络的popularity累积分布00.511.52x10400.51PPopularity0510x10400.51PPopularity020004000600000.51PPopularity0500100000.51PPopularityNetScienceC.elegansPBUSAir10网络的PA指数PA指数：Random(PA):同等规模随机网络的平均popularityM:网络边的条数NMCrHdkPADatasets33221260.749-0.2063.462.4612.8079.9231222167170.361-0.0793.132.5127.3601.96029721480.3080.4543.472.4614.4562.5123799410.798-0.0821.664.934.8237.168USAirPBCelegansNetScience)()1)(1(1,PARandomakkMPAVyxxyyx11边的预测精度随popularity的变化测试集中边的预测精度：该边的分数比网络中不存在的边分数高的概率。0510x10410-5100popularity1-AUC012x10410-5100popularity1-AUC0500100010-5100popularity1-AUC050001000010-5100popularity1-AUCCNC.elegansUSAirNSPBCNCNCN0510x10410-5100popularity1-AUC012x10410-5100popularity1-AUC0500100010-5100popularity1-AUC050001000010-410-2100popularity1-AUCPAC.elegansUSAirNSPBPAPAPA12边的预测精度随popularity的变化0510x10410-410-2100popularity1-AUC012x10410-410-2100popularity1-AUC0500100010-5100popularity1-AUC050001000010-410-2100popularity1-AUCC.elegansUSAirNSPBLHN-1LHN-1LHN-1LHN-10510x10410-410-2100popularity1-AUC012x10410-210-1100popularity1-AUC0500100010-410-2100popularity1-AUC050001000010-210-1100popularity1-AUCUSAirNSLHN-2LHN-2LHN-2LHN-2PBC.elegans大部分指标预测精度与边的popularity成反比。PA指标最为明显。相对于其他指标，LHN指标的预测精度随popularity的波动不大，在某些网络中popularity小的边的预测精度反而要高些。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的增加还有所下降的情况。15Top-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指标更倾向于预测出非流行边。16Top-L-popularity表：基于网络结构的相似性指标（PB）17调节节点度的影响()()()axyxySxykka=-1:LHN-I指标a=-0.5：saltona=0：CN1）最优的参数值a大体上与P成正比2)测试集边比较流行时，最优参数a很接近0.3)最优参数的选取对网络的依赖性很大。引入自由参数a18下步的工作现有的基于相似性的指标大都更倾向于预测流行的连边。LHN指标的对非流行边的预测精度比较好。但是LHN总体上的表现又不那么令人满意，能否设计一种对流行边和非流行边预测精度都比较高的相似性指标？19