无标度网络模型构造
课题:无标度网络模型构造
姓名 赵训
学号 班级 实验班1001
内容需要下载文档才能查看 内容需要下载文档才能查看
一、 源起
无标度网络(或称无尺度网络)的概念是随着对复杂网络的研究而出现的。“网络”其实就是数学中图论研究的图,由一群顶点以及它们之间所连的边构成。在网络理论中则换一套说法,用“节点”代替“顶点”,用“连结”代替“边”。复杂网络的概念,是用来描述由大量节点以及这些节点之间错综复杂的联系所构成的网络。这样的网络会出现在简单网络中没有的特殊拓扑特性。
自二十世纪60年代开始,对复杂网络的研究主要集中在随机网络上。随机网络,又称随机图,是指通过随机过程制造出的复杂网络。最典型的随机网络是保罗·埃尔德什和阿尔弗雷德·雷尼提出的ER模型。ER模型是基于一种“自然”的构造方法:假设有个节点,并假设每对节点之间相连的可能性都是常数。这样构造出的网络就是ER模型网络。科学家们最初使用这种模型来解释现实生活中的网络。
ER模型随机网络有一个重要特性,就是虽然节点之间的连接是随机形成的,但最后产生的网络的度分布是高度平等的。度分布是指节点的度的分布情况。在网络中,每个节点都与另外某些节点相连,这种连接的数目叫做这个节点的度。在网络中随机抽取一个节点,它的度是多少呢?这个概率分布就称为节点的度分布。
在一般的随机网络(如ER模型)中,大部分的节点的度都集中在某个特殊值附近,成钟形的泊松分布规律(见下图)。偏离这个特定值的概率呈指数性下降,远大于或远小于这个值的可能都是微乎其微的,就如一座城市中成年居民的身高大致的分布一样。然而在1998年,Albert-László Barabási、Réka Albert等人合作进行一项描绘万维网的研究时,发现通过超链接与网页、文件所构成的万维网网络并不是如一般的随机网络一样,有着均匀的度分布。他们发现,万维网是由少数高连接性的页面串联起来的。绝大多数(超过80%)的网页只有不超过4个超链接,但极少数页面(不到总页面数的万分之一)却拥有极多的链接,超过1000个,有一份文件甚至与超过200万个其他页面相连。与居民身高的例子作类比的话,就是说大多数的节点都是“矮个子”,而却又有极少数的身高百丈的“巨人”。Barabási等人将其称为“无标度”网络。
随机网络的度(a)集中在某个平均值
律分布 附近,而无标度网络的度分布(b)则遵守幂
二、 描述与定义
无标度网络的特性,在于其度分布没有一个特定的平均值指标,即大多数节点的度在此附近。在研究这个网络的度分布时,Barabási等人发现其遵守幂律分布(也称为帕累托分布),也就是说,随机抽取一个节点,它的度 是自然数的概率:
也就是说的概率正比于的某个幂次(一般是负的,记为)。因此越大, 的概率就越低。然而这个概率随增大而下降的“速度”是比较缓慢的:在一般的随机网络中,下降的速度是指数性的,而在无尺度网络中只是以多项式类的速度下降。
在现实中许多大规模的无尺度网络中,度分布的值介于2与3之间。在对数坐标系中,度分布将会是一条斜率介于-2至-3之间的直线。如下图中,横坐标为节点的度,从一直到;纵坐标为找到这样的节点的概率从一直到。最高度数的节点有882条连接。所有的蓝点大致成一条直线分布(绿色的直线)。
内容需要下载文档才能查看 内容需要下载文档才能查看
200,000个节点的无标度网络的度分布(对数坐标)
仅仅是将度分布的幂律分布作为无标度网络的定义有其不够完善之处。由于幂律分布是方差可能无穷的高可变分布,对于度分布是同一个幂律分布的不同网络,其拓扑结构和特性可能存在巨大的差异。2005年,Lun Li和大卫·阿尔德森(David Alderson)等人在论文《迈向无标度图的理论》(Towards a Theory of Scale Free Graphs)中提出了一种补充性的标度性测度。设
布的)度分布为所有具有(依照幂律分的网络的集合,对于其中每一个网络
,定义度-度相关数:
其中表示 中所有连接的集合。根据排序原理,如果度数大的点之间相互连
会比较大。设为最大的,那么定义度-度相关系数:
内容需要下载文档才能查看 内容需要下载文档才能查看接的话,那么
度-度相关系数介于0与1之间。越靠近1,则称此网络 “无尺度”的,
靠近0,则称是“富尺度”的。在此定义下,无尺度网络中的节点度数分布特征体现了自相似的性质,而凸显了“无尺度”的特征,与富尺度网络之间有相当的差异。
三、 例子
不少现实中的网络结构都属于无标度网络,或者有无标度的特性。以下是一些无标度网络的例子:
内容需要下载文档才能查看 内容需要下载文档才能查看
四、 BA模型及其构造算法
Albert-László Barabási与Réka Albert在1999年的论文中提出了一个模型来解释复杂网络的无标度特性,称为BA模型。这个模型基于两个假设:
增长模式:不少现实网络是不断扩大不断增长而来的,例如互联网中新网页的诞生,人际网络中新朋友的加入,新的论文的发表,航空网络中新机场的建造等等。
优先连接模式:新的节点在加入时会倾向于与有更多连接的节点相连,例如新网页一般会有到知名的网络站点的连接,新加入社群的人会想与社群中的知名人士结识,新的论文倾向于引用已被广泛引用的著名文献,新机场会优先考虑建立与大机场之间的航线等等。
在这种假设下,BA模型的具体构造为:
1.增长:从一个较小的网络开始(这个网络有个节点,条边),逐步加入新的节点,每次加入一个。
2.连接:假设原来的网络已经有个节点(
个节点时,从这个新节点向原有的个节点连出)。在某次新加入一个连结。
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
- 2018宁夏公务员面试结构化面试模拟题5.9
- 2018宁夏公务员面试结构化面试模拟题答案5.30
- 2018宁夏公务员面试结构化面试模拟题答案5.22
- 2018宁夏公务员面试热点模拟题:高校图书馆对外开放谁将受益
- 2018宁夏公务员面试结构化面试模拟题答案5.10
- 2018宁夏公务员面试结构化面试模拟题5.16
- 2018宁夏公务员面试结构化面试模拟题答案5.8
- 2018宁夏公务员面试热点模拟题:反腐倡廉热度从未减
- 2018宁夏公务员面试结构化面试模拟题答案5.14
- 2018宁夏公务员面试结构化面试模拟题5.30
- 2018宁夏公务员面试结构化面试模拟题答案5.7
- 2018宁夏公务员面试结构化面试模拟题答案5.16
- 2018宁夏公务员面试结构化面试模拟题4.27
- 宁夏公务员结构化面试模拟题4.25
- 2018宁夏公务员面试结构化面试模拟题5.31
- 2018宁夏公务员面试结构化面试模拟题答案5.15
- 2018宁夏公务员面试热点模拟题:禁止燃放烟花爆竹体现社会进步
- 2018宁夏公务员面试结构化面试模拟题答案5.2
- 2018宁夏公务员面试结构化面试模拟题5.17
- 2018宁夏公务员面试热点模拟题:农村成为高价彩礼“重灾区”
- 2018宁夏公务员面试结构化面试模拟题5.4
- 2018宁夏公务员面试结构化面试模拟题答案5.18
- 2018宁夏公务员面试结构化面试模拟题5.8
- 2018宁夏公务员面试结构化面试模拟题答案5.11
- 宁夏公务员面试热点模拟题:如此脆弱的医患关系
- 宁夏公务员结构化面试模拟题答案4.25
- 2018宁夏公务员面试热点模拟题:小学生超过十点不做作业
- 2018宁夏公务员面试备考注意事项
- 2018宁夏公务员面试结构化面试模拟题答案5.23
- 2018宁夏公务员面试热点模拟题:如何开展敬老爱老活动
网友关注视频
- 外研版英语七年级下册module3 unit1第二课时
- 苏科版数学八年级下册9.2《中心对称和中心对称图形》
- 冀教版英语五年级下册第二课课程解读
- 外研版英语七年级下册module1unit3名词性物主代词讲解
- 沪教版八年级下册数学练习册21.3(3)分式方程P17
- 【部编】人教版语文七年级下册《过松源晨炊漆公店(其五)》优质课教学视频+PPT课件+教案,江苏省
- 二年级下册数学第二课
- 【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,辽宁省
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 河南省名校课堂七年级下册英语第一课(2020年2月10日)
- 青岛版教材五年级下册第四单元(走进军营——方向与位置)用数对确定位置(一等奖)
- 《小学数学二年级下册》第二单元测试题讲解
- 外研版英语三起6年级下册(14版)Module3 Unit1
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 第19课 我喜欢的鸟_第一课时(二等奖)(人美杨永善版二年级下册)_T644386
- 冀教版英语四年级下册第二课
- 北师大版数学四年级下册第三单元第四节街心广场
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
- 小学英语单词
- 冀教版小学英语五年级下册lesson2教学视频(2)
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4
- 第五单元 民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830
- 外研版英语七年级下册module3 unit2第一课时
- 沪教版八年级下册数学练习册21.3(2)分式方程P15
- 外研版八年级英语下学期 Module3
- 苏科版数学 八年级下册 第八章第二节 可能性的大小
- 二年级下册数学第三课 搭一搭⚖⚖
- 【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,广东省
- 沪教版八年级下册数学练习册20.4(2)一次函数的应用2P8
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理