引用本文

潘永昊, 于洪涛.基于网络同步的链路预测连边机理分析研究.自动化学报, 2020, 46(12): 2607−2616 doi: 10.16383/j.aas.c180469

Pan Yong-Hao, Yu Hong-Tao. Analysis of linkage mechanism of link prediction based on network synchronization. Acta Automatica Sinica, 2020, 46(12): 2607−2616 doi: 10.16383/j.aas.c180469

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180469

关键词

复杂网络，链路预测，同步，主稳定函数方法 

摘要

链路预测是研究复杂网络结构演化趋势的重要组成部分, 用于预测网络丢失的连边和未来可能出现的连边, 具有极大的理论和应用价值.当前链路预测研究成果主要基于网络结构特征对连边进行预测, 具体分析其连边机理的研究较少.网络同步的研究能够深刻反映节点的动力学演化行为与网络结构之间的内在机理.本文针对链路预测考虑的静态网络引入节点动力学模型构成动态网络, 通过分析链路预测连边与动态网络模型同步之间的关系, 对链路预测连边机理进行分析研究.通过实验与理论分析总结发现了链路预测连边具有同步能力稳定性的规律.进一步讨论了链路预测连边的动力学机理, 并揭示了链路预测连边机理与真实网络演化的差别.

文章导读

近年来随着科学技术的不断发展, 人们的社会生活、工业生产越来越多地依托各类复杂网络系统, 如社交网络、电力网络、交通运输网络、工控网络等, 这些复杂网络系统在方便人们生活、提高生产效率等方面发挥了极大的作用.在复杂网络系统的应用中, 常常需要对网络的结构连边信息进行链路预测[1], 这种预测既包括对已经存在但未被观测到的连边的预测, 也包括了未来可能出现的连边的预测.近年来, 关于链路预测的研究已经成为复杂网络理论研究的一个重要部分, 已有的研究成果主要基于网络拓扑结构, 而基于网络同步的链路预测研究成果相对较少, 复杂网络中的链路预测问题仍然具有很大的研究空间.

唯物辩证法中, 对立统一规律揭示了"事物发展变化的源泉和动力在于自身的矛盾运动", 统一性和斗争性是矛盾双方的固有属性, 对立面之间既相互依存、相互渗透、相互贯通, 同时也相互排斥、相互否定, 矛盾双方既统一又斗争, 从而推动事物发展变化.网络的演化发展过程中, 节点之间通过连边关系相互影响、对立统一, 是网络演化过程中的基本动力.链路预测与网络同步正是这种动力在不同角度的体现, 链路预测研究网络静态结构演化, 网络同步则是研究节点动力学演化过程与网络静态结构的相互关系, 因此, 把链路预测与网络同步联系在一起, 能够进一步接近并且深入研究网络演化发展运动的动力和规律.

现有链路预测研究主要从网络拓扑结构出发, 通过充分挖掘拓扑结构特征中包含的信息, 对网络的连边情况进行预测.现有链路预测方法多为基于相似性的方法, 基于局部信息相似性的指标如共同邻居(Common neighbours, CN) [2]、Adamic-Adar (AA) [3]、资源分配(Resource allocation, RA) [4]、偏好受限(Preferential attachment, PA) [5]、拓展资源分配(Extended resource allocation) [6]等, 基于路径相似性的指标如Local path (LP)、Katz等, 以及基于随机游走相似性的指标如基于随机游走的余弦相似性(Cos+) [7]、有重启的随机游走(Random walk with restart, RWR) [8]等, 另外还有其他相似性指标[1].在链路预测中还有一种复杂的框架, 基于似然分析的链路预测方法, 如层次结构模型[9]、随机分快模型[10]、闭路模型[11]等.近年来有学者利用不同链路预测方法的互补性, 提出了对多种链路预测方法的叠加优化方法, 如文献[12]中采用三种不同的OWA (Ordered weighted averaging)算子对九种基于局部信息的结构相似性指标进行了融合, 文献[13]将链路预测问题定义为二分类问题, 并提出一种基于Adaboost的链路预测优化算法, 利用Boosting方法通过错误反馈提升弱学习算法, 从而得到强学习算法的思想, 并利用链路预测计算结果的互补性原则选取若干链路预测指标作为弱分类器, 提出一种基于AdaBoost算法的链路预测优化算法.文献[14]则提出一种基于Choquet模糊积分的链路预测算法, 引入模糊数学中模糊测度和模糊积分的概念, 在考虑不同链路预测指标的重要性和交互作用的基础上, 提出对不同链路预测指标进行叠加优化的算法.从以上研究中可以看出, 仅仅从网络拓扑结构出发的链路预测研究, 并没有考虑到每个节点自身的动力学特征.

对网络中的节点行为和特性进行动力学建模, 即为复杂网络动力学模型.同步正是复杂网络动力学模型中, 节点动力学演化行为的重要现象.网络同步主要就是研究节点动力学行为与网络拓扑结构的关系[15].在Pecora等[16]提出的主稳定函数方法中推导出了网络达到完全同步的必要条件, 网络的Laplacian矩阵的特征值就是其中一个主要变量, 网络同步的研究主要包括对不同网络的同步研究以及网络同步的方法, 如单层网络[17-28]和多层网络[29-32]的同步、Lyapunov方法[33]、主稳定函数方法[16]以及连接图方法[34-37]等.在Zhou等[38]的研究中表明, 节点的动力学同步过程能够反演网络拓扑结构, 进行网络拓扑结构识别以及参数识别.可以看到, 网络同步研究包含了节点动力学行为与网络拓扑结构两个部分, 互为支撑且互为补充.

基于以上研究结论, 本文的研究中考虑节点动力学行为与网络拓扑结构两个方面对链路预测问题进行研究分析, 具体为链路预测计算的连边对于网络同步过程的影响, 通过对节点的动力学同步过程以及网络的同步能力的讨论, 对链路预测连边的动力学特性以及动力学机理进行研究, 揭示链路预测的连边在网络同步中的基本规律.通过数值仿真实验总结发现, 链路预测计算的连边对于网络的同步过程影响极小, 即网络拓扑结构按照链路预测的方式演化(后文中称为网络的链路预测演化), 网络的同步能力与演化前近似相等, 具有稳定性(后文中称为链路预测的同步能力稳定性), 并通过理论分析, 给出同步能力稳定性的理论解释, 同时也从网络同步的角度, 对链路预测进行了讨论, 分析了链路预测连边的动力学机理.本文创新点如下: 1)从网络同步的角度出发研究链路预测连边与节点动力学演化的相互作用关系; 2)结合节点动力学研究讨论了链路预测的连边机理; 3)以同步能力作为网络的一种结构特征, 提出链路预测的同步能力稳定性.

图 1  NW小世界网络的x分量运动轨迹图

图 2  Jazz网络的x分量运动轨迹图

图 4  8节点网络

链路预测是复杂网络领域研究网络结构信息与网络演化的重要部分, 网络同步是研究网络结构与节点动力学同步之间的关系, 网络结构的演化会使得网络节点动力学同步发生变化, 而通过节点的动力学同步现象又可以研究网络结构演化的动力学机理.在本文的研究中发现链路预测演化具有同步能力稳定的特点, 也就是网络通过链路预测演化前后, 网络的同步能力具有稳定性, 并结合链路预测相似性指标的定义, 说明这种稳定性是链路预测的原理方法决定的.通过对于网络结构演化与节点动力学行为的研究, 进一步分析了结构演化的动力学机理, 清晰的反映出链路预测研究与真实网络演化过程在动力学机理上的区别, 链路预测的演化趋势是完全基于现有网络结构信息的, 而在真实网络演化中既包含了链路预测的部分, 也包含随机演化的部分.值得注意的是, 本文的研究把复杂网络领域中链路预测研究与网络同步研究两个方向联系在了一起, 用网络同步的研究方法研究分析了链路预测问题, 同时也提出了网络演化中的同步问题, 是一个新的研究网络结构演化与节点动力学行为的研究思路.

作者简介

潘永昊

国家数字交换系工程技术研究中心硕士研究生.主要研究方向为复杂网络链路预测.E-mail: panyonghao2016@163.com

于洪涛

国家数字交换系工程技术研究中心研究员, 博士.主要研究方向为网络大数据分析与处理.本文通信作者. E-mail: 15937101921@139.com