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
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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)
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)
Bargiela, A., Pedrycz, W.: Human centric information processing through granular modelling. Springer, Berlin (2009)
Yao, Y.Y.: Triarchic theory of granular computing. In: Zhang, Y.P., et al. (eds.), pp. 115–143. Science press, Beijing (2010) (in Chinese)
Pawlak, Z.: Rough Sets Theoretical Aspects of Reasoning about Data. Kluwer Academic Publishers, Dordrecht (1991)
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)
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)
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)
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)
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)
Sanders, P., Schultes, D.: Engineering Highway Hierarchies. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 804–816. Springer, Heidelberg (2006)
Bauer, R., Delling, D.: SHARC:Fast and robust unidirectional routing. In: Workshop on Algorithm Engineering and Experiments (2008)
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)
Pothen, A., Simon, H., Liou, K.P.: Partitioning sparse matrices with eigenvectors of Graphs. SIAMJ. Matrix Anal. Appl. 11(3), 430–452 (1990)
Girvan, M., Newman, M.E.J.: Community structure in social and biological network. Proc. Natl. Acad. Sci. 99, 7821–7826 (2001)
Radicchi, F., Castellano, C., Cecconi, F., et al.: Defining and identifying communities in networks. Eur. Phys. J. B. 38, 373–380 (2004)
Fortunato, S., Latora, V., Marchiori, M.: A method for finding community structure based on information centrality. Phys. Rev. E 70, 056104 (2004)
Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004)
Ulrik, B., Daniel, D., Marco, G., et al.: On Modularity Clustering. IEEE Transactions on In Knowlegde Data Engineering 20(2), 172–188 (2007)
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)
Zhuge, H., Zhang, J.S.: Topological centrality and its applications (2009),http://arxiv.org/abs/0902.1911v1
Author information
Authors and Affiliations
School of Computer Science and Technology, Anhui University, Hefei, 230039, China
Fugui He, Yanping Zhang, Shu Zhao & Ling Zhang
- Fugui He
You can also search for this author inPubMed Google Scholar
- Yanping Zhang
You can also search for this author inPubMed Google Scholar
- Shu Zhao
You can also search for this author inPubMed Google Scholar
- Ling Zhang
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
School of Computer and Information Technology, Beijing Jiaotong University, 100044, Beijing, China
Jian Yu
Faculty of Economics, University of Catania, Corso Italia, 55, 95129, Catania, Italy
Salvatore Greco
Department of Mathematics and Computing Science, Saint Mary’s University, B3H 3C3, Halifax, Nova Scotia, Canada
Pawan Lingras
Institute of Computer Science and Technology, Chongqing University of Posts and Telecommunications, 400065, Chongqing, China
Guoyin Wang
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
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-16247-3
Online ISBN:978-3-642-16248-0
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative