A New Algorithm for Optimal Path Finding in Complex Networks Based on the Quotient Space

被引:26
作者
Zhang, Ling [1 ]
He, Fu-gui [1 ]
Zhang, Yan-ping [1 ]
Zhao, Shu [1 ]
机构
[1] Anhui Univ, Key Lab Intelligent Comp & Signal Proc, Minist Educ, Hefei 230039, Peoples R China
基金
中国博士后科学基金; 中国国家自然科学基金;
关键词
The path finding; weighted network; granularity; quotient space; computational complexity;
D O I
10.3233/FI-2009-113
中图分类号
TP31 [计算机软件];
学科分类号
081205 [计算机软件];
摘要
The optimal path finding problem in weighted edge networks is an old and interesting one in many fields. There were many well-known algorithms to deal with that issue. But they were confronted with the high computational complexity while the network becoming larger. We present a hierarchical quotient space model based algorithm that reduces the computational complexity. The basic idea is the following. The nodes of a given network are partitioned with respect to the weights of their adjacent edges. We construct a variety of coarser versions of the given network with new nodes corresponding to the blocks of partitions at various levels of granularity. They are called the quotient spaces (networks) of the original network. The construction of the (sub) optimal path is then done incrementally, throughout the hierarchy of quotient networks. Since each version of the network is much simpler than the original one, especially of the coarsest spaces, the computational complexity is reduced. In this paper, we present the basic principles of the algorithm and its experimental comparison to other well-known algorithms.
引用
收藏
页码:459 / 469
页数:11
相关论文
共 14 条
[1]
Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[2]
Bellman R.E., 1958, Q APPL MATH, V16, P87
[3]
Cormen T.H., 2001, Introduction To Algorithms, Vsecond
[4]
Dijkstra E. W., 1959, Numerische Mathematik, DOI [10.1007/BF01386390, DOI 10.1007/BF01386390]
[5]
ERDOS P, 1960, B INT STATIST INST, V38, P343
[6]
FLOYD RW, 1962, COMM ACM, V5
[7]
Larson R. C., 1981, Urban operations research
[8]
Renormalization group analysis of the small-world network model [J].
Newman, MEJ ;
Watts, DJ .
PHYSICS LETTERS A, 1999, 263 (4-6) :341-346
[9]
PEMMARAJU S, COMPUTATIONAL DISCRE, P330
[10]
Preiss B R., 1998, Data Structures and Algorithms with Object-Oriented Design Patterns in Java