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

• Autorzy: Zhang L. , He F-g , Zhang Y-p , Zhao S.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

path finding; weighted network; granularity; quotient space; computational complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 93, nr 4
• Strony: 459--469
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Zhang L.

autor

He F-g

autor

Zhang Y-p

autor

Zhao S.

• Key Lab of Intelligent Computing & Signal Processing at Anhui University, Ministry of Education, Anhui University, Hefei, Peoples Republic of China, 230039,

Bibliografia

• [1] Larson, R. and Odoni, A.: Shortest Paths between All Pairs of Nodes, in Urban Operations Research, 1981.
• [2] Pemmaraju, S. and Skiena, S.: All-Pairs Shortest Paths, in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 330-331.
• [3] Floyd, R. W.: Algorithm 97.. Comm. ACM 5-6, 345, 1962.
• [4] Preiss, B.: Floyd's Algorithm, in Data Structures and Algorithms with Object-Oriented Design Patterns in Java. 1998.
• [5] Dijkstra, E. W.: A note on two problems in connection With graphs, In Numerische Mathematik, 1(1959), pp. 269-271.
• [6] Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein C: Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, 2001.
• [7] Bellman, R.: On a routing problem, Quarterly of Applied Mathematics, 1958,Volume 16, Number 1, pp. 87-90.
• [8] Zhang, L. and Zhang, B.: Theory and Applications of Problem Solving-Theory and Applications of Quotient Space based Granular Computing (second version) Tsinghua University Press, 2007 (in Chinese).
• [9] Zhang, B. and Zhang, L.: Theory and Applications of Problem Solving, Elsevier Science Publications B. V., North-Holland-Amsterdam. London. New York. Tokyo, 1992.
• [10] Zhang, L. and Zhang, B.: The quotient space theory of problem solving, Fundamenta Informatcae, 2004,59,pp.287-298.
• [11] Erdos, P., and Renyi, A.: On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci., 1960,5, pp. 17-60.
• [12] Watts, D. J., and Strogatz, S. H.: Collective dynamics of 'small-world' networks. Nature, 1998,393(6684), pp.440-442.
• [13] Newman, M. E. J., and Watts, D. J.: Renormalization group analysis of the small-world network model, Phys. Lett. A, 1999,263, pp.341-346.
• [14] Barabasi, A. L., and Albert, R.: Emergence of scaling in random networks. Science, 1999,286(5439), pp.509-512