Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Computing the Point-to-Point Shortest Path: Quotient Space Theory’s Application in Complex Network

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNAI,volume 6401))

Included in the following conference series:

  • 1002Accesses

Abstract

The quotient space theory can represent the world at different granularity sizes and deal with complicated problems hierarchically. We present significant improvement to point-to-point shortest path based on quotient space theory in complex large-scale network. We propose the shortest path algorithm that is a heuristic method, in which evaluation function is based on community and hierarchical granularity decomposition of quotient space theory. In preprocessing, we decompose large-scale network into some communities using hierarchical granularity decomposition of quotient space theory, compute and store the minimum spanning trees in the communities and the shortest distance among communities. The implementation works on the large-scale road network. From experimental results, we know the proposed algorithm is effective and efficient in the road network of US.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Lin, T.Y.: Granular Computing: Fuzzy Logic and Rough Sets. In: Zadeh, L.A., Kacprzyk, J. (eds.) Computing with words in information- intelligent systems, pp. 183–200. Physica-Verlag, Heidelberg (1999)

    Google Scholar 

  2. Zadeh, L.A.: Towards a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic. Fuzzy Sets and Systems 19, 111–127 (1997)

    Article MathSciNet  Google Scholar 

  3. Bargiela, A., Pedrycz, W.: Human centric information processing through granular modelling. Springer, Berlin (2009)

    Book  Google Scholar 

  4. Yao, Y.Y.: Triarchic theory of granular computing. In: Zhang, Y.P., et al. (eds.), pp. 115–143. Science press, Beijing (2010) (in Chinese)

    Google Scholar 

  5. Pawlak, Z.: Rough Sets Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht (1991)

    MATH  Google Scholar 

  6. Zhang, L., Zhang, B.: Theory and Applications of Problem Solving– the Quotient Space granular computation theory and Applications (the second version). Tsinghua University Press, Beijing (2007) (in Chinese)

    Google Scholar 

  7. Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. on Sys. Sci. and Cyber. 4(2), 100–107 (1968)

    Article  Google Scholar 

  8. Goldberg, A.V., Harrelson, C.: Computing the shortest path: A* search meets graph theory. In: 16th ACM-SIAM symposium on discrete algorithms, pp. 156–165 (2005)

    Google Scholar 

  9. Goldberg, A.V., Werneck, R.F.: Computing point-to-point shortest paths from external memory. In: Workshop on Algorithm Engineering and Experiments, pp. 26–40 (2005)

    Google Scholar 

  10. Goldberg, A.V., Kaplan, H., Werneck, R.F.: Better landmarks within reach. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 38–51. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  11. Sanders, P., Schultes, D.: Engineering Highway Hierarchies. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 804–816. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  12. Bauer, R., Delling, D.: SHARC:Fast and robust unidirectional routing. In: Workshop on Algorithm Engineering and Experiments (2008)

    Google Scholar 

  13. Zhang, L., He, F.G., Zhang, Y.P., et al.: A new algorithm for optimal path finding in complex networks based on the quotient space. Fundamenta Informaticae 93(4), 459–469 (2009)

    MATH MathSciNet  Google Scholar 

  14. Pothen, A., Simon, H., Liou, K.P.: Partitioning sparse matrices with eigenvectors of Graphs. SIAMJ. Matrix Anal. Appl. 11(3), 430–452 (1990)

    Article MATH MathSciNet  Google Scholar 

  15. Girvan, M., Newman, M.E.J.: Community structure in social and biological network. Proc. Natl. Acad. Sci. 99, 7821–7826 (2001)

    Article MathSciNet  Google Scholar 

  16. Radicchi, F., Castellano, C., Cecconi, F., et al.: Defining and identifying communities in networks. Eur. Phys. J. B. 38, 373–380 (2004)

    Article  Google Scholar 

  17. Fortunato, S., Latora, V., Marchiori, M.: A method for finding community structure based on information centrality. Phys. Rev. E 70, 056104 (2004)

    Google Scholar 

  18. Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004)

    Google Scholar 

  19. Ulrik, B., Daniel, D., Marco, G., et al.: On Modularity Clustering. IEEE Transactions on In Knowlegde Data Engineering 20(2), 172–188 (2007)

    Google Scholar 

  20. Fortunato, S., Barthelemy, M.: Resolution limit in community detection. Proc. of the National Academy of Sciences of the United States of America 104(1), 36–41 (2007)

    Article  Google Scholar 

  21. Zhuge, H., Zhang, J.S.: Topological centrality and its applications (2009),http://arxiv.org/abs/0902.1911v1

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Technology, Anhui University, Hefei, 230039, China

    Fugui He, Yanping Zhang, Shu Zhao & Ling Zhang

Authors
  1. Fugui He

    You can also search for this author inPubMed Google Scholar

  2. Yanping Zhang

    You can also search for this author inPubMed Google Scholar

  3. Shu Zhao

    You can also search for this author inPubMed Google Scholar

  4. Ling Zhang

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computer and Information Technology, Beijing Jiaotong University, 100044, Beijing, China

    Jian Yu

  2. Faculty of Economics, University of Catania, Corso Italia, 55, 95129, Catania, Italy

    Salvatore Greco

  3. Department of Mathematics and Computing Science, Saint Mary’s University, B3H 3C3, Halifax, Nova Scotia, Canada

    Pawan Lingras

  4. Institute of Computer Science and Technology, Chongqing University of Posts and Telecommunications, 400065, Chongqing, China

    Guoyin Wang

  5. Institute of Mathematics, Warsaw University, Banacha 2, 02-097, Warsaw, Poland

    Andrzej Skowron

Rights and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

He, F., Zhang, Y., Zhao, S., Zhang, L. (2010). Computing the Point-to-Point Shortest Path: Quotient Space Theory’s Application in Complex Network. In: Yu, J., Greco, S., Lingras, P., Wang, G., Skowron, A. (eds) Rough Set and Knowledge Technology. RSKT 2010. Lecture Notes in Computer Science(), vol 6401. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16248-0_101

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp