已阅读5页,还剩42页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 中文摘要中又摘要 许多系统可以用复杂网络来描述,如万维网、因特网、科学家合作网等等网 络的无标度特性是复杂网络的个重大发现实证研究表明许多现实网络都是无标 度网络根据b a 模型的局限性及现实网络的特性,本文对无标度网络的演化模型 进行了研究,提出了三个演化模型 ( 1 ) 一个具有节点适应度的无标度网络模型在每个时间间隔,网络以概率p 增加个新点,并以适应度择优选择m 个旧点与新点连接,产生m 条新边;以概 率1 一p 按度数择优的规则在旧点之间生成m 条新边对于一些特定的概率密度函 数p ( x ) 和率函数f ( x ,y ) ,该网络的度分布具有幂律尾部,且幂律指数2 7 + o 。 ( 2 ) 一个节点具有初始吸引度的网络演化模型在本模型中,每一个点有随机 的初始吸引度并假设其期望存在在每一时间间隔内,向网络中添加一个新点,连 接到仇( m o ) 个不同的已有节点上,并假设新节点连接到旧点t 的概率依赖 ( 正比) 于旧点i 的度数与初始吸引度之和对于一些特定的概率密度函数,该网 络的度分布具有幂律尾部 ( 3 ) 几个局部世界网络演化模型其中,从网络中随机选取一个随时间变化的点 数砉( 8 1 ) 来作为局域世界,利用平均场方法,得到具有幂律尾部的度分布并进 一步考虑了以概率p 随机选取m 个节点作为局域世界,以概率1 一p 选取( 口1 ) 个节点作为局域世界,也得到具有幂律尾部的度分布 关键词:复杂网络,无标度网络,加权网络,演化模型,度分布,集群系数, 适应度 中文文摘 中文文摘 复杂网络就是具有复杂拓扑结构和动力学行为的大规模网络,现实世界的许多 系统都是复杂网络,例如,w w w 、i n t e r n e t 、引文网、人际关系网、食物链网、蛋 白质相互作用网、科学家合作网、电力网以及社会网等等 1 9 6 0 年,数学家e r d o s 和r e n y i 提出了随机图理论,开创了研究复杂网络的新纪元此后将近四十年时间 里,随机图一直是人们研究复杂网络的基本模型近年来,两项开创性的工作掀起 了复杂网络研究的新纪元1 9 9 8 年w a t t s 和s t r o g a t z 提出了小世界网络模型( w s 模型) ;1 9 9 9 年b a r a b 缸i 和a l b e r t 提出了以增长和择优为基本机制的无标度网络模 型( b a 模型) 实证研究表明许多现实网络都具有小世界和无标度的特性然而在 许多实际网络中,节点获得新连接的能力除了与节点度有关外,还与其固有的竞争 能力( 适应度) 有关,适应度强的节点可能比那些连接度高但适应度低的节点获得 更多的新边,为了解释这一现象,许多学者进行了探索和研究其中最有影响力的 是g c a l d a r e l l i 等提出了适应度模型( f i t n e s s 模型) 在简单规则下自然界可以呈现复杂结构,而在复杂背景下自然界可以遵循简单 定律,演化模型可以捕捉网络形成的动态特性,能够准确获得各种微观机制对网络 最终结构的影响,对人们掌握网络功能及其动力学有着重要的作用探索复杂网络 的演化机理和模型建立倍受人们的广泛关注 本文主要研究具有适应度的无标度网络,提出几个可以产生无标度网络的演化 模型,主要结果如下s ( 1 ) 基于节点自身特性,提出一个具有节点适应度的无标度网络模型在每个 时间间隔,以概率p 增加一个新点,并以适应度择优选择m 个旧点与新点连接, 产生m 条新边;以概率1 一p 按度数择优的规则在旧点之间生成m 条新边对于 一些特定的概率密度函数p ) 和率函数,( z ,y ) ,证明了该网络的度分布具有幂律 尾部,且幂律指数2 7 0 ) 之下,也得到度分布的无标度特性,且指数为,y = 1 + 三 b e d o g n e 和g j r o d g e r s 3 8 】用率方程方法【2 5 】分析了适应度连接与随机连 接、按度择优连接相结合的两个模型 我们在本文中第二章研究了按适应度择优和按度择优相结合的模型,对于一些 特定的概率密度函数p ( x ) 和率函数( x ,可) ,该网络的度分布具有幂律尾部,且幂 律指数2 ,y 警h 一志, 则网络的度分布为 聊,= 掣= 鼎南 在t 较大时,蒜再1 ,网络的度分布为 k m ( 1 4 3 ) ( 1 4 4 ) p ( k ) - - t 1 i m p ( 圳2 m 2 七一,k r n ,7 = 1 + 万1 = 3 , ( 1 4 5 ) 1 3 福建师范大学李志勇硕士学位论文 即度分布p ( k ) 服从幂律分布,其中度指数,y 与网络的参数m 无关 ( 2 ) 率方程方法 k r a p i v s k y 等 2 5 】提出了用变化率方程方法解决网络演化动力学问题,并利用 变化率方程计算出了一种扩展b a 模型的严格解,考虑t 时刻网络中度数为k 的节 点个数的平均值小吒( t ) ,建立n k ( t ) 的变化率方程,计算网络的度分布 为了方便起见,这里只考虑b a 模型,n k ( 芒) 满足如下微分方程: 掣= m 错一叩豇k g k 丽( t ) 地m ,忌狐 ( 1 4 6 ) 其中右边第一项对应于度为七一1 的节点与新节点相连其度变成k 时,引起眠( ) 的变化;第二项对应于度为k 的节点与新节点相连其度变成七+ 1 ,引起n k ( t ) 的变 化;第三项对应于度为m 的新节点可能引起n k ( t ) 的变化 其中南k y k ( t ) = 2 m r ,在k = 仇时以,m = 1 ;k m 时以,m = o 又七( t ) t 为t 时刻网络中度为七的节点平均值设p ( k ,t ) 表示时刻网络 的度分布,则帆( t ) t p ( k ,) 在亡较大时,假设极限p ( k ) = l i m t + p ( k ,亡) 存在,则 跗) 恕华,k m ( 1 4 7 ) 当t 充分大时,肌( t ) t p ( k ) ,代入式( 1 4 6 ) ,有: 2 p ( k ) = ( 后一1 ) p ( 后一1 ) 一k p ( k ) + 2 以m ,k m ( 1 4 8 ) 由上述方程可以得出: p ( k ) = 2 m ( m 4 - 1 ) k ( k - 4 - 1 ) ( 凳+ 2 ) k m ( 1 4 9 ) 与平均场方法得到的度分布相差无几 ( 3 ) 主方程方法 d o r o g o v t s e v 等 2 6 】提出了主方程方法( m a s t e r - e q u a t i o na p p r o a c h ) ,研究单 个节点在t 时刻度为k 的概率,研究的模型对象是广义b a 模型,与b a 模型不同 1 4 复杂网络的定义及概念 的是考虑到新生节点自身固有的吸引口( 在b a 模型中a = o ) ,进而得到网络的度分 布 为方便表述和计算起见,我们考虑b a 模型,设p ( k ,t i ,t ) 为节点i 在t 时刻度 为k 的概率,利用全概率公式可以得到如下主方程: p ( k , t i , t + 1 ) = 等p ( 七1 ) + ( 1 一去) 础删,后m ( 1 4 1 0 ) 上述方程的边界条件为p ( k ,t ,t ) = 以,m 并假定l i r a t - - - * o o 【p ( 忌,t + 1 ) 一p ( k ,亡) 】存在, 由式( 1 4 1 0 ) ,可以得到t 2 p ( k ,t + 1 ) + k p ( k ,t ) + 2 t p ( k ,t + 1 ) - p ( k ,亡) 】_ ( k - 1 ) p ( k - 1 ,亡) + 2 以,m ( 1 4 1 1 ) 令t o o ,由上述方程可以得出,网络的度分布为 耶) = 端m 仇( 1 4 1 2 ) 可以看出,主方程方法与率方程方法所得到的结果一样,也有p ( k ) 一k - 3 ( k 较 大) ,也接近于平均场方法计算的结果 ( 4 ) 马氏链方法 史定华与陈庆华【2 7 - 2 9 】提出了一种用马氏链计算网络度分布的新方法对于 b a 模型,设( 亡) 表示节点t 在t 时刻的度,他们证明了随时间变化的度序列 ( t ) ,t = i ,t + 1 ,) 是个非齐次马氏链,并给出了具有时间相依的一步转移 概率矩阵只 + 1 ) ,t = 1 ,2 ,根据马氏链理论,由转移概率矩阵p i ( t + 1 ) 给出 了网络在t 时刻的度分布p ( k ,亡) 的矩阵运算表达式根据矩阵p l + 1 ) 具有特殊 的结构,利用矩阵运算性质,他们给出了一种度分布数值计算的新方法,简称马氏 链方法 1 5 福建师范大学李志勇硕士学位论文 第2 章具有节点适应度的无标度网络 前面提到,b a 模型揭示了无标度网络的两个基本原理:网络增长和节点择优 连接在b a 模型中老节点总是以较大的概率获得新边,然而在许多实际网络中, 节点获得新连接的能力除了与节点度数有关外,还与其固有的竞争能力( 适应度) 有关,适应度强的节点可能比那些连接度高但适应度低的节点获得更多的新边, 这就是所谓的。适者生存”规则为了解释这一现象,许多学者进行了探索和研究 f 3 0 - 3 5 】其中最有影响力的是g c a l d a r e l l i 等提出了适应度模型( f i t n e s s 模型) 【3 6 】 本章提出个具有适应度的无标度网络模型每个时间间隔,网络以概率p 增加 一个新点,并以适应度择优选择m 个1 日点与新点连接,产生m 条新边;以概率1 - p 按度数择优的规则在旧点之间生成m 条新边对于一些特定的概率密度函数p ( o ) 和率函数( x ,妙) ,证明了该网络的度分布具有幂律尾部,且幂律指数2 1 + 2 1 具有节点适应度的无标度网络模型 模型2 1 1t 假设网络中每一个节点的适应度为随机变量o ,其概率密度函数为p ) ,且适 应度为z 和y 的两个节点有连接边的率为f ( x ,可) 设莓,7 7 表示任意两个节点的适应度,定义 僻删= 厕鞣羝 网络的演化规则,初始网络有m o 个节点,每一时间间隔 ( a ) 以概率p 增加一个新点,并与网络中已有的m 个节点相连接,产生r n 条新 边,其中以适应度择优的方式选择旧点,即适应度为z 的旧点与新点连接的概率为 适应度为z 的旧点与新点连接的率平均与所有旧点与新点率平均总和之比掣, 其中为亡时刻网络的总点数 ( b ) 以概率1 一p 在旧点之间产生m 条新边;随机选择一点作为新边的初始 第2 章具有节点适应度的无标度网络 点,并以度数择优选择另一端点,即旧点t 被选中的概率为p ( ) = 最,其中 为亡时刻t 点的度数这个步骤被重复m 次 2 2 度分布的解析计算 现在,我们使用平均场方法来推导该网络的度分布记( z ,亡) 表示t 时刻具 有适应度为z 的节点i 的度数则有 掣_ ( 1 - p ) ( 斋+ 嘉( 1 一如m + p 掣等+ 害+ p 丁m f ( x ) ( 2 2 1 ) 1 当p l 时 考虑t 很大时,有n 彤,则微分方程( 2 2 1 ) 的解为 蝴) = e 愕m re - ,铷( 导+ 掣 = 悬两2 字【盟学】+ g ) = t 字g ( 。) 一2 0 一v ) m + p m f ( z ) 】眵( 1 一p ) 】- 1 初始条件为乜( z ,屯) = m ,则g ( z ) = ( m + 6 ) 亡= - 下,所以 ,亡) = ( m + 6 ) ( 兰) 宇一b ( 2 2 2 ) 其中b = 2 【( 1 一p ) + 肌f 0 ) 】眵( 1 一p ) 】 注意到,我们可假设每个节点进入网络都是等可能的,即岛服从 o ,m o + t 】上 的均匀分布,且z 与岛独立,则 f ( k ) = p ( ( x ,t ) 尼) = e ( p 陬( x ,t ) 七lx 】) ,十 = p 【( z ,t ) k p ( x ) d x ,0 = 门1 一志( 揣一m z ) d x 2 当p = 1 时,即演化规则只有适应度择优连接,则方程( 2 2 1 ) 为 o k , ( x ,t )m f ( x ) 巩 r n o + t 。一二;。一 】7 ( 2 2 3 ) ( 2 2 4 ) 福建师范大学李志勇硕士学位论文 初始条件为( z ,岛) = m ,则微分方程( 2 2 4 ) 的解为 坼= m f ( 互糕+ m 当t 较大时 乜( 正,t ) m f ( x ) l n 圭+ m ( 2 2 5 ) 。i 同样地 ) = 小) = z 佃卜丽te 计而k - m f ( k p ( k i ( xt k 1 0 7 1bb _ r 渺出( 2 2 6 ) =,) ) = 【一= - :j e 3 - p ( 一= - 云瓦天) 】j 口( z ) 出 ( 2 2 6 ) , 叼- 广l o , 由于大规模网络的复杂性,度分布的简单表达式难以给出在此,我们只对一些简 单的情况给出度分布的具体表达式 ( a ) 当,( z ,y ) 为常数时,f ( x ) = 1 ,则 ( 1 ) 当p 1 时,b = 2 ( 1 一p + 怖扫一1 ( 1 一p ) ,由( 2 2 3 ) 式得 m ) - 1 一( 揣一厂加肛1 一( 揣一 从而,度分布为 p ( 七) = 百o f ( k ) = r 2 i + 6 ) 一南( 七+ 6 ) 一( 南+ 1 ) o t ( 七十6 ) 一( 南+ 1 ) 所以,度分布具有幂律尾部,即该网络为无标度网络 ( 2 ) 当p = 1 时,即模型里只有适应度择优连接,则由( 2 2 5 ) 、( 2 2 6 ) 两式可 得 悱百o f ( k ) = 磊1 丽t 唧( 一i k - m ) c ce x p ( 一示k ) 此时。度分布为指数分布,该网络没有演化成无标度状态 ( b ) 当,( z ,y ) = x y 时,且假设z 的期望e z 存在,这时有f ( z ) = 彘 1 8 第2 章具有节点适应度的无标度网络 ( 1 ) 当p 1 时,则由( 2 2 3 ) 式有 f ( k ) 1 一鬲南口0 。【( m z + 宁仇e x + 孚m e x ) ( 仇z 4 - 纽pm e x 4 - 字忌e z ) 一1 】南j d ( z ) 如 1 一咖t + 。付【 + 宁e x + 孚e z ) ( z + 垃p e x + 专署忌e z ) 一1 】毒;j d ( z ) d z 为了达到度分布的无标度性质,令 比) - 【枷+ 器等等c 1 1 。1 南艇= 箫c 1 问) 其中口= 宁+ 孚,c = 南一1 从而 跗) = 百o f ( k ) = 熹杀e z ( x o + b e x ) 一南 ( 2 2 7 ) 其中b = 宁+ 垃2 mk ,e x = 因此,度分布 p ( 后) o ( ( 七十矿,y = 巧2 其中d 为常数,且2 ,y + o 。所以,该网络为无标度网络 ( 2 ) 当p = 1 时,则由( 2 2 5 ) 、( 2 2 6 ) 两式可得 f ( 七) = p ( 氟( z ,t ) 2 时,度分布也有幂律尾部 ( c ) 当y ( x ,y ) = z + y 时,且假设z 的期望e z 存在,则f ( x ) = 盎+ i 1 ( 1 ) 当p l 时,则由( 2 2 3 ) 式有 令 聊) 1 一上m o + t 门( 斜,掣协+ ( 1 刊饥,勖他) ( 蚪警掣e x + 生娑也+ e z ) 一南 ) d x pm 咖) = 妇+ 唑燕篙啬舞铲c + l 】- 呻。= 箫c 1 问) 其中a = 宁+ 字,c = 耳2 1 此时,度分布 删= 百o f ( k ) 仪( 七+ 回- 7q = 巧2 ( 2 2 1 0 ) 其中d 为常数,且幂指数2 0 ,由。 的取值可知,y ( 2 ,+ 。o ) ,s u nj i e 3 9 】等用平均场方法也得出了类似结果 3 1 节点具有初始吸引度的无标度网络演化模型 在b a 模型中,新点以度择优与旧点连接,所以会导致越老的点获得的边越 多但现实中的一些网络并非如此 假设初始吸引度是一个随机变量,提出以下演化模型s 模型3 1t 假设每一个点有初始吸引度x ( x 一m ) ,z 是一个随机变量,服从概率分布密 度p ( z ) ,假设其期望e x 存在 ( 1 ) 假设初始网络中有咖个点,在每一时间间隔内,向网络中加个新点,连 接到m ( m o ) 个不同的已有节点上,产生仇条新边 ( 2 ) 在选择新节点的连接点时,假设新节点连接到旧点z 的概率n 依赖( 正比) 于旧点t 的度数q - o ,即 ( ) 2 丽k i - - x ( 3 1 1 ) 第3 章节点具有初始适应度的无标度网络演化模型 这样的步骤重复仇次,在亡时刻,该模型生成个具有亡+ 仇。个点
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 人教版新教材七年级上册英语时文组合训练(二)教学设计
- 初中综合实践活动九年级“传统节日文化探究与体验”教学设计
- 初中美术八年级下册第七单元《乡村展新貌-乡村改造规划师》教学设计
- 小学四年级语文下册说明性与叙事性语段结构辨认及概括专项训练教学设计
- 高三历史一轮复习教学设计:统编版教材与湖南考情的精准对接
- 小学语文五年级下册第七单元习作中国的世界文化遗产教学设计
- 高二信息技术《了解数据管理技术》教学设计
- 高一地理教学设计:走进敦煌风成地貌的世界
- 七年级美术《拼接流动的美景》教学设计
- 小学三年级英语Unit 4 This is my friend第一课时教学设计
- 2026年烟花爆竹经营单位主要负责人考试题库及答案
- 复盘的讲解课件
- 外协加工工艺统一规范细则
- 超声造影剂安全使用专家共识(2026版)
- 太原铁路面试题目及答案
- DB53-T 1137-2023 公路建设项目电子文件与电子档案管理系统建设指南
- 股骨颈骨折患者护理 2
- TCECS-628-2019-石材粘贴工程技术规程
- 2025年人教版中考英语复习:2022年版课标核心词汇1600词 英汉+汉英 默写练习(含答案)
- 23G409先张法预应力混凝土管桩
- 2024年甘肃省职业院校技能大赛(高职学生组)财经商贸类互联网+国际经济与贸易赛项样卷3
评论
0/150
提交评论