复杂网络的链路预测算法及其应用研究

摘要

复杂网络中链路预测的研究已经在很多学科中引起热议。它不仅在理论上有助于理解复杂网络的演化机制，而且还解决了应用中的重大问题。比如信息集成、社会网络分析、推荐系统和生物信息学等等。所以研究低时耗、高精度的预测算法在当下仍然是一项具有挑战性的工作。现有的链路预测算法大多是基于网络的拓扑信息提出的，比如网络的局部相似性信息和全局相似性信息等。基于网络局部相似性信息的链路预测算法具有时间复杂度低的优点，但是精度不高；而基于网络全局相似性信息的链路预测算法却正好相反，精度提升的同时时间复杂度也增加了。所以越来越多的研究者开始探索如何折中算法的精度和时间复杂度，来设计出更高效的链路预测算法。于此同时，也有更多的学者研究复杂网络的其他特性对链路预测算法的影响，比如复杂网络的幂率分布特性、小世界效应等。作为复杂网络的一类重要特征，层次结构信息和社区结构信息对网络的链路预测是非常有意义的，但是目前存在的链路预测算法对这类网络的结构特征利用还几乎为零。针对这一问题，本文利用挖掘的网络社区结构信息，建立了基于社区结构信息的链路预测理论，提出了三种有效地链路预测算法。此外，还对所设计算法的适用网络做出分析，最后运用解决链路预测问题的思想提出了一种有效的社团检测算法。
　　（1）提出了基于多分辨社区划分的链路预测算法，用以解决网络中缺失链接难预测的问题。这是首次利用网络的多分辨社区结构信息来解决复杂网络的链路预测问题。算法主要分三大步：第一步是多分辨率的社区划分。为了避免出现分辨率限制问题，也为了得到足够的统计样本，所设计的社区划分方法是基于模块度密度优化的。传统的社区划分方法是以得到高精度的划分结果为目标的，所以在运行时间上很难控制，本章所提出的社区划分方法和传统的社区划分方法不同，只是为了划分结果的多样性，并不追求划分结果的高精度，因此可以大大的降低算法的时间复杂度；第二步是统计在不同的划分结果下，出现在同一个社区的节点对的频度。本文假设不同分辨率下社区划分的结果对所要预测的链接存在概率的影响因子不同，所以文中赋予其不同的权重；最后，频度频率进行转换，得到缺失链接可能存在的概率。越高的概率值意味着该链接存在的可能性越大。通过对不同规模的benchmark网络和现实网络进行预测，结果验证了本文所提方法的有效性，以及对比经典链路预测方法的优势。
　　（2）提出了基于社区相关性和规则推理的缺失链路的预测算法。该工作提倡转变考虑问题的角度，即从节点到社区，特别是从节点相似性到社区相关性的转变。以一种新的理念来制定以社区信息为基础的衡量指标，而且重点研究不同社区之间的关系，以及这种关系对链路预测的影响性。该方法主要分三大步：首先提取网络的社团结构信息，为了减少算法的时间复杂度，本文设计的是一种基于网络局部信息的社团划分方法，可以快速对网络进行社区划分；接着，利用新定义的社区相关性指标来计算每对社区之间的相关性，这里定义的社区相关性指标是用来描述社区之间联系紧密程度的，所以社区间联系越紧密，相关性指标值也就越大；最后，采用一个简单的基于规则推理的预测模型来估计缺失链接的存在概率。通过对不同规模的benchmark标准网络和真实网络进行预测，并与其他十个经典的方法进行比较，结果表明，增加了社区相关性特征的算法，以增加较低的时间复杂度为代价，克服了传统的基于相似性算法的弊端，即位于不同社区的节点之间链路存在的概率完全等同于它们之间的相似性。
　　（3）通过折中算法的时间复杂度和预测精度，提出了基于社区相关性的无监督链路预测算法对缺失链接进行快速准确地预测。该算法考虑了更多的网络结构信息，除了局部信息外还包括网络的部分全局信息，且有效的把全局信息和局部信息结合起来设计网络的相关性指标。该方法主要分三大步：首先利用COMM-ST算法对网络进行初始划分；在得到网络的初始划分之后，我们结合网络的全局信息和局部信息设计合适的社区相关性指标，利用设计的指标计算不同社区之间的联系紧密程度；最后根据得到的社区相似性矩阵来预测缺失链接的存在概率。通过对不同规模的benchmark标准网络和真实网络进行预测，实验结果证明此方法克服了网络度分布一致性对基于局部信息的社区相关性算法的限制，而且在可接受的时间复杂度下具有更高的预测精度。
　　（4）分析了基于社区相关性链路预测算法的两个大问题。其中一个是网络度分布一致性对基于局部信息的社区相关性算法性能的限制问题；另一个是基于全局和半局部信息的社区相关性链路预测算法的过拟合问题。本章对实验中出现的问题进行分析，提出问题出现的原因假设，然后通过大量的实验来验证，并统计出问题出现的临界点。实验结果表明，当训练样本不多时，基于局部信息的社区相关性算法性能会因为网络的度分布不一致而出现明显地下降；当训练样本太多时，基于全局信息的社区相关性算法性能会因为相似性矩阵的有效解个数太多而变差。此外，我们还定量的分析了基于全局信息的社区相关性算法出现过拟合现象的临界点，对于有效的避免过拟合提供了数据参考。
　　（5）传统的社区检测算法大多是基于网络的模块度优化进行的，但是这类方法在计算复杂度上不具有优势，而且还存在分辨率限制等问题。针对这一问题，本章节参照社区结构的表现形式提出了一种新的社区检测方法。该方法的核心思想就是通过多次合并相关性大的社区对，从而得到网络的一个合理划分。首先，根据网络节点的度分布来初始化一个社区划分；然后，利用社区相关性指标计算网络中不同社区之间的相关性，相关性越大则表明社区之间联系越紧密，联系越紧密的社区，合并在一起的可能性也越大；最后，合并相关性大的社区对直到条件不满足时结束。该算法在社区合并的过程中收敛速度越来越快，与其它6种经典算法对benchmark标准网络和真实网络进行社区划分发现，无论是在时间复杂度上还是在划分精度上本方法均有优势。除此之外，本文中还定义了一种新的测度标准来描述网络划分的难易程度。

目录

声明

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.2 链路预测发展历史及研究现状

1.3 社区检测发展历史及研究现状

1.4 本文主要内容

第二章 基于多分辨社区划分的链路预测

2.2 基于多分辨社区划分的链路预测算法

2.3 实验结果与分析

2.4 本章小结

第三章 基于社区相关性和规则推理的链路预测

3.2 基于社区相关性和规则推理的链路预测算法

3.3 实验结果与分析

3.4 本章小结

第四章 基于社区相关性的无监督链路预测

4.2 基于社区相关性的无监督链路预测算法

4.3 实验结果与分析

4.4 本章小结

第五章 基于社区相关性链路预测算法的一致性与过拟合问题

5.2 CR-local算法的度分布一致性

5.3 CR-global算法的过拟合

5.4 实验结果与分析

5.5 本章小结

第六章 基于社区相关性的复杂网络聚类

6.2 基于社区相关性的复杂网络聚类算法

6.3 实验结果与分析

6.4 本章小结

第七章 总结与展望

7.1 工作总结

7.2 工作展望

参考文献

致谢

作者简介