复杂网络上重要节点寻找算法的研究——基于随机游走和边重要性衡量指标

摘要

识别网络中重要节点的问题在社会和经济生活中有着重要的作用，近几年已经得到广泛的研究。节点的重要性也称“中心性(centrality)”，是网络分析领域的一个重要问题。这不仅因为其重大的理论研究意义，更因为其广泛的实际应用价值。它有很多应用，比如，控制爆发传染病、为电子商务产品做广告、预测流行的科学出版物、控制谣言的传播等。
　　对于重要节点寻找问题有各种算法，从简单的计数邻居节点的数目到复杂的算法。目前识别网络中重要节点最常用、最经典的算法有degree centrality、betweenness centrality、closeness centrality、PageRank算法等。其中，PageRank算法在实际中有广泛应用，Google搜索引擎成功地将其用于对网页进行排序。在PageRank算法或其他基于随机游走的中心性方法的随机游走过程中，随机游走者总是从其邻域中随机地选择下一个到达的节点。但在现实世界中，这种选择更可能具有“倾向性”。例如，信息在两个更亲密的朋友之间传播得更频繁。因此，在本文中，提出了两种新的考虑到这种“倾向性”的节点中心性方法，即DPRank centrality和ECP-Rank centrality。
　　DPRank centrality的主要思想是，为了使信息可以迅速传播，random walker不再从邻居节点中随机选择下一个节点，而是有远见地倾向于转移到具有更大度的邻居节点（或者在有向网络中转移到出度更大的节点），即random walker从当前节点vi转移到它的邻居节点vj的倾向性，与邻居节点vj的（出）度成正比。可以看出，DPRank中心性方法不仅考虑了节点的一阶邻居，还考虑到了节点的二阶邻居（即邻居的邻居）的信息。
　　ECP-Rank centrality的主要思想是，random walker不再从邻居节点中随机选择下一个节点，而是有倾向性地通过走“重要的”边来到达下一个邻居节点，边的重要性通过采用边重要性指标（或中心性指标）来进行衡量，如Jaccard指标、Bridgeness指标、Degree product指标和Estrada指标等，即random walker从当前节点转移到它的邻居节点的倾向性，与他们之间边的“重要性”成正比。
　　以上两种方法均是通过定义新的转移概率矩阵，重新衡量了复杂网络中顶点的重要性。转移概率矩阵的转置矩阵对应于最大特征值1的特征向量，即为网络中各节点重要性的得分。将DPRank centrality和ECP-Rank centrality，以及几个经典的节点中心性方法应用于多个真实网络，通过计算SIR传播模型所得的标准排序和不同中心性方法所得结果之间的Kendall系数，验证了DPRank centrality和ECP-Rank centrality两种新方法的优势。
　　本文的创新之处在于，在随机游走过程中，将random walker在顶点之间转移的倾向性考虑在内。据所知，这是第一次将节点中心性与边中心性相结合的节点中心性衡量方法。从试验结果来看，DPRank算法和ECP-Rank算法的结果比其他算法结果准确性高。

目录

声明

摘要

符号说明

第1章 绪论

1．1 节点重要性问题

1．2 研究背景与研究意义

1．3 节点重要性问题的经典算法

1．3．1 度中心性

1．3．2 接近中心性

1．3．3 介数中心性

1．3．4 PageRank算法

1．3．5 LeaderRank算法

1．3．6 Pro-PageRank算法

1．4 节点重要性算法评价标准

1．4．1 SIR模型

1．4．2 Kendall相关系数

1．5 本文结构及创新点

第2章 DPRank centrality：一种基于新随机游走规则的重要节点寻找算法

2．1 基本知识

2．2 DPRank centrality算法

2．3 DPRank centrality算法流程

2．4 应用和试验

2．4．1 数据集2-1：伊斯兰祈祷团2002年巴厘岛恐怖袭击网络

2．4．2 数据集2-2：Zachary空手道俱乐部网络

2．4．3 数据集2-3：911袭击事件网络

2．4．4 数据集2-4：Freeman的EIES网络

2．4．5 更多数据集

2．5 本章小结

第3章 ECP-Rank centrality：一种基于随机游走和边重要性指标的重要节点寻找算法

3．1 一些经典的边中心性指标

3．2 ECP-Rank centrality算法

3．3 应用和试验

3．3．2 数据集3-2：伊斯兰祈祷团2002年巴厘岛恐怖袭击网络

3．3．4 数据集3-4：悲惨世界网络

3．3．5 数据集3-5：Kapferer矿井网络

3．3．6 更多数据集

3．4 本章小结

第4章 结论与展望

4．1 结论

4．2 展望

参考文献

致谢

作者简介