| 一种新的大规模网络最短路径的近似算法 |
| |
| 引用本文： | 苏磊,张宁,马良.一种新的大规模网络最短路径的近似算法[J].复杂系统与复杂性科学,2008,5(2):51-54. |
| |
| 作者姓名： | 苏磊 张宁 马良 |
| |
| 作者单位： | 上海理工大学管理学院,上海,200093 |
| |
| 基金项目： | 国家自然科学基金
,
上海市重点学科建设项目
,
上海市自然科学基金 |
| |
| 摘 要： | 平均最短路径长度是复杂网络的一个重要特性,但是对于大规模网络的平均最短路径长度的计算是困难的.在最近的一次对中国教育网的研究中.建立了一个有2 354 934个网页和26 816 209个链接的网络.要想计算该网络的平均最短路径长度,无论是传统的Floyd、Dijkstra算法,还是基于MPI的并行算法,在现有的计算机资源下都难以实现.提出了二级网络的概念,并基于此给出了一种针对中国教育网的新算法,使得在可以接受的时间内完成平均最短路径的近似计算,经试算效果令人满意,说明这种方法对于计算大规模网络的平均最短路径是有效的.
|
| 关 键 词： | 复杂网络 中国教育网 最短路径 Dijkstra算法 大规模 复杂网络 平均最短路径长度 近似算法 Networks Large 方法 效果 试算 近似计算 时间 资源 计算机 并行算法 Dijkstra Floyd 网页 研究 教育网 中国 |
A New Approximation Algorithm for Finding Shortest-path in Large Networks |
| |
| Authors: | SU Lei ZHANG Ning MA Liang |
| |
| Institution: | Business School;Shanghai University for Science and Technology;Shanghai;200093;China |
| |
| Abstract: | The average shortest path length is one of characteristics of complex networks. However,it is hard to calculate the average shortest path length of vary large networks. In the recent research of China Education and Research Network,we construct a network that contains 2 354 934 pages and 26 816 209 links. It is hard to calculate its average shortest path length either using the classic Floyd or Dijkstra algorithm or the message passing interface (MPI) according to the available computer resources. In this p... |
| |
| Keywords: | complex network CERNET shortest-path Dijkstra algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
