基于搜索效率的复杂网络结构与功能的关系研究-计算机应用技术专业论文.docx

万方数据 万方数据 分类号： 密级： U D C ： 编号： 工学硕士学位论文 基于搜索效率的复杂网络 结构与功能的关系研究 硕士研究 生：高坤 指 导 教 师：朴秀峰 副教授 学 位 级 别：工学硕士 学科、专 业：计算机应用技术 所 在 单 位：计算机科学与技术学院 论文提交日期：2014 年 1 月 6 日 论文答辩日期：2014 年 3 月 10 日 学位授予单位：哈尔滨工程大学 Classified Index： U.D.C： A Dissertation for the Degree of M.Eng Research on the Relationships of the Structure and Function in Complex Networks Based on Search Efficiency Candidate: Kun Gao Supervisor: Associate-Prof.Piao Xiufeng Academic Degree Applied for: Master of Engineering Speciality: Computer Applied Technology Date of Submission: January, 2014 Date of Oral Examination: March, 2014 University: Harbin Engineering University 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。 有关观点、方法、数据和文献的引用已在文中指出，并与参考文献相对应。除文中已注 明引用的内容外，本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者（签字）： 日期： 年 月 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作 的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送 交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进 行检索，可采用影印、缩印或扫描等复制手段保存和汇编本学位论文，可以公布论文的 全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一 署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文（□在授予学位后即可 □在授予学位12个月后 □解密后）由哈尔滨工程 大学送交有关部门进行保存、汇编等。 作者（签字）： 导师（签字）： 日期： 年 月 日 年 月 日 基于搜索效率的复杂网络结构与功能的关系研究 摘 要 复杂网络理论对于研究信息的传播与共享、社团的博弈与收益和控制对象的动力学 行为有极大的助益，其中复杂网络结构与功能的探索已成为网络科学研究的重点之一。 鉴于复杂网络拓扑结构与功能的多样性，本文选取普遍存在的搜索功能作为研究对象， 探索复杂网络结构与搜索功能的关系。对于发现实际网络的演化模式、理解社团间的合 作关系，对互联网搜索及社会网络分析等都具有重要意义。 本文首先对复杂网络的基本概念和国内外研究现状进行相关介绍，指出目前 ER 随 机图网络、WS 小世界网络和 BA 无标度网络是专家认可的三种经典复杂网络拓扑结构， 研究这些模型与搜索功能之间的关系对网络科学具有重要的普适意义；其次，对哲学、 社会学、复杂网络等领域的结构与功能的基本理论进行了简单分析；再次，本文较早提 出“复杂网络竞争演化猜想”，并基于搜索效率在一个较为公平的异质网络模型中证实 了此猜想，从而在一定程度上解释了真实复杂网络中普遍存在的无标度特性结构的原因， 以及该结构与搜索功能的关系。本文研究表明，具有无标度特性的网络模型较其它模型 更有利于搜索，实验过程中发现了搜索的不对称现象，结果表明 BA 网络和 WS 网络之 间相互搜索的路径长度之比可以高达 7 倍之多，又进一步在大量的实际非时序网络中观 察到这种现象。而真实的网络竞争过程只能从时序网络的演化中观察，最后，本文选取 DBLP 时序网络作为分析对象，分析其结构模式及角色地位，深度剖析子网规模随着时 间演化的规律。结果证明真实网络演化过程中存在大量复杂异质的局部社团，其中具有 无标度性质的子网增长速度最快，具有明显优势。本文工作在一定程度上丰富了以往复 杂网络对于该领域的研究成果，而且有利于发现有实用价值的优化搜索效率或信息传播 的手段，弥补了复杂网络全局拓扑缺乏对搜索带来的困难，同时，也促进了结构功能理 论在大规模复杂网络中的验证分析