论文部分内容阅读
复杂网络是近十年来随着计算机技术迅猛发展而兴起的一门综合信息学、数学、物理学、生物学、管理学等众多学科的交叉学科。对复杂网络理论和应用的研究,有助于人们更好的认识网络,鉴别存在于自然和社会中各式各样的实际网络;有助于人们了解网络,揭示实际网络的内在特性和形成规律;有助于人们改进网络,使各种实际网络更好的为人类服务。
本文从实际网络出发,分别提出了一个无标度网络模型和一个加权演化网络模型;研究了实际公交网络的统计特性,揭示了其网络特征;设计了一个基于加权复杂网络的公交换乘算法;分析了公交网络的社团结构和传播行为。主要研究内容如下:
提出了一个基于派系增长和优先连接的无标度网络模型。该模型演化的每一步有一个新的派系加入到网络中,并且这个新加入的派系优先与已存在的具有较多连接的派系相连接。仿真结果显示生成网络的节点度分布为无标度幂律分布。将派系视为节点,派系间连接视为边构成一个新的网络,此网络节点的度分布也符合无标度幂律分布。基于平均场理论,给出了该模型节点度分布的解析结果。
提出了一个基于派系重叠增长的加权演化网络模型。该模型在两种不同的连接机制下(优先连接和随机连接)具有不同的网络特性。利用平均场方法,分别分析了在两种不同机制下产生的网络的节点所属派系数分布和节点强度分布。证明了在优先连接机制下,两种分布都符合幂律分布;在随机连接机制下,两种分布都符合指数分布,并且解析得到了其分布指数。数值模拟结果与解析结果很好地吻合。
研究了spaceL描述下的公交网络的平均路径长度、聚类系数、度分布等特性,认为spaceL描述下的公交网络类似于规则网络,并不具备明显的小世界特性,而其度分布符合幂律分布。随后研究了spaceP描述下的公交网络的度分布、多重边分布、不同派系之间的重叠节点数分布、每个节点所属派系数分布等规律。并将每个派系看成为一个节点,派系间的重叠看成多重边,构成一个派系网络,研究了该派系网络的平均路径长度、聚类系数和度分布等特性。认为spaceP描述下的公交网络是一个高度派系重叠、高度派系聚类、具有指数型度分布的小世界网络。最后,根据spaceP描述下的公交网络的特性,提出一个公交网络演化模型,并基于平均场方法对其进行理论分析。模型的模拟结果和解析结果很好的解释了spaceP描述下的实际公交网络中所呈现的网络特性。
用spaceP方法将公交网络建模成为一个无权复杂网络,然后利用广度优先搜索算法得到需换乘两公交站点间的所有最少次数换乘方案。在此基础上,引入了网络点权,即站点的经纬度,进而得到网络的边权,即站点间的直线距离,把公交网络进一步建模成一个加权的复杂网络模型。结合得到的最少换乘次数方案,最终得到一种在保证换乘次数最少的基础上站间总直线距离也最短的换乘方案。用杭州的实际数据验证了此算法的有效性。
利用改进的社团结构划分方法(PKM凝聚算法)分别对spaceP和spaceL描述下的实际公交网络进行社团特性分析。得到的结果说明在spaceL描述下的公交网络具有明显的社团特性,而在spaceP描述下的公交网络并不具有社团特性。究其原因是由于spaceP描述下的公交网络具有高度重叠的性质,用以上方法不能有效辨识出此类型网络的社团结构。因此,我们提出一种新的社团的定义,称之为N-深度社团,并给出了这种社团结构的划分方法。将此定义和划分方法应用到一个公交网络模型上,取得了较好的效果。
基于SIS传播模型分别在spaceP描述下的北京、上海和杭州三个实际公交网络上做了传播行为仿真,得到网络中感染节点的密度随时间的变化情况和感染节点的稳态密度随传染率的变化情况。在一个公交网络模型上做了传播行为的仿真研究。利用平均场理论,分析了此模型的传播临界值,与仿真结果一致。