大规模二分图节点影响力分析研究

摘要

针对图模型中节点影响力的研究，是近年来复杂网络分析领域的热门方向之一。研究者们发现，用于描述节点连接关系的各种中心性度量并不能很好地表征节点对整个网络的影响力。例如，节点的度中心性高并不意味着从这个节点开始传播的信息就会很快的扩散到整个网络。相比传统的中心性度量，基于传染病学中病毒扩散模型的动力学仿真更能准确地反映图中节点的影响力。不幸的是，当图的规模较大时，无论是计算一些需要全局搜索操作的中心性度量，或是进行全图节点的动力学仿真，都会遇到计算量爆炸的问题。因此，如何在大规模图中准确而高效地寻找高影响力的节点，一直是研究领域一个悬而未决的问题。
　　针对此问题，本文利用节点的近邻信息提出了节点的近邻谱(neighborhoodspectrum)，再基于近邻谱定义了两个新的节点影响力度量，近邻谱扇出系数(fan-out coefficient)和传播功率(propagation power)，实验表明这两个度量比传统的中心性度量能更好地表征节点的影响力。本文进一步发现在大规模二分图中存在复杂度与图的边规模接近线性关系的高效算法，提出了基于桶排序的快速求解全图节点近邻谱的高效算法，可以在十亿条边规模甚至更大规模的二分图上估算全图每个节点的影响力。
　　为了评估文中所提方法和度量的有效性，本文针对不同规模不同拓扑结构的真实世界网络做了大量的SI和SIR动力学仿真实验。实验结果表明，在小规模图上，本文提出的两个度量比传统的中心性度量能更好地表征节点的影响力。在大规模二分图上，本文提出的高效算法能快速求解出全图的节点近邻谱，利用本文提出的两个度量能高效地识别出大规模二分图中的高影响力节点。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 节点影响力度量研究现状

1．2．2 二分图研究现状

1．2．3 大规模图节点影响力研究现状

1．3 研究内容

1．4 结构安排

第2章 相关理论与方法

2．1 网络的图表示

2．2 节点的中心性度量

2．2．1 度中心性

2．2．2 局部中心性

2．2．3 H-度中心性

2．2．4 介数中心性

2．2．5 紧度中心性

2．2．6 特征向量中心性

2．2．7 PageRank

2．2．8 LeaderRank

2．2．9 K壳中心性

2．2．10 HITS算法

2．3 网络的演化模型

2．3．1 ER随机网络模型

2．3．2 WS小世界网络模型

2．3．3 BA无标度网络模型

2．4 节点影响力与SI／SIR模型仿真

2．4．1 SIR模型

2．4．2 SI模型

2．4．3 节点影响力的评估方法

2．5 本章小结

第3章 基于节点近邻谱的节点影响力分析

3．1 节点近邻谱

3．1．1 近邻谱扇出系数和传播功率

3．1．2 节点近邻谱及其相关度量计算举例

3．2 针对大规模二分图求解节点近邻谱的算法

3．3 本章小结

第4章 实验分析

4．1 真实小规模网络仿真实验

4．1．1 Zachary空手道俱乐部网络

4．1．2 南方妇女社会活动网络

4．1．3 悲惨世界人物关系网络

4．1．4 海豚家族关系网络

4．1．5 美国大学足球队网络

4．1．6 美国政治书网络

4．1．7 网络科学的协作关系网络

4．1．8 单词连接关系网络

4．1．9 Internet路由快照网络

4．2 真实大规模网络仿真实验

4．2．1 Yahoo!搜索关键词与广告商关系二分图

4．2．2 Yahoo!用户-群组成员关系二分图

4．2．3 QQ用户-群组关系二分图

4．3 Github仓库展示

4．4 本章小结

总结与展望

参考文献

致谢