复杂网络的节点重要性度量算法研究-系统工程专业论文.docxVIP

万方数据 万方数据 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。 研究生签名： 日期： 南京邮电大学学位论文使用授权声明 本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档；允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索； 可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质 论文的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院办理。 涉密学位论文在解密后适用本授权书。 研究生签名： 导师签名： 日期： III 摘要 近年来，众多复杂网络研究学者越来越关注复杂网络中重要节点发现算法的研究。网络 中少量的重要节点对网络的影响超乎想象，例如信息通过重要节点能够在很短的时间内快速 传播到整个网络，对社会网络中少量的重要节点进行免疫能够有效延缓甚至控制谣言或者病 毒的传播。有效发现网络中的重要节点在诸多领域中都具有非常重要的意义，如政治、经济、 生物、电力网、通信网络等领域。本文针对重要节点发现算法的研究做了如下工作： 1. 针对现有传统经典的重要节点发现算法进行了研究，详细介绍了度中心性，介数中心 性，接近中心性，特征向量以及 PageRank 算法 5 种算法，并比较了各自的优缺点。 2. 根据相连节点对之间的共同邻居节点数目，提出了贡献度概念来表征节点间的相互贡 献。在现实网络中，节点与其邻居节点的连接关系存在亲疏之分，节点对与其连接亲密的邻 居节点的贡献度较大，这与传统算法不同，更符合实际情况。本文通过 K-Shell 分解算法得到 节点的自身属性值，认为节点的重要度取决于节点自身属性和邻居节点对其影响，由此提出 了 KSC 算法。 3. 针对真实的 Zachary 空手道网络，海豚社会网络以及计算机生成的 ER 随机图进行仿真。 通过分析网络的拓扑结构，观察节点之间的连接情况，验证本文 KSC 算法能够有效发现网络 中的核心节点，尤其是发现社团中的核心节点很有效。 4. 编写传播仿真程序，采用 SIR 传播模型，在单源传播情况下，KSC 算法表现较好。此 外还进行重要节点免疫实验仿真，实验结果表明：免疫 KSC 算法发现的重要节点，能够有效 阻止恶意信息的传播。 关键词: 复杂网络，重要节点 ，贡献度 ，KSC 算法 IV Abstract Recently, the study on the algorithm of discovering important nodes in complex networks is becoming a research hotspot. It is very valuable to discover important nodes in complex networks for lots of areas, such as politics, medicine, society, information technology and so on. The effect of several important nodes on the networks is unbelievable. For example, information will be spread to the whole network in a very short time via a few important nodes. In addition, immunizing important nodes in the network can effectively control the spread of disease. In this thesis, we mainly focus on the research of the algorithm of discovering important nodes, and the main contens are as follows: Some classic algorithms are introduced, including Degree centrality, Betweeness centrality, Closeness centrality, Eigen