基于迭代变邻域下降算法求解TTRP问题

为了求解卡车带挂车的车辆路径问题(truck and trailer routing problem, TTRP),提出迭代变邻域下降算法(iterated variable neighborhood descent, IVND).该算法首先使用T-cluster算法求得一个初始可行解.然后,设计了基于多邻域算子的变邻域下降搜索算法.在搜索过程中,借鉴"粒邻域"的思想定义了"受限邻域",同时设计了基于switch-vehicle-type算子的扰动策略.最后,选取国际上通用的Chao测试数据集(21个50～199个顾客规模的标准测试算例)对算法性能进行测试.通过与文献中其它4种算法比较,实验结果表明,提出的IVND算法可以在最短的计算时间内收敛到满意解,并且IVND算法结构简单、计算效率高、易实现,可以被灵活地扩展解决其它车辆路径问题和组合优化问题.     

基于节点标号的Koch网络结构性质研究

针对正多边形Koch分形岛所映射成的Koch网络,根据节点接入网络的时间和位置信息给节点标号。在节点标号的基础上,研究网络的最短路由及计算最短路径长度;并分析网络的主要结构性质,如节点的度、度分布和累积度分布函数,以及网络的聚类系数、平均最短路径长度、度关联函数和介数中心性,得出结构性质的解析解。结果表明,所构建的Koch网络是无标度和小世界的;其聚类系数趋向于比较大的常数值;平均路径长度与网络节点数的对数呈正比关系,度相关函数、点介数和边介数都随节点度的变化而指数变化。     

开源软件系统中社会-技术网络的协同演化分析

收集了开源软件项目Vuze 10个连续版本的源代码与开发者交互历史数据,构建对应的软件网络与开发者网络,依次从网络规模、平均度、最短路径和聚类系数,以及社区结构4个方面对比了两类网络的协同演化。结果表明:软件网络以3-4个版本周期性增长,而开发者网络呈明显的线性增长;整体上平均度均满足近似线性增长;"小世界"特性越来越明显,最短路径周期性下降,但开发者间局部合作更明显;模块度呈下降趋势,但开发者网络中波动更大。     

东亚集装箱港口体系层次结构

在确定33个东亚集装箱港口的基础上,根据全球运力份额前20名班轮公司的现有航线分布情况,构建了一个港口的有向二分网络。运用复杂网络中的k-核分析对该港口网络进行层次划分,分析各个层次内部和层次之间港口的连接关系并考察了低层次港口的k-核深度。此外还分析了核心结构的小世界特性,并分别从聚集系数、平均最短路径长度以及接近中心势三个方面,针对最高层次中的每个港口对网络整体结构的影响进行了进一步研究。     

汉语句法网络的复杂性研究

旨在研究汉语句法网络的复杂性和复杂网络指标作为一种语言学研究手段的可行性,给出了如何按照依存句法树库构建句法网络的方法,自建了两种不同语体的汉语句法网络,对平均路径长度、聚集系数和度分布等复杂网络指标进行了测度.结果表明,两个句法网络和随机网络的平均路径长度和直径大致相当,但句法网络的聚集系数要远远大于随机网络,句法网络的度分布符合幂律,因此两种句法网络均为小世界和无尺度网络.发现两种语体的句法网络直径相同,但在平均度、平均路径长度、聚集系数和幂律指数方面则有较明显的差别.     

一种新的大规模网络最短路径的近似算法

平均最短路径长度是复杂网络的一个重要特性,但是对于大规模网络的平均最短路径长度的计算是困难的.在最近的一次对中国教育网的研究中.建立了一个有2 354 934个网页和26 816 209个链接的网络.要想计算该网络的平均最短路径长度,无论是传统的Floyd、Dijkstra算法,还是基于MPI的并行算法,在现有的计算机资源下都难以实现.提出了二级网络的概念,并基于此给出了一种针对中国教育网的新算法,使得在可以接受的时间内完成平均最短路径的近似计算,经试算效果令人满意,说明这种方法对于计算大规模网络的平均最短路径是有效的.     

探索小世界特性产生的一种新方法

在研究WS模型基础上，探讨了产生小世界特性的一种新方法，即提出了度不变的边遍历小世界模型。主要算法是在重新连接过程中保持每个节点的度不变，首先将所有满足度不变条件的规则边断开，然后随机地连接相同数目的长距离边。谊模型的数值模拟结果与WS模型的结果比较表明，新模型具有很好的小世界特性，即平均最短路径小和平均集群系数大的两大特点。同时研究了新模型下参数变化对网络特性的影响。     

基于个体选择的小世界网络结构演化

将复杂网络理论和基于博弈论的经济网络理论相结合，探讨小世界网络的结构演化问题。从个体选择的角度，以网络中个体价值优化作为网络结构演化的动力机制，用顶点度分布(P(K))、平均最短路径长度(l)、集群系数(C)作为网络结构演化判据，研究小世界网络的结构演化问题。     

基于节点复合特性的端-边协同网络生成算法

针对智慧交通系统数据处理量大、对传输时间要求严苛的难题，通过将协同系统定义为复杂网络模型，构建了设备端和边缘节点协作运行的端-边协同系统。提出了基于网络节点复合特性的协作网络生成算法，实现了多层复杂网络的构建。相比随机几何法，提出的由节点聚类系数和介数中心性两种特性参数相结合的协作网络生成算法能够更全面地描述节点特性，反映节点重要性，改善现有多层复杂网络模型对节点信息描述不全的问题。最后，使用4种复杂网络模型构建多层网络模型并验证该算法，以节点间最短路径值作为评价指标，证明提出的由节点复合特性生成协作网络的算法能够明显降低整个网络中节点间最短路径值，减少传输时间，提高传输效率。     

介数中心性和平均最短路径长度整合近似算法

基于Brandes算法给出了复杂网络中介数中心性和平均最短路径长度的整合近似算法,通过理论分析和Rocketfuel项目实测数据的实验分析,验证了该整合算法能够快速有效地估计出复杂网络的介数中心性和平均最短路径长度,为进一步的研究工作奠定了基础.     

具有随机性的确定性网络模型

为了进一步研究复杂网络的统计特性,简单介绍了复杂网络的几个统计指标,给出了一种通过边的迭代方式生成一种确定性网络模型的方法.在此模型构造算法的基础上对网络的个别特性进行了推导,并通过计算机编程构造了模拟网络,对比了不同规模模拟网络的部分统计特性.由推导结果和模拟数据可知,迭代生成的网络具有较小的平均路径长度和较大的群聚系数,度分布服从指数分布.因此可判断出生成的确定性网络既具有小世界特性,又具有完全随机网络的特性.     

谢尔宾斯基地毯的复杂网络特征研究

引入了谢尔宾斯基地毯的网络拓扑性质,并在此基础上采用内连结点法,构造具有分形和小世界特性的网络,利用数学归纳的方法得到了该网络图的集聚系数、网络图的直径、平均路径长度及平均度分布等,证明了该网络的小世界特性;由网络的自相似性及其具有的精细结构得到该网络的分形特性,由此证明了其分形和小世界特性.     

节点数固定的复杂网络模型初探

由于随机图模型、小世界模型和无标度模型的结构上存在交叉性，有必要对复杂网络进行新的分类。本文将复杂网络分成两类：节点数固定的复杂网络和节点数变化的复杂网络，且重点研究了前一类网络。首先时节点数固定的网络进行了细分，然后分析了在边的不同连接方式下节点数固定的网络的度分布、平均最短路长度和聚类系数等特征，最后讨论了小世界特性与无标度特性产生的原因。研究表明，节点数固定的网络大多具有小世界特性，小世界特性与无标度特性是从不同的侧面来研究复杂网络的，从而很好地解释了在许多复杂网络这两种特性能够共存的原因。     

A New Peer-to-Peer Topology for Video Streaming Based on Complex Network Theory

A new wave of networks labeled Peer-to-Peer(P2P) networks attracts more researchers and rapidly becomes one of the most popular applications.In order to matching P2 P logical overlay network with physical topology,the position-based topology has been proposed.The proposed topology not only focuses on non-functional characteristics such as scalability,reliability,fault-tolerance,selforganization,decentralization and fairness,but also functional characteristics are addressed as well.The experimental results show that the hybrid complex topology achieves better characteristics than other complex networks’ models like small-world and scale-free models;since most of the real-life networks are both scale-free and small-world networks,it may perform well in mimicking the reality.Meanwhile,it reveals that the authors improve average distance,diameter and clustering coefficient versus Chord and CAN topologies.Finally,the authors show that the proposed topology is the most robust model,against failures and attacks for nodes and edges,versus small-world and scale-free networks.     

无尺度网络平均路径长度的估计

无尺度网络的拓扑结构研究主要集中于聚类系数和平均路径长度的计算以及度分布分析. 在实际的无尺度网络中,表征网络拓扑结构的三个参数之间是互相联系的,其中一个参数均可近似用另外两个参数表示. 鉴于此,针对大规模无尺度网络的平均路径长度计算问题,基于树形结构模型给出了无尺度网络平均路径长度<l>_SF 的计算公式,并分析了网络规模和节点间连接方式对平均路径长度的影响. 分析结果表明,<l>_SF与无尺度网络的平均度数k、平均聚类系数C以及幂指数γ有关,从而将直接求解平均路径长度的复杂问题转化为间接求解,大大提高了分析无尺度网络拓扑结构的效率. 实验结果表明,提出的无尺度网络平均路径长度计算公式是有效的.     

上海公共交通网络复杂性分析

城市公共交通系统可以抽象为由公交线路和停靠站点构成的网络,这个网络的几何性质对公共交通的状况具有重要影响。在本论文中,以上海市的公共汽车交通系统中的停靠站点网络为研究对象,对其进行复杂性分析,计算了网络的度分布、平均路径长度、聚集系数等指标,并测试了网络在随机失效和有选择性攻击情况下的抗毁性。结果表明,上海市公共交通网络的度分布符合幂率分布,具有较小的平均路径长度和较高的聚集系数。在抗毁性方面,公共交通网络对结点的随机失效具有很强的抗击能力,而对有选择性攻击的抗击能力很弱。因此,可以看出上海市公共交通网络是一个无尺度复杂网络。     

卷积神经网络复杂性质与准确率的关系研究

卷积神经网络的结构也会对其性能造成影响,设计卷积神经网络更多的是依靠经验和强大的算力,如何设计出性能更好的卷积神经网络目前缺少有效的理论支撑.为了解决这一问题,在分析典型卷积神经网络拓扑复杂性的基础上,为快速实现满足给定复杂性特征的卷积神经网络,给出了由复杂网络拓扑到卷积神经网络的生成算法,通过建立系列不同拓扑特征的卷...     

Complex Network Analysis of the Robustness of the Hanoi,Vietnam Bus Network

Many complex networks exist to facilitate the transport of material or information. In this capacity, the authors are often concerned with the continued flow of material or information when a fraction of the links in the complex network is disrupted. In other words, the authors are interested in the robustness of the complex network. In this paper, the authors survey measures of robustness like the average path length, the average clustering coefficient, the global efficiency, the size of largest cluster and use these to analyze the robustness of the bus network in Hanoi, Vietnam. The authors find that the bus network is robust against random failure but sensitive to targeted attack, in agreement with its scale-free character. By examining sharp drops in the average path length within the largest cluster of the Hanoi bus network under successive targeted attack, the authors identify five nodes whose loss lead to the fragmentation of the network into five or six disconnected clusters. These isolated clusters represent geographically the Central, Western, Southern, and Northwestern districts of Hanoi. Special considerations must therefore be given to these five nodes when planners wish to expand the bus network, or make it more robust.