模块化无标度网络模型的建立与仿真分析毕业设计(论文)(编辑修改稿)

模块化无标度网络模型的建立与仿真分析毕业设计(论文)(编辑修改稿)内容摘要：

式可等价定义为 相连的三元组的数量与节点 相连的三角形的数量与节点 iiiC （ 24） “ 与 顶 点 i 连接 的三元组 ” 是指 涵盖顶 点 i 的三个 顶 点，并 存在 从 顶 点 i 到 其他两个 顶 点的两条边。 度与度分布 经过科学家们数年的努力，我们发现度是描述节点特征的主要指标。 节点 ik 的度是 说 与节点 ik 连接的结点 个数。 对于有向网络，节点的度 又 分为出度和入度。 节点的出度是 指 该节点指向其 它 节点的边的数目。 节点的入度是指从其 它 节点指向该节点的边的数目。 通俗来讲，节点的度越大就意味着这个节点在这个系统中 连接的节点越多， 扮演的角色 越重要。 我们把一个 网络中所有 包含的 节点的度的平均值 叫做该 网络的平均度，用 k表示。 网络中节点的度的分布情况可用函数 )(kp 来描述。 一种说法是， )(kp 表示在 一个系统 中随机选择的 顶 点的度为 k 的概率。 另 一种 说法 是 系统 中 顶 点度数为 k 的 顶 点数 与顶 点总数的 比。 完全随机网络的度分布近似其 形态 在 距离最大 值 k 很远的地方 处呈指数下降。 这意味着 并不存在 kk 的节点，这样的网络叫做均匀网络。 经过许多科学家证明 ，许多实际网络的度分布 事实上不 符合 泊松 分布，而是符合幂率分布。 南华大学计算机科学与技术学院毕业设计（论文） 我们把任意挑选到的顶 点 的 度数为 k 的概率 , 记为 )(kp ,k 为度数 ,可以更直观的告诉我们该节点在该系统中所扮演的角色。 除了这三种最基本的统计 属性 以外， 复杂网络还具有许多与传统网络， ER 网络等网络不一样的统计特征，这里面 最 值得关注 的莫过于小世界性，和无标度 属性。 经过长期的研究表明，规则网络具有比较大的剧烈系数，和较大的平均路径长度：随机网络具有较小的聚类系数和小的平均路径长度。 而后，科学家 Watts 和 Strogatz开创了以后新的 理论， 以 一 个很小的概率 p ，打 断规则网络中原 有 的边， 然后 随机选择新的节点重新连接在一起， 就形成了 一 个 新的网络。 这个网络与我们过去所研究的 ER 网络和规则网络均不相同 ，介于他们二者之间。 它具有大的聚类系数和小的平均路径长度。 往后，科学家把这种特性的定义为小世界性，把这种网络定义为小世界网络 ，如图 所示。 图 小世界网络拓扑结构图 往后， 在漫长的实验道路中 ，科学家们发现真实网络都具有小世界性。 同时，科学家们还发现真实网 络的节点 按照 幂律分布。 这里 的顶 点的度是指该 顶 点所 具 有的 连接 节点的 个数。 节点服从幂律分布是指， 可以用一个幂律函数近似的表示该节点与该特性的度之间的联系。 幂律函数曲线 如图 所示，是一条缓慢滑坡的曲线 ，这就告诉我们，在这个网络中可以找到度很大的节点。 图 BA 网络度分布图 南华大学计算机科学与技术学院毕业设计（论文） 对于传统的规则网络和随机网络 来说 ，度 值在一个很狭窄的区间内取值，所以我们基本找不到和平均度值相差较大的节点。 那么我们就可以把度看做是考察一个节点的重要指标。 我们就把这种顶点的度的分布满足幂律分布的网络叫做无标度网络，把这 种特性叫做无标度特性，如图 所示。 图 无标度网络拓扑结构图 除了 上文介绍的 小世界性和无标度性，真实网络还存在许多统计上的特性，如，混合模式特性，度相关性，超小世界性等，有兴趣的读者可以查阅相关文献。 在此，不一一介绍。 典型无标度模型介绍 由上文我们可以知道，在小世界网络的研究兴起之后， 后期有大量的科研学者投身到复杂网络的研究中。 他们发现许多现实网络在统计特性上存在普遍共性，其中最显著的就是他们的节点度分布都服从幂律分布。 这一发现逐渐演化成无标度网络， 形成了无标度网络模型的建立，最 具代表性的便是经典 BA 无标度网络模型。 BA 模型 源于对科学的热爱，对真理的探索， 1998 年， Barabasi 和 Albert 等开展了一项关于万维网 (World Wide Web)的研究。 他们本认为其结果应该是一个符合随机网络的“钟形图”，即泊松分布，但是他们却发现结果天壤之别。 Inter 上网页基本由少数几个高连通的页面相互串接。 只有不到 20%的页面连接大于 4，其他均小于 4。 这些有高连通的页面却只占整个网络的极小部分，只有不到万分之一。 他们计算了 k 个南华大学计算机科学与技术学院毕业设计（论文） 连接着 Inter 的页面，发现这些页面 的连接也遵从幂律分布。 于是 在 1999 年， Barabasi和 Alberty提出了史上最重要的一种离婚，即构造无标度网络的演化模型。 他们也采取了与 Price 相类似的办法。 Barabasi 和 Albert 认为随机网络之所以不能解释集散节点存在的原因 ： 是因为随机网络 不 能 表现 现实网络中的两个重要 属性 ：第一，增长特性，我们的现实网络每天都不在不断变化，每天都有新的节点产生并加入到我们的网络中来，每天也都有旧的节点消失，我们的网络也是通过不断演化，更新而来的，而随机网路在安置连接之前能够得到所有的网络节点，而节点数在网络 中是固定的，一成不变的。 第二，优先连接机制，随机模型都假设在添加新的连接时，概率都是均匀的，而事实上却不是如此，许多真实网络都是择优连接的。 例如 Inter， 人们 在选择页面连接到何处时， 本 可从多达数亿的网站中选择，但是我们大部分人 仅仅 熟悉 Inter 中的一小部分，例如 百度，酷狗这些网 页，这一小部分分 事实上 含有连接 度 较多的网站，只要我们连接到这些节点，便可以连接到数以万亿的其他节点，这一偏好就等同于增强了他们的偏好，这种“择优连接”的过程，也发生在其他网络当中。 比如在好莱坞，连接着关系较多的 明星往往更 便于 得到 新锐们 的 关注。 又比如 在我们 每天所使用 的互联网上， 一些 端口 很多的路由器 由于担负着繁重的工作，一般情况下会 被分配到更多的带宽， 以便更好的工作，服务于社会。 因此 我们便更喜欢 把自己的电脑 连接到这些路由器上 ，从而得到更快，更高效的网络服务。 我们可以通过 图 来更好的理解。 图 真实网络示意图 在过去，我们常常说在我们的网络节点集散中，出现了“富者更富”的现象。 这又是为什么呢。 无标度网络模型给出了解释。 介于增长特性和优先连接机制的出现，当网络中有新的节点产生时，他在选择自己的连接对象时比较喜欢和已经 有较南华大学计算机科学与技术学院毕业设计（论文） 多连接的节点相连接。 正如我们在生活中，如果让我们选择交朋友的对象，恐怕许多人都会选择已经有很多朋友的人来建立关系。 随着时间的推移，这种趋势愈发明显，从而造成了集散现象的产生。 显然，我们可以推论“富者更富”现象在以往的随机网络中是不可能出现的。 随着 BA 模型的发明与广泛推广，复杂网络的历史又翻开了一页新的篇章。 人们在网络研究的历史长河中铸就了新的里程碑。 此后，有更多的学者开始了对复杂网络的研究与探索，他们提出了诸如加速增长，局域时间，网络老化，网络适应性以及非线性优先连接机制等。 但是我们必须承认一点 ，我们只能说绝大多数网络是无标度网络，而不能一概而论的说所有的现实网络都是无标度网络，还有小部分网络服从指数分布，截断形式等，这也是我们研究的科学性所在。 如图 就是一个幂律分布的网络。 图 典型的具有幂律分布的网络 蛋白质网络 模块化无标度网络模型 我们在漫长的学习与探索过程中，明白一个道理。 即使是大家普遍认同的，我们也不能一概而论的，更不能断章取义。 我们在上文中说，许多现实的系统网络都有小世界性和无标度性，换言之他们具有许多共同的全局结构特征。 但是，他们还是有区别的，要 不然我们怎么能说他们终究是不同的网络，在局部方面看，各个网络还是各有异同的。 于此，我们就必须再了解这些网络的局部所存在不一样的地方，探讨这些不同产生的机理，过程，后期的发展状况。 举个例子，我们生物界的细胞网络，细胞是靠各种功能联系在一起的，功能类似的细胞高度集中，形成了一个团南华大学计算机科学与技术学院毕业设计（论文） 体，我们把这个团体叫做模块。 那么到底什么是模块呢。 一般的定义是，一组物理性质或者功能性质而聚集在一起，共同工作，从而完成一个特例的功能的节点。 在我们生活中许多地方，都具备了模块。 比如说，我们现在所熟知的 FACEBOOK，博客，微博，都是 由许多有共同兴趣的人聚集在一起的：再比如说，在一个汽车的制造过程中，不管是发动机，还是轮胎，都是由一个特定的群体专业生产制造的，所以说高度模块化在我们的生活中随处可见，而模块化的工作，生活，是现代社会的必要的产物。 例如 在生物系统中 ，相对固定的 核糖核酸 和 脱氧核糖核酸 ，就是我们生命活动的基础。 事实上，一个系统中的绝大多数分子或者是具有模块化活动的一个细胞内的联合体的一部分（如核糖体），或者是参与到一个功能上的更广的模块以作为一个相对独立过程的调控单元（如信道中的信号放大）。 那么网络中的模块是如何构成的呢。 近期 的研究表明，模体可能是复杂网络的基本模块 ，也就是我们所说的基本组成部分。 假设两个网络具有相同的规模，那么无标度网络要比随机网络具有较高的聚类系数，即我们所说的高聚类行。 所谓的高聚类行就是指这个网络的某一部分，由各种高度链接的顶点组成，成型一个团体也就是模块，而这也正是出现某一个功能模块的前提。 在一个网络内部的某个模块显示了这个网络在一定层次上的链接模式。 尽管如此，但是这么多模块也不是所有的模块都是重要模块的。 在一个复杂网络中，可以包括各种各样的模块，如三角形模块，正方形模块，菱形模块等。 其中的一些模块所占的 比例很高，而另一些模块却占有较低的比例。 这些比例高的模块就叫做模体。 我们知道，一个复杂网络都是由他内部特定的模块所表示的，那么如果我们可以清晰准确的辨识出这些模块，就有利于我们了解这个网络的局部特征，进而了解整个网络。 南华大学计算机科学与技术学院毕业设计（论文） 第三章 BA 模型与模块化模型算法比较 BA 模型 通过上文的介绍，我们知道随机网络和“小世界”网络的度分布遵从泊松分布。 该分布的特点主要表现在在其均值处有一个峰值，而两侧则呈现出逐渐递减，导致这样的网络在后来也被称为指数网络（ exponential works）。 随着科技的发展 ，技术的进步，后来人们提出了复杂网络的概念，例如我们熟悉的万维网，互联网，英特网等，以及生物界的神经系统网，生物体的新陈代谢网等的节点的度分布都遵从幂律分布。 由于这种网络的顶点关联方式并没有显著的特别属性，我们就把他们称为无标度网络。 为了进一步给大家解释这种网络中节点的度分布服从幂律分布的现象，Barabasi和 Albert 创造了一个无标度网络模型，就是我们现在所广泛研究的 BA 无标度网络模型。 BA 模型的特性 在现实意义中，我们知道一个网络具有幂律度分布固然是有意义的，但是更为重要的是我们要理 解幂律分布的产生机理。 由 Barabasi 和 Albert 创建的 BA 无标度网络模型实际上阐述了真实网络的两个重要特性 : (1) 增长特性： 我们的网络每天都在变化，用户每天都在增加与退出，网上的网站也在每天更新，每天都有新的页面产生，有旧的页面撤除。 再例如，每天都有新的车辆上户，也有旧的车辆报废 ； 每天都有新的想法产生等等。 所以说，我们的网络规模在不断增长。 而 ER 随即图和 WS 小世界模型中网络节点数是固定的，这不符合实际网络的发展规律。 （ 2）优先连接特性： 每当有新的节点加入到已知网络中时，他们在选择邻居的时候都愿意选择 那些已经有很多节点连接的节点作为自己的邻居，也就是我们所说的“马太效应”或者说“富者更富”现象。 举个例子，我们在做毕业设计时，我们喜南华大学计算机科学与技术学院毕业设计（论文） 欢参考借鉴那些名人学者的学术研究报告。 在我们的朋友圈中，可能很多人都认识某几个特别受欢迎的人，但是这些人互相却并不认识。 而在 ER 随即图中，两个节点之间是否有边相连是完全随机确定的，在 WS 和小世界模型中，长程边的端点也是完全随机确定的。 BA 模型的算法 1）增长性：开始 时创建 少量节点 0m ，在每个时间间隔添加一个具有  0mm条边的新节点（连接到已存在于系统中的 m 个节点上）。 2）择优连接： 当选择与新节点连接时，假设新节点连接到节点 i的概率  取决于该节点的连通度 ik ，即   .i iii kkk （ 31） 经过这样的计算后，我们在经过 t时刻以后，就可以得到一个 tmN  0 ， mt条边的 BA无标度网络模型。 我们可以看到网络整体上呈现幂律分布 kP ： k ，幂指 数 3。 这个结果在后来的多种理论方法和实验结构都得到了证明，实验结果如图。 图 BA网络度分布图 南华大学计算机科学与技术学院毕业设计（论文） 模块化无标度网络模型 随着 近 年来对许多实际网络的研究及探索，人们发现，他们。