复杂网络研究的一些进展与思考
复杂网络及其在国内研究进展的综述
第17卷第4期2009年10月 系统科学学报 JOURNAL OF SYSTEMS SCIENCE Vo1.17No.4 oct ，2009 复杂网络及其在国内研究进展的综述 刘建香 （华东理工大学商学院上海200237） 摘要：从复杂网络模型的演化入手，在简要介绍复杂网络统计特征的基础上，对国内关于复杂网络理论及其应用的研究现状从两方面进行综述：一是对国外复杂网络理论及应用研究的介绍，包括复杂网络理论研究进展的总体概括、复杂网络动力学行为以及基于复杂网络理论的应用研究介绍；二是国内根植于本土的复杂网络的研究，包括复杂网络的演化模型，复杂网络拓扑性质、动力学行为，以及复杂网络理论的应用研究等。并结合复杂网络的主要研究内容,对今后的研究重点进行了分析。 关键词：复杂网络；演化；拓扑；动力学行为中图分类号：N941 文献标识码：A 文章编号：1005-6408（2009）04-0031-07 收稿日期：2009-01-05 作者简介：刘建香（1974—），女，华东理工大学商学院讲师，研究方向：系统工程。E-mail ：jxliu@https://www.sodocs.net/doc/7918498733.html, 0引言 系统是由相互作用和相互依赖的若干组成部分结合的具有特定功能的有机整体[1]。而网络是由节点和连线所组成的。如果用节点表示系统的各个组成部分即系统的元素，两节点之间的连线表示系统元素之间的相互作用，那么网络就为研究系统提供了一种新 的描述方式[2、3] 。复杂网络作为大量真实复杂系统的高度抽象[4、5]，近年来成为国际学术界一个新兴的研究热 点，随着复杂网络逐渐引起国内学术界的关注，国内已有学者开始这方面的研究，其中有学者对国外的研究进展情况给出了有价值的文献综述，而方锦清[6]也从局域小世界模型、含权网络与交通流驱动的机制、混合择优模型、动力学行为的同步与控制、广义的同步等方面对国内的研究进展进行了简要概括，但是到目前为止还没有系统介绍国内关于复杂网络理论及应用研究现状的综述文献。本文从复杂网络模型的演化入手，在简要介绍复杂网络统计特征的基础上，对国内研究现状进行综述，希望对国内关于复杂网络的研究起到进一步的推动作用。 1.复杂网络模型的发展演化 网络的一种最简单的情况就是规则网络 [7] ，它 是指系统各元素之间的关系可以用一些规则的结构来表示，也就是说网络中任意两个节点之间的联系遵循既定的规则。但是对于大规模网络而言由于其复杂性并不能完全用规则网络来表示。20世纪50年代末，Erdos 和Renyi 提出了一种完全随机的网络模型———随机网络（ER 随机网络），它指在由N 个节点构成的图中以概率p 随机连接任意两个节点而成的网络，即两个节点之间连边与否不再是确定的事，而是由概率p 决定。或简单地说，在由N 个节点构成的图中，可以存在条边，从中随机连接M 条边所构成的网络就叫随机网络。如果选择M =p ，这两种构造随机网络模型的方法就可以联系起来。规则网络和随机网络是两种极端的情况，对于大量真实的网络系统而言，它们既不是规则网络也不是随机网络，而是介于两者之间。1998年，Watts 和Strogatz [8]提出了WS 网络模型，通过以概率p 切断规则网络中原始的边并选择新的端点重新连接 31--
5僵尸网络翻译
外文译文 僵尸网络（节选） 一种网络威胁 摘要 僵尸网络常源于网络攻击，他能对我们的网络资源和组织的财富造成严重威胁。僵尸网络是一系列没有抵抗能力的计算机的集合（肉鸡），他们能够被始发人（控制机）在一个普通的指挥-控制架构下远程控制。在许多种恶意软件中，僵尸网络是现在兴起的最严重的网络安全威胁，因为他提供一种分布式平台让许多非法活动如发射许多分散的拒绝服务攻击特定的目标、病毒扩散、钓鱼和点击欺诈。僵尸网络最重要的特点就是可以使用指挥控制通道，通过这个通道他们可以更新和指挥肉鸡。僵尸网络对用户完整性和资源的攻击目的是多样的，包括青少年证实其组织犯罪的黑客技术，让基础设施瘫痪和给政府和组织造成经济上的损失。本文中，了解系统如何被盯上是很重要的。分类的重要优势在于发现问题和找到具体的防范和回复的方法。这篇文章旨在基于攻击的技术而提供针对主流存在的僵尸网络类型的简明的概述。 一般综述 僵尸网络是一种正在兴起的面向在线生态环境和计算机资源的最重要的危险，恶意的僵尸网络是分散的计算平台，主要用作非法活动，如发动分布式拒绝服务攻击、发送垃圾邮件、含特洛伊木马和钓鱼软件的电子邮件，非法散布盗版媒介和软件，强制分布、盗取信息和计算资源，电子商务勒索、进行点击诈骗和身份盗窃。僵尸网络最重要的价值在于能通过使用多层次的指挥控制架构提供匿名的功能。另外，个别的肉鸡并不比被控制机物理拥有，因而可以散布在世界各地。时间、地点、语言以及法律让跨疆域追踪恶意僵尸网络变得困难。这种特性让僵尸网络成为网络犯罪很有吸引力的一种工具，事实上给网络安全造成了巨大威胁。
关键词僵尸网络肉鸡僵尸网络的检测 介绍 僵尸网络是一个由无反抗力的计算机（称为肉鸡）被远程的一个人为操控端（称为主控机）控制下构成的网络。术语“Bot”来源于单词“机器人”。类似于机器人，僵尸程序被设计来自动地完成一些预定义的动能。换句话说，单个的僵尸程序是运行在宿主机上并允许控制机远程控制主机的行为的软件程序。 僵尸网络是当下基于网络的最危险的网络攻击形式之一，是因为其包含采用大型的、许多组协调运行的主机为强制攻击和狡猾的攻击服务。一组肉鸡，当被一个指挥控制架构控制的时候，就形成所谓的“僵尸网络”。僵尸网络通过提供一定的间接性来掩盖发动攻击的机器，发动进攻的机器被一层肉鸡与被攻击的机器分离出来，而攻击本身又在任意的总时间内和一个僵尸网络群分离开。技术进步同时推动人们的生活走向安逸和麻烦。不断产生的信息技术让人们可以前所未有地轻松接触信息。但另一方面，它恶化了信息安全水平。僵尸网络被证明是信息技术领域最新的和最灾难性的威胁。一个门外汉关于僵尸网络的理解是一个促进恶意攻击用户机器的网络，但理论上讲“僵尸网络是一个计算机集合，软件“bot”，是自动安装无需用户干预并且被指挥与控制服务器远程控制着”。尽管这一事实暗示该网络可既为邪恶的和有益的目的利用，其在犯罪中的广泛使用和毁灭性的目的使标题“僵尸网络”等于恶意软件。一个活跃的僵尸网络首先利用用户电脑的漏洞初始化它的攻击。然后它下载恶意二进制代码并在本地执行。这个程序登录到指挥与控制服务器，并通知它的主人，俗称主控机，这样该计算机就转换为一个肉鸡。现在它可以被用来通过使用相同的步骤感染其他机器。僵尸网络和其他的安全威胁的主要区别是一个主控机定期与肉鸡通过集中或分散的网络通信信道。这些机器人按照从主控机收到的命令执行任何类型的破坏。这些主控机发送命令，控制所有的肉鸡，然后可以作为一个单位攻击受害者。僵尸网络的发展速度非常快使它难以被检测，并恢复他们的损害。然而，它们广泛使用的一些类型可以被划分。本报告主要涉及三大类型的僵尸网络：IRC僵尸网络，点对点和HTTP僵尸网络，提出了一些技术来识别和检测他们。第一部分给出了一个僵尸网络的介绍。第二部分回顾了他们的历史和拓扑结构。第三章是关于他们的生命周期，僵尸网络的指挥与控制、僵尸网络拓扑结构，根据是指挥控制的信道和僵尸网络生命周期。三种主要类型的僵尸网络及其检测方案在3.1.1节，3.1.2节和3.1.3节分别谈到了。第3.2部分所提出的“僵尸网络”检测框架和组件；第四部分提出了该领域未来工作的一些预期的进展。第五部分是致力于对我们的研究的总体结论。
复杂网络研究概述,入门介绍
复杂网络研究概述 周涛柏文洁汪秉宏刘之景严钢 中国科学技术大学，近代物理系，安徽合肥：230026 摘要：近年来，真实网络中小世界效应和无标度特性的发现激起了物理学界对复杂网路的研究热潮。复杂网络区别于以前广泛研究的规则网络和随机网络最重要的统计特征是什么？物理学家研究复杂网络的终极问题是什么？物理过程以及相关的物理现象对拓扑结构是否敏感？物理学家进入这一研究领域的原因和意义何在？复杂网络研究领域将来可能会向着什么方向发展?本文将围绕上述问题，从整体上概述复杂网络的研究进展。 关键词：复杂网络小世界无标度拓扑性质 A short review of complex networks Zhou Tao Bai Wen-Jie Wang Bing-Hong? Liu Zhi-Jing Yan Gang Department of Modern Physics, University of Science and Technology of China, Hefei, 230026 Abstract: In recent years, the discoveries of small-world effect and scale-free property in real-life networks have attracted a lot of interest of physicists. Which are the most important statistical characteristics for complex networks that known from regular networks and random networks? What is the ultimate goal of the study of complex networks? Are physical processes sensitive to the topological structure of networks? What are the reason and meaning that physicist come into the research field on complex networks? What are the directions for future research? In the present paper, we concentrate on those questions above and give a general review about complex networks. Keyword: complex networks, small-world, scale-free, topological characters 1 引言 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[1]；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2]。类似的还有电力网络[1]、社会关系网络[1,3-4]、交通网络[5]等等。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？两百多年来，对这个问题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又或者最近邻环网，它总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了二十世纪五十年代末，数学家们想出了一种新的构造网
浅议僵尸网络攻击
电脑编程技巧与维护 浅议僵尸网络攻击 邹本娜 (中共葫芦岛市委党校，鞍山125000) 摘要：僵尸网络是指采用一种或多种传播手段，将大量主机感染僵尸程序，从而在控制者和被感染主机之间所形成的一对多控制的网络。僵尸网络，有别于以往简单的安全事件，它是一个具有极大危害的攻击平台。本文主要讲解了僵尸网络的原理、危害以及相应的应对方法。 关键词：僵尸网络；因特网中继聊天；控制服务器 1引言 2007年4月下旬，爱沙尼亚当局开始移除塔林这个繁忙海港城市一个公园的二战苏军士兵铜像，同情俄罗斯的僵尸网络第一次让世人真正地感受到了僵尸网络的可怕，攻击者使用了分布式拒绝服务攻击（DDOS）。利用数据轰炸网站的手段，攻击者不仅能够瘫痪一个国家的服务器，而且也能够让路由器、网关等专门传送网络数据的设备失去作用。为了让这种攻击效果加倍，黑客们利用僵尸软件（bot）侵入了全球的计算机中，这种被侵入的电脑组成了僵尸攻击网络，它们充当了攻击网站的主要进攻武器。爱沙尼亚一方获得的数据是正常流量的几千倍，5月10日，数据负担依然沉重，爱沙尼亚最大的银行被迫关闭自己的网络服务一小时多。这让银行至少损失了1百万美元，这一次攻击极大地引起了各国网监部门的重视。 为了降低僵尸网络的威胁，欧美地区已经开始尝试采用黑名单方式屏蔽僵尸网络控制服务器，我国大陆的大量IP地址面临着被列入黑名单的危险，然而更危险的是，我国大量主机已经在用户毫不知情的情况下被黑客暗中控制，僵尸网络已经成为威胁我国网络与信息安全的最大隐患。目前，中国互联网用户已达1.62亿户，仅次于美国，互联网连接主机数占全世界的13%；根据赛门铁克最近的统计，中国是受僵尸病毒感染的电脑最多的国家，占感染总数的78%，成为拒绝服务攻击最频繁的攻击对象[1]。 2僵尸网络 僵尸网络己经逐渐成为互联网的主要威胁之一，但目前仍然没有统一给出僵尸网络的定义，反病毒领域对僵尸程序也没有明确的定义。2005年网络与信息安全技术研讨会上，国家计算机网络应急技术处理协调中心和北京大学计算机科学技术研究所信息安全工程研究中心的狩猎女神项目组对僵尸网络的定义如下僵尸网络指的是攻击者利用互联网秘密建立的可以集中控制的计算机群。其组成通常包括被植入“僵尸”程序的计算机群、一个或多个控制服务器、控制者的控制终端等。 3Botnet结构和原理以及危害 Bot的种类很多，主要有IRC Botnet、AOL Botnet、PZP Botnet等。其中最广泛的是IRC Bot，它利用IRC协议相互通信[2]，同时攻击者利用该协议进行远程控制，在IRC Bot植入被攻击者主机后，它会主动连接IRC服务器，接受攻击者的命令。下面就IRC Rot方式进行分析。 3．1IRC Botnet结构 Botnet的典型结构如图1。被安装在主机中的bot能够自己拷贝到一个安装目录，并能够改变系统配置，以便开机就能够运行。攻击者首先通过介入一个扫描和攻击漏洞程序精心编写一个bot或者修改能够得到的bot来获得将要投放的bot，这些bot能够模拟IRC客户端IRC服务器进行通信，然后利用bot某段网络，一旦发现目标，便对目标进行试探性攻击[3]。 A Discussion of the Botnet Network Attack ZOU Benna (Party School of CPC Huludao Municipal Committee,Anshan125000) Abstract：The Botnet is a kind of net controlled by hacker who spread bot program and control fall victim computers by any way.The Botnet is different from other kind of net,just because it is much more dangerous.This paper includes the princip－ium,harm and anti-step of the Botnet. Key word：Botnet；IRC；Control Server 本文收稿日期：2008年10月21 日图1IRC Botnet结构图 78 --
复杂网络理论及其研究现状
复杂网络理论及其研究现状 复杂网络理论及其研究现状 【摘要】简单介绍了蓬勃发展的复杂网络研究新领域，特别是其中最具代表性的是随机网络、小世界网络和无尺度网络模型；从复杂网络的统计特性、复杂网络的演化模型及复杂网络在社会关系研究中的应用三个方面对其研究现状进行了阐述。 【关键词】复杂网络无标度小世界统计特性演化模型 一、引言 20世纪末，以互联网为代表的信息技术的迅速发展使人类社会步入了网络时代。从大型的电力网络到全球交通网络，从Internet 到WWW，从人类大脑神经到各种新陈代谢网络，从科研合作网络到国际贸易网络等，可以说，人类生活在一个充满着各种各样的复杂网络世界中。 在现实社会中，许多真实的系统都可以用网络的来表示。如万维网（WWW网路）可以看作是网页之间通过超级链接构成的网络；网络可以看成由不同的PC通过光缆或双绞线连接构成的网络；基因调控网络可以看作是不同的基因通过调控与被调控关系构成的网络；科学家合作网络可以看成是由不同科学家的合作关系构成的网络。复杂网络研究正渗透到数理科学、生物科学和工程科学等不同的领域，对复杂网络的定性与定量特征的科学理解，已成为网络时代研究中一个极其重要的挑战性课题，甚至被称为“网络的新科学”。 二、复杂网络的研究现状 复杂网络是近年来国内外学者研究的一个热点问题。传统的对网络的研究最早可以追溯到18世纪伟大数学家欧拉提出的著名的“Konigsberg七桥问题”。随后两百多年中，各国的数学家们一直致力于对简单的规则网络和随机网络进行抽象的数学研究。规则网络过于理想化而无法表示现实中网络的复杂性，在20世纪60年代由Erdos和Renyi（1960）提出了随机网络。进入20世纪90年代，人们发现现实世界中绝大多数的网络既不是完全规则，也不是完全随机
信息网络安全威胁及技术发展趋势
Expert's Forum 专家观点https://www.sodocs.net/doc/7918498733.html, Expert's Forum 专家观点
互联网及IT技术的应用在改变人类生活的同时，也滋生了各种各样的新问题，其中信息网络安全问题将成为其面对的最重要问题之一。网络带宽的扩充、IT应用的丰盛化、互联网用户的膨胀式发展，使得网络和信息平台早已成为攻击爱好者和安全防护者最激烈斗争的舞台。Web时代的安全问题已远远超于早期的单机安全问题，正所谓“道高一尺，魔高一丈”，针对各种网络应用的攻击和破坏方式变得异常频繁，安全防护也在不断发展。 本文对当今信息网络安全应用中的攻防热点问题作了较为深入的分析，首先分析了当前网络环境下的主要威胁趋势，重点阐述了新网络时代下主要的网络安全攻击方式，进而从安全博弈的角度探讨了漏洞挖掘的新发展方向，最后阐述了近期主要的安全技术发展趋势和技术热点问题。 1. 信息网络安全威胁的主要 方式 1.1 信息网络威胁的趋势分析 当今的信息化发展及演变已极大改变了人类的社会生活，伴之信息 化快速发展的信息网络安全形势愈加严峻。信息安全攻击手段向简单化综合化演变，而攻击形式却向多样化复杂化发展，病毒、蠕虫、垃圾邮件、僵尸网络等攻击持续增长，各种软硬件安全漏洞被利用并进行攻击的综合成本越来越低，而内部人员的蓄意攻击也防不胜防，以经济利益为目标的黑色产业链已向全球一体化演进。表1总结了国内外主要公司及媒体对2009年信息网络安全威胁的趋势分析。 本文主要基于近期安全威胁的主要发展趋势，探讨当前信息网络时代下主要的安全攻击种类及演进模式，分析了目前影响最为常见木马、僵尸网络、蠕虫等恶意软件，无线智能终端、P2P及数据泄露等内部攻击。 1.2 新时期下的安全攻击方式 1.2.1 恶意软件的演变 随着黑色地下产业链的诞生，木马、蠕虫、僵尸网络等恶意软件对用户的影响早已超过传统病毒的影响，针对Web的攻击 成为这些恶意软件新的热点，新时期下这 些恶意软件攻击方式也有了很多的演进： 木马攻击技术的演进。网页挂马成 为攻击者快速植入木马到用户机器中的最 常用手段，也成为目前对网络安全影响最 大的攻击方式。同时，木马制造者也在不 断发展新的技术，例如增加多线程保护功 能，并通过木马分片及多级切换摆脱杀毒
基于异常行为监控的僵尸网络发现技术研究
专家新论 本栏目由网御神州科技有限公司协办 ４４ 赵佐，蔡皖东，田广利 （西北工业大学计算机学院，陕西 西安 ７１００７２） 【摘 要】僵尸网络作为近年来危害互联网的重大安全威胁之一，引起了研究者的广泛关注。论文通过分析僵尸网络工作过程中各阶段表现出的异常行为特征，提出了基于异常行为监控的僵尸网络发现技术，详细阐述了僵尸网络发现系统的原理及系统框架结构，并对其关键技术进行了设计实现。【关键词】僵尸网络；异常行为特征；发现机制；监控规则 【中图分类号】ＴＰ３９１ 【文献标识码】Ａ 【文章编号】１００９－８０５４（２００７） ０９－００４４－０３ Research on technology for Botnet Detection Based on Abnormal Behavior M onitoring Z H A O Z u o , C A I W a n -d o n g , T I A N G u a n g -l i (S c h o o l o f C o m p u t e r S c i e n c e , N o r t h w e s t e r n P o l y t e c h n i c a l U n i v e r s i t y , X i ?a n S h a n x i 710072, C h i n a ) 【Abstract 】I n r e c e n t y e a r s , B o t n e t h a s b e e n o n e o f t h e e m e rg i n g s e r i o u s th r e a t s t o t h e I n t e r n e t a n d a t t r a c t e d w i d e a t t e n -t i o n f r o m r e s e a r c h e r s . B y a n a l y z i n g t h e c h a r a c t e r i s t i c s o f a b n o r m a l b e h a v i o r s h o w n b y B o t n e t a t i t s d i f f e r e n t s t a g e s , t h e p a p e r p r o p o s e s a B o t n e t -d e t e c t i n g m e t h o d b a s e d o n a b n o r m a l -b e h a v i o r -m o n i t o r i n g , d e s c r i b e s t h e p r i n c i p l e a n d t h e s t r u c -t u r a l f r a m e w o r k o f t h e s y s t e m , i n c l u d i n g t h e d e s i g n a n d i m p l e m e n t a t i o n o f i t s k e y t e c h n o l o g y .【Keywords 】b o t n e t ; a b n o r m a l b e h a v i o r ; d e t e c t i n g m e t h o d ; m o n i t o r i n g r u l e s 基于异常行为监控的 僵尸网络发现技术研究 ＊ ０ 引言 僵尸网络（Ｂｏｔｎｅｔ）是指控制者和大量感染僵尸程序（Ｂｏｔ）主机之间形成一对多控制的网络，是近年来危害互联网的重大安全威胁之一。攻击者利用Ｂｏｔｎｅｔ远程控制大量僵尸计算机（Ｚｏｍｂｉｅ）作为攻击平台，实施各种恶意行为。由于Ｂｏｔｎｅｔ能够实施众多攻击行为并从中获取经济利益，Ｉｎｔｅｒｎｅｔ上Ｂｏｔｎｅｔ的数量和规模急剧膨胀，技术日趋成熟和复杂，逐渐发展成规模庞大、功能多样、不易检测的恶意网络，对互联 网的安全构成了不容忽视的威胁。 本文根据Ｂｏｔｎｅｔ在工作过程各阶段表现出的异常行为特征，提出基于异常行为检测的Ｂｏｔｎｅｔ发现思路，详细阐述了系统设计及关键技术的实现。 １ 僵尸网络结构及其工作过程分析 １．１ 僵尸网络结构 Ｂｏｔｎｅｔ并不是物理意义上具有拓扑结构的网络，可以认为是一个受控逻辑网络［２］。网络架构依据控制和通信方式分为ＩＲＣ Ｂｏｔｎｅｔ、ＡＯＬ ｂｏｔｎｅｔ和Ｐ２Ｐ Ｂｏｔｎｅｔ三大类，现有大多数Ｂｏｔｎｅｔ都采用ＩＲＣ协议。典型ＩＲＣ Ｂｏｔｎｅｔ结构采用 了命令与控制体系结构，如图１所示。 １．２ Ｂｏｔｎｅｔ工作过程分析 Ｂｏｔｎｅｔ工作过程分为传播、加入、等待和控制四个阶段。（１） 传播阶段：Ｂｏｔｎｅｔ控制者通过几种手段传播Ｂｏｔ控制一定规模的僵尸主机。研究发现，有些Ｂｏｔ具有自动扫描大规模网段，利用系统漏洞和弱口令等手法查找脆弱主机进行传播，传播方式与蠕虫相类似。
复杂网络的某些性质研究及其应用
复杂网络的某些性质研究及其应用 自从Watts,Strogatz 1998年发现真实网络的小世界特性以来,复杂网络融合了图论、工程数学、计算机理论、社会科学等学科的有关理论与成果,已成为了一门单独的学科。经过十多年的研究,科学家们已经发现了一些典型复杂网络模型如小世界网络模型、无标度网络模型、确定性小世界网络模型等,同时也发现了这些典型网络模型的一些主要特性。 本文围绕复杂网络的小世界现象,针对典型复杂网络模型重点研究了网络节点度序列长度特性、电阻距离特性及其应用;基于代数图论中的凯莱图（Cayley）模型在随机化加边后也同样具有复杂网络的小世界特性,论文结合无线传感器网络和数据中心网络的应用需求,同时研究了基于代数图论的具有小世界特性的复杂网络模型及应用。论文主要成果如下:（1）在肖文俊等人提出复杂网络度序列长度新特性的基础上,论文从理论上证明了具有扩展幂律分布、泊松分布、指数分布的复杂网络模型的度序列长度的新特性:即度序列长度l与 log2N是同级别的结论,进一步完善了肖文俊等人的结论。 实验仿真结果及现实网络的数据验证了该结论的有效性。该结论从理论上解释了为什么现实世界的网络直径不大的问题,可以作为复杂网络的基本特性之一,同时论文提出了基于复杂网络的度序列长度的复杂网络模型。 针对复杂网络的搜索问题,论文完成了最短路径算法和最大度算法的仿真实验,结果表明在复杂网络中基于最大度的搜索算法相比基于最短路径的搜索算法更有效。（2）论文研究了复杂网络中的电阻距离特性及其在社团划分中应用的需求,提出了结合节点中心性指标与电阻距离的社团划分算法。 论文选择了节点度中心性、接近度指标、特征向量、聚类系数及最短路径等
复杂网络链路预测研究现状与展望
复杂网络链路预测的研究现状及展望 吕琳媛 前言：做链路预测这个方向有一年多的时间了，有一些收获和体会。一直想写一个综述进行总结，总是希望这个综述尽可能的包括更多更全面的信息，但是新的思想和结果源源不断的涌现，所谓的综述也就无限期的搁置了下来。前不久刚刚和伟平合作发表了一篇关于利用网络局部随机游走进行链路预测的文章，借此文发表之动力，总结一下链路预测这个方向的研究进展以及展望。希望该文能对那些正奋战在这个方向上和希望在此领域有所建树的科研工作者有所帮助和启迪。 （本文中所提到的具体的技术方法以及实验结果将在另一篇中文综述中详细介绍。） 1．链路预测及其研究意义 网络中的链路预测(Link Prediction)是指如何通过已知的网络节点以及网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的可能性[1]。这种预测既包含了对未知链接（exist yet unknown links）的预测也包含了对未来链接（future links）的预测。该问题的研究在理论和应用两个方面都具有重要的意义和价值。 近年来，随着网络科学的快速发展，其理论上的成果为链路预测搭建了一个研究的平台，使得链路预测的研究与网络的结构与演化紧密联系起来。因此，对于预测的结果更能够从理论的角度进行解释。这也是我们相比计算机专业的人研究链路预测的优势所在。与此同时，链路预测的研究也可以从理论上帮助我们认识复杂网络演化的机制。针对同一个或者同一类网络，很多模型都提供了可能的网络演化机制[2, 3]。由于刻画网络结构特征的统计量非常多，很难比较不同的机制孰优孰劣。链路预测机制有望为演化网络提供一个简单统一且较为公平的比较平台，从而大大推动复杂网络演化模型的理论研究。另外，如何刻画网络中节点的相似性也是一个重大的理论问题[4]，这个问题和网络聚类等应用息息相关[5]。类似地，相似性的度量指标数不胜数，只有能够快速准确地评估某种相似性定义是否能够很好刻画一个给定网络节点间的关系，才能进一步研究网络特征对相似性指标选择的影响。在这个方面，链路预测可以起到核心技术的作用。链路预测问题本身也带来了有趣且有重要价值的理论问题，也就是通过构造网络系综并藉此利用最大似然估计的方法进行链路预测的可能性和可行性研究。这方面的研究对于链路预测本身以及复杂网络研究的理论基础的建立和完善，可以起到推动和借鉴的作用。 链路预测研究不仅具有如上所述的理论价值，其更重要的意义还是体现在应用方面。很多生物网络，例如蛋白质相互作用网络和新陈代谢网络，节点之间是否存在链接，或者说是否存在相互作用关系，是需要通过大量实验结果进行推断的。我们已知的实验结果仅仅揭示了巨大网络的冰山一角。仅以蛋白质相互作用网络为例，酵母菌蛋白质之间80%的相互作用不为我们所知[6]，而对于人类自身，我们知道的仅有可怜的0.3%[7,8]。由于揭示这类网络中隐而未现的链接需要耗费高额的实验成本。那么如果能够事先在已知网络结构的基础上设计出足够精确的链路预测算法，再利用预测的结果指导试验，就有可能提高实验的成功率从而降低试验成本并加快揭开这类网络真实面目的步伐！实际上，社会网络分析中也会遇到数据不全的问题，这时候链路预测同样可以作为准确分析社会网络结构的有力的辅助工具[9,10]。除了帮助分析数据缺失的网络，链路预测算法还可以用于分析演化网络，即对未来
复杂网络度分布的研究
复杂网络度分布的研究 (1) 1. 复杂网络的研究对象........................................................................................ 1 2. 复杂网络的研究内容........................................................................................ 1 3. 复杂网络中的三个概念.................................................................................... 1 4. 复杂网络的几何量............................................................................................ 1 5. 社会网络与其它网络的判别指标.................................................................... 2 6. 随机网络－ER 模型 ......................................................................................... 2 7. 随机网络的研究宗旨........................................................................................ 2 8. 子图出现的临界概率........................................................................................ 3 9. 子图临界概率存在的证明................................................................................ 3 10. BA 模型与度的幂指分布 ................................................................................ 4 11. BA 模型构造的网络度符合幂指形式的证明 (4) 复杂网络度分布的研究 － 复杂网络度分布的研究 河北工大硕士论文 陈德伟 指导教师：何文辰 1. 复杂网络的研究对象 用来描述真实网络统计特征的物理量主要有度分布、平均路径长度、聚集系数、相关系数等，都是力求更加详细、精确的描述复杂的真实网络。寻找网络各种宏观统计性质的微观生成机制一直都是网络研究中一项极具意义而且也是极具挑战性的工作。现在人们已经对复杂网络的小世界性质和无标度特征的微观生成机制有了一定的认识，但是度的相关性、团体性质、分层结构等更为复杂的宏观统计性质的微观生成机制的探索还处于起步阶段。对不同结构复杂网络的鲁棒性和脆弱性(vulnerability)的研究也是一个具有广泛应用价值的课题。 2. 复杂网络的研究内容 目前，复杂网络研究的内容主要包括：网络的几何性质，网络的形成机制，网络演化的统计规律，网络上的模型性质，以及网络的结构稳定性，网络的演化动力学机制等问题。 3. 复杂网络中的三个概念 三种概念在当代对复杂网络的思考中占有重要地位。第一，小世界概念；第二，集群即集聚系数的概念；第三，幂律的度分布概念。 4. 复杂网络的几何量 直径：网络的直径是指任意两个顶点之间最短路径的最长长度(包含的边数)。 集聚系数：对于网络中的任意一个节点i 来说，其集聚系数i C 表示与i 相连的节点中任意两点之间相互连接的概率。它可定义如下：如果与节点i 相连的点的数目为i k ，则在这i k 个节点之间最多存在2/)1(-k k 条边，而实际存在的可能只有i E 条边，则得到i 的集聚系数i C 为 ) 1(2-= i i i i k k E C .
复杂网络理论研究状况综述
■现代管理科学■2010年第9期 一、复杂网络概述 1.复杂网络演化过程。用网络的观点描述客观世界起源于1736年德国数学家欧拉Eular使用图论解决哥尼斯堡七桥问题。数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又如最近邻环网，它总是会让你想到一群手牵着手、围着篝火跳圆圈舞的姑娘。也就是说网络中任意两个节点之间的联系遵循既定的规则。用得最多的规则网络是由N个节点组成的环状网络，网络中每个节点只与它最近的K个节点连接。规则网络的特点就是：每个节点的近邻数目都相同。但是对于大规模网络而言由于其复杂性并不能完全用规则网络来表示。 到了20世纪50年代末，Erdos&Renyi想出了一种新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。这是一种完全随机的网络模型，数学家把这样生成的网络叫做随机网络。随机网络ER模型的描述如下：给定网络节点总数N，网络中任意两个节点以概率P连接，生成的网络全体记为G（N，P），构成一个概率空间。由于网络中连线数目是一个随机变量X，取值可以从0到N（N-1）/2。随机网络在接下来的40年里一直被很多科学家认为是描述真实系统最适宜的网络。 规则网络和随机网络是两种极端的情况，随着信息技术的飞速发展，科学家们发现对于大量真实的网络系统而言，他们既不是规则网络，也不是随机网络，而是介于两者之间，具有与前两者皆不同的统计特征的一种复杂网络。1998年，Watts&Strogatz提出了W-S网络模型，通过以概率p切断规则网络中原始的边并随机选择新的端点重新连接，构造出一种介于规则网络和随机网络之间的网络—— —小世界网络（Small-world Networks）。显然，当p=0时，相当于各边未动，还是规则网络；当p=1时就成了随机网络。1999年，Barabasi&Albert在Science上发表文章指出，许多实际的复杂网络的连接度分布具有幂律函数形式，由于幂律分布没有明显的可度量特征，该类网络又被称为无标度网络。 2.复杂网络的统计性质。复杂网络的不同的统计性质决定了不同的网络内部结构，而结构又决定了系统的功能。所以，我们先了解一下复杂网络的相关统计性质。 （1）度及度分布。在网络中，节点的度是与目标节点相连的边的条数。即与该节点相邻的节点的数目，朋友的个数。而网络的度