复杂网络链接的可预测性

banxia

论文题目: Toward link predictability of complex networks
论文作者: Linyuan Lü, Liming Pan, Tao Zhou, Yi-Cheng Zhang, and H. Eugene Stanley
论文背景:真实世界的网络结构包括规则的和不规则的。而规则的网络能够解释为什么缺失的链接可以被预测。理解网络结构，我们应该尽可能的去评估链接可预测的性能。这样一个网络存在有效的链接预测能够证明这个网络的机制,而一个好的理解网络结构的方式也能转化成一个好的链接预测算法。
文章提出的重点:
1、链接可预测性：不是指某一特定的算法的性能，而是指网络本身对于预测的困难程度固有的特性。
2、结构一致性：如果随机添加或移除网络中的一些链接，而网络的结构特征没有明显改变的网络，作者认为具有更高的链接可预测性。所以作者提出了一个结构一致性指标，是一个基于一阶矩阵扰乱，不要求有关于网络的任何先验性知识而反映这个网络的内在链接可预测的性能。
3、结构扰乱方式：随机抽取网络的一小部分链接。对这个链接进行一个扰乱，看是否对网络的结构造成大的影响，由此判断整个网络的结构特征。
结构一致性的计算：分为六步，给一个网络G:
        随机选择网络中的一部分链接构建扰乱局∆E（对应∆A)，余下部分E^R（对应A^R），且A=A^R+∆A。
        计算A^R特征值λ_k和它相对应的特征向量x_k。
        用 计算出∆λ。
        用 计算出A ̃。
        根据A ̃给出的分值对未被观察到的链接排序。对于一个未被观察到的链接（i，j）它的分值是A ̃_ij。
    选择top-L没有被观察到的链接，L是∆E链接的数量，看有多少是在∆E中的，比率就是σ_c。
（计算方法中各变量代表的含义：A:N*N的邻接矩阵；N:结点数目。A_ij:为1代表i,j两结点有关联，为0代表i,j两结点没有关联。∆E：随机选取的一部分链接，构造一个扰乱局对应矩阵∆A。E^R：余的链接部分是E-∆E，对应的矩阵是A^R。σ_c：结构一致性。）
SPM(structural perturbation method)结构扰动方式：
    结构扰乱方式被用来判断网络结构是否能被应用于预测缺失链接的应用。最简单的关联预测架构是基于每个节点对x和y被配置一个相似分数s_xy。所有没被观察到的根据它们的分数值被分为不同的等级，假设链接之间的分数值越高相关性越大。在这个框架之下，进入A能够被考虑作为相似分数被分配给链接。例如，在图1中，如果我们想要通过使用结构扰动方式(SPM)在被给的网络A中去预测一个缺失的链接。我们将根据他们的分值分级所有的未被观察链接（例如，链接矩阵中对应链接为0），然后找到排名第一相关的链接。
对于一个给定的网络计算SPM分五步：
        把网络A分为训练网络E^T 〖和E〗^P,A=A^T+A^P。
        进一步把E^T分为E^R和∆E。
        用∆E去扰乱E^R，计算A ̃接着计算σ_c。
        重复步骤2和3十次，也就是我们独立的把E^T分为E^P和∆E十次。我们得到10个A ̃矩阵。平均这十个矩阵的A ̃_ij链接得到链接（i,j）的分值
        根据A ̃的分值递减排列所有未被观察的链接，我们选择E^P顶部的链接看有多少实在探测的部分，这个比率就是精度。
图1、图例计算：

图一为一个网络，蓝色的虚线为选取的扰乱局∆E=｛（5，8），（6，9）｝，图二A为网络对应的矩阵，黑色部分和蓝色部分为网络的E^R 和∆E。图三是得到的一个扰乱矩阵A ̃，根据A ̃的值递减排序在U-E^R的链接，有两个链接为∆E，L=2，E^L=｛（3，8），（6，9)}为图四红色虚线部分。两个图一的蓝色虚线部分只有一条被覆盖，则σ_c=0.5.
（上述一些变量代表的意义：E^T：网络中选取一部分作为训练集。E^P：网络中余下部分，作为测试集。L=|∆E|，为扰乱局中链接的数量。E^L为扰乱后的排名前L个链接分值组成的链接部分。）
有两个指标来度量链接预测的准确性：AUC和精度
AUC（the area under the receiver operating characteristic curve）：高精确度的估计AUC的值不需要知道目标列表。每次随机选择一个缺失的链接和一个不存在的链接比较他们的分值。独立的比较n,如果缺失的链接有n’次更高的分数，n”次相同的分数，则
精度：就是缺失的链接被正确预测到的概率。
实验比较：
    作者把SMP方式跟六个现有的算法进行了比较。包括四个基于相似指数集： the common neighbors (CN) index ，theAdamic-Adar (AA) index , the resource allocation (RA)index , and the Katz index .和两个基于相似性方法的：the hierarchical structure model (HSM) and the stochastic block model (SBM)。
比较结果：
图2、在10个真正网络中链接预测的精度比较：

图3、在3个现在的真正网络中的链接预测的精度的比较：

证明σ_c作为链接可预测性指标的有效性:
    考虑模式网络的结构一致性来展示σ_c作为链接可预测性指标的有效性。作者选取了两个已知的结构不具有一致性的网络，一种是the Erdös−Rényi (ER) 网络，这种网络每对结点相关联的概率为p，当概率p确定后，结点数目N增大到无穷时这个网络变得随机具有较低的结构一致性，也就是链接可预测性的概率很低。另一个网络是Watts−Strogatz (WS)网络，这个网络的特点是有N个结点，每个结点假定有K个最近邻居结点，也就是跟其他K个结点有链接。每个链接被随机选择的一个结点对形成的链接替代的概率为q。q=1时网络是完全随机的，q=0时网络是确定的。既网络随着q的增加，链接可预测性会变低，观察σ_c的变化，来反向证明σ_c作为度量链接可预测性的有效性。这两个实验的结果如图所示：

    图示可以看出，当一个网络的可预测性变低时，σ_c也变得越来越小，由此可证明σ_c可作为网络固有的链接可预测性的指标。
对于同一个网络，选取的扰乱局的大小对σ_c值是否会有影响：

     上图为作者在分别不同网络中选取不同数量的扰乱局测试选取不同大小的扰乱局对σ_c值的影响，由图中可以看到选取的扰乱局的大小对σ_c的影响不大。
    总结：作者提出了网络的链接预测不光跟算法有关，也跟网络本身所固有的性能有关，提出来一个预测链接的算法，并给出了一个判定网络本身是否具有可预测性的度量指标。并证明了这个度量指标的有效性。