1、学年论文题目基于复杂网络的兰州公交抗毁性分析学院数学与统计学院专业信息与计算科学班级2011级1班学生姓名学号201171020109指导教师1基于复杂网络的兰州公交抗毁性分析（西北师范大学数学与统计学院,兰州730070）摘要本文采用随机攻击和蓄意攻击两种方式研究兰州公交复杂网络的抗毁性。以兰州市公交换乘网为复杂网络模型，研究该模型受到这两类攻击后的最短路径长度和相对连通率以及网络直径的变化情况，并绘制相关示意图。由此分析并得出结论随机攻击和蓄意攻击均具有脆弱性。关键词复杂网络城市公交抗毁性THEANALYSISOFSURVIVABILITYOFTHECOMPLEXNETWORKINLANZ
2、HOUHECHAOCOLLEGEOFMATHEMATICSANDSTATISTICS,NORTHWESTNORMALUNIVERSITY,LANZHOU730070ABSTRACTTHISPAPERFOCUSESONTHESTUDYOFSURVIVABILITYOFTHECOMPLEXNETWORKINLANZHOUBYUSINGTHERANDOMATTACKSTRATEGYANDTHEDELIBERATEATTACKSTRATEGYTAKINGTHEBUSTRANSFERINLANZHOUASTHECOMPLEXNETWORKMODEL,THISMODELUSESTHEAVERAGESHOR
3、TESTPATHLENGTHRELATIVECONNECTEDRATEANDCYBERDIAMETERTOMEASURESURVIVABILITYOFTHENETWORKAFTERITISATTACKEDBYTHEABOVETWOTYPESOFATTACKSANDDRAWSTHERELEVANTSCHEMATICDIAGRAMWECANDRAWTHECONCLUSIONFROMABOVEANALYSISTHEBUSNETWORKINLANZHOUHASTHEFRAGILECHARACTERISTICSKEYWORDSTHECOMPLEXNETWORKCITYPUBLICTRANSPORTSUR
4、VIVABILITY1引言公共交通是城市发展的必然产物，也是如今城市赖以生存的重要基础设施，具有不可替代的重要作用。公共交通网络是由公交线路和停靠站点组成的巨型复杂网络，其结构复杂，难于管理。利用复杂网络有关知识对其进行复杂网络特征及抗毁性分析研究，为揭示公交网络的复杂性及演化机理，改善交通有一定意义上的启发。城市公交网络构成了城市的骨架，是城市社会经济学的载体和城市交通赖以正常运行的物质基础。城市公交会受到人类的恶意攻击以及交通堵塞等的影响，这些可能会导致公交线路的局部失效，从而增加公交路线其它部分的客流负担，使路网超载并损害其交通功能，失效甚至会扩散至整个网络，导致更多的破坏，造成路网能力
5、和效率的明显降低。因此要缓解突发事件造成的不利影响，必须深刻认识公交拓扑性质的变化规律，深化城市公交的抗毁性研究，在此基础上对公交进行控制与管理。本文构建了兰州公交复杂网络拓扑图，引用复杂网络节点度、平均最短路径相关特征指标评价兰州公交结构特征。22复杂网络的拓扑参数21节点的度节点的度是复杂网络众多属性中最简单但也是最重要的属性，一个节点错误未找到引用源。的度定义为与它相连的节点数目，用错误未找到引用源。表示，例如图21中节点1的度为错误未找到引用源。一个节点的度越大表明这个节点在整个网络中作用越重要，这样的节点我们通常称为关键节点或HUB节点。22平均路径长度网络中任意一对节点错误未找到引
6、用源。之间的距离为这对节点相连的最短路径的边数，记为错误未找到引用源。网络的直径错误未找到引用源。为任意一对节点间的距离最大值，定义为错误未找到引用源。（式21）网络中的平均路径长度错误未找到引用源。为任意两个不同节点之间的距离平均值，这个参数着重于度量网络的拓扑结构，用来衡量网络节点之间的离散程度，计算公式如下错误未找到引用源。（式22）其中错误未找到引用源。为节点总个数。例如图21中，节点2和节点3的距离记为错误未找到引用源。,网络直径错误未找到引用源。，平均路径长度错误未找到引用源。23平均度与度分布一个节点错误未找到引用源。的度错误未找到引用源。定义为与它相连的节点数目，从直观上来看节
7、点的度值越大说明这个节点在网络中越重要。网络中的平均度是所有节点错误未找到引用源。的度错误未找到引用源。的平均值，记为错误未找到引用源。网络中节点的度分布用分布函数错误未找到引用源。表示，可理解为任意选择一个节点的度恰好有错误未找到引用源。的概率，也等于网络中度数为错误未找到引用源。的节点的个数占网络节点总个数的比值，即错误未找到引用源。式23其中，错误未找到引用源。表示度为错误未找到引用源。的节点个数，例图21中，网络的平均度错误未找到引用源。，节点2和节点4的度都为2，则有错误未找到引用源。24集聚系错误未找到引用源。集聚系数用来描述网络中节点的聚集情况,即整个网络中各节点的紧密程度，又称
8、之为聚类系数，它着重于度量网络的局部连通程度。网络中的任意节点3错误未找到引用源。有错误未找到引用源。条边将它和其它节点连接，错误未找到引用源。个节点就是节点错误未找到引用源。的邻居节点，易知这错误未找到引用源。个节点之间最多可能有错误未找到引用源。条边。而这错误未找到引用源。个节点之间实际存在的连接边数错误未找到引用源。与错误未找到引用源。全部连接的边数错误未找到引用源。的比值就是节点错误未找到引用源。的集聚系数,记为错误未找到引用源。，错误未找到引用源。错误未找到引用源。（式24）网络中所有节点集聚系数的平均值就是网络的集聚系数，错误未找到引用源。错误未找到引用源。（式25）例图21中，错
9、误未找到引用源。可知错误未找到引用源。的取值范围在0到1之间；错误未找到引用源。时，表示网络变为许多孤立的节点，当错误未找到引用源。时，表示网络中任意对节点都有边连接。错误未找到引用源。值越大表明网络中各节点间越紧密。25最大连通子图我们把图的所有节点用最少的边将其连接起来的子图称为最大连通子图，最大连图子图的相对大小错误未找到引用源。定义为最大连通子图中节点数目错误未找到引用源。与网络中所有节点数目错误未找到引用源。的比值，即错误未找到引用源。（式26）在初始状态下，最大连通子图的相当大小错误未找到引用源。，表示初始网络中所有节点都有边连接的无向图。这个参数着重于度量网络的总体大小，而不是刻
10、画网络的拓扑结构。25复杂网络抗毁性的定义在现实复杂网络中，不同类型的网络其抗毁性的定义也不相同，一般同网络的可靠性、生存性和有效性等指标混用。图论中网络抗毁性的定义是网络在遭到人为4破坏情况下的可靠性，它从网络整体连通性的角度来刻画拓扑结构对网络可靠性的影响。文错误未找到引用源。中对抗毁性的定义是在网络中的节点或边遭受蓄意破坏或发生随机失效的情况下网络维持其功能的能力。该定义表示，要进行网络抗毁性的研究，应该完成三个方面的工作确定网络抗毁性分析的测度；网络失效模式的选择；网络维护策略。3兰州市公交复杂网络抗毁性分析31公交复杂网络构造城市公交网络由公交线路和公交站点组成，而公交线路由多个公交
11、站点连接而成。本人在爱帮网上统计了兰州主城公交数据（截止时间2014年5月25日），总共线路有90条，公交站点576个，建立了公交线路和站点的数据库，以此为基础来建立兰州市公交换乘复杂网络。评价一个城市公交网络的可达性的一个重要指标是换乘次数，换乘次数越少，可达效率越高，市民出行越方便。在公交换乘网络中，公交站点为节点，如果两个节点之间有共同的公交线路通过，那么这两个节点有边连接。本文采用公交换乘网络来构造兰州市区公交复杂网络,从爱帮网上逐个站点经纬度复制到EXCEL表中，整理好将EXCEL表导入到MATLAB中，用MATLAB语句编程，将编程获得的数据保存到M文件和MAT文件中，对其编程在M
12、ATLAB软件平台运行，即可获得兰州市区公交复杂网络的拓朴参数，如度分布、平均路径长度、集聚系数等，并对其分析总结。如图31所示度分布如图所示兰州公交度数分布图节点度1234567891011121415171937节点数2279880614225187312421221532兰州市公交复杂网络的抗毁性分析根据公交网失效站点是否具有选择性，将公交网络失效形式分为蓄意攻击失效和随机攻击失效两种，如下表类型地点事例蓄意攻击有目的性重要交通节点堵塞、恐怖袭击、群众聚集随机攻击无目的性重大山滑坡、突发性交通事故研究一个复杂网络的抗毁性，就要找到符合该网络抗毁性的度量参数，城市公交网络的抗毁性是从整个网
13、络的拓扑结构来描述的，一般采取的抗毁性的度量参数有平均最短路径长度错误未找到引用源。、平均集聚系数错误未找到引用源。、网络直径错误未找到引用源。等。结合本实例具体情况，选用平均路径长度错误未找到引用源。、最大连通成分相对大小错误未找到引用源。和网络直径错误未找到引用源。作为兰州市公交网络的抗毁性测度，并对随机攻击和蓄意攻击两种策略进行仿真，认真分析仿真结果，得出结论。随机攻击实验中每次随机删除1的节点，每删除一次求平均路径长度。蓄意攻击实验中按照节点度值由大到小的顺序每次删除网络中1的节点，同时每次求平均最短路径长度、相对连通率和网络直径。可分别得如下图64结论通过以上的分析和研究，可以得出如下结论1兰州市公交站点网络对蓄意攻击和随机攻击均具有脆弱性。相比较而言，蓄意攻击对公交网络的影响更大，其影响程度约为随机攻击的2倍。2该研究成果有助于提高公交网络能力和运营效率，为针对性预防体系的建立、公交调度组织和应急救援方案的有效制定提供参考，具有重要的应用价值和现实指导意义。参考文献【1】高小净常州公交复杂网络研究南京交通大学硕士学位论文南京交通大学，2013,89【2】汪小帆,李翔,陈关荣,复杂网络理论及其应用M,清华大学出版社,2006,929【3】谭跃进，吕欣，吴俊，邓宏钟复杂网络抗毁性研究若干问题的思考J系统工程与理论实验，2008,SO116120指导教师职称成绩7评语
