基于传递相似性的复杂网络链路预测

作     者：房金飞 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：高琳

授予年度：2014年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：复杂网络 链路预测 资源分配 传递相似性 

摘      要：复杂网络是研究复杂系统的有效工具,真实世界的复杂系统是随着时间变化的,因而对应的网络也在变化,刻画这种变化的网络就需要对边的变化进行预测,即链路预测问题的研究。按照网络的边是否随时间变化,可以将网络分为静态网络和动态网络。相关的链路预测方法也不同。静态网络链路预测认为,在当前已知数据条件下,网络中现有的边在未来的短时间内不会发生变化,而目前不存在的边在未来中可能出现。链路预测在实际应用和理论研究中都有重要的经济以及理论价值。现有的静态网络链路预测方法按照其思想主要可分为基于拓扑结构的方法、基于马尔科夫理论方法以及基于概率似然理论的方法等三大类。其中,以共同邻居和资源分配(Resource Allocation,RA)方法为代表的基于局部拓扑结构信息的方法计算复杂性较低、容易理解,比较适合处理大规模网络数据。然而,此类方法只使用了拓扑上最邻近的结构信息,对于拓扑上更远的结构信息并未考虑,限制了其预测的性能。本文改进了资源分配方法,将其和传递相似性整合,提出了基于资源分配的传递相似性(Transferring Similarity based on Resource Allocation,TSRA)链路预测方法,并考虑到该方法需要计算逆矩阵的不足,提出了由该方法改进的基于资源分配的传递结构相似性(Transferring Structure Similarity based on Resource Allocation,TSSRA)链路预测方法和基于资源分配的多步传递相似性(Multi-step Transferring Similarity based on Resource Allocation,MTSRA)链路预测方法,这两个方法克服了基于资源分配的传递相似性方法需要矩阵求逆的不足。由于考虑了两节点之间的中间节点对节点对相似性的贡献,相比于资源分配方法,新方法更充分的利用了节点对路径上中间结构信息。实验结果表明,新方法在保持方法低时间复杂度的同时,提高了链路预测的准确性。针对链路预测问题,本文用链路预测领域常用数据集对新方法的特性进行了详细的实验研究,并且和资源分配方法在多个网络数据集上按照多种不同的评测标准进行了预测性能的综合比较分析。实验结果表明,本文提出的基于资源分配的传递结构相似性方法在Router以及Power等数据集上得到的AUC比原有的RA方法提高了0.06左右,在Yeast以及Celegans等数据集上的AUC提高了0.03左右。基于资源分配的传递相似性方法则相比于资源分配方法主要在Power数据集上AUC提高了0.06左右,在其它数据集上则提升不明显。基于资源分配的多步传递相似性方法也是主要在Router以及Power数据及上有0.04左右的提高。