Shortest Path of a Random Graph and its Application

Authors

  • Laxminarayan Sahoo Department of Computer and Information Science, Raiganj University, Raiganj-733134, West Bengal, India
  • Rakhi Das Department of Computer and Information Science, Raiganj University, Raiganj-733134, West Bengal, India

DOI:

https://doi.org/10.13052/jgeu0975-1416.1214

Keywords:

Random graph, shortest path, probability distribution, weighted graph, unweighted graph

Abstract

The goal of this work is to provide an effective method for determining the shortest path in random graphs, which are complicated networks with random connectivity patterns. We have developed an algorithm that can identify the shortest path for both weighted and unweighted random graphs to accomplish our objective. As connectivity in these types of structures is changing, the algorithm adjusts to different edge weights and node configurations to provide fast and precise shortest path searching. The study shows that the suggested method performs more successfully in finding the shortest path throughout random graphs using comprehensive computations. Many networks, including social networks, granular networks, road traffic networks, etc., include nodes that can connect to one another and create random graphs in the present-day computational era. The outcomes demonstrate how flexible it is, which makes it a useful tool for practical uses in domains where random graph structures are common, like transportation networks, communication systems, and social networks. For illustration, we have taken into consideration an actual case study of communication road networks here. We have determined the shortest path of the road networks using our proposed algorithm, and the results have been presented. Better decision-making across a range of areas is made possible by this study, which advances effective algorithms designed for complicated and unpredictable network environments.

Downloads

Download data is not yet available.

Author Biographies

Laxminarayan Sahoo, Department of Computer and Information Science, Raiganj University, Raiganj-733134, West Bengal, India

Laxminarayan Sahoo is currently an Associate Professor of Computer and Information Science, Raiganj University, Raiganj, India. He obtained his MSc from Vidyasagar University, India and his PhD from The University of Burdwan, India. He has received MHRD fellowship from Govt. of India and received Prof. M.N. Gopalan Award for Best PhD thesis in Operations Research from Operational Research Society of India (ORSI). He is a reviewer of several international journals and Academic Editor of International Journal “Mathematical Problems in Engineering,” Hindawi Publication. He is also Associate Editor of “Journal of Graphic Era University” River Publication. His specializations include, Wireless Sensor Network, Distributed Computing, Reliability Optimization, Genetic Algorithms, Particle Swarm Optimization, Graph Theory, Fuzzy Game Theory, Interval Mathematics, Soft Computing, Fuzzy Decision making and Operations Research. He has published a good number of articles in international and national journals of repute. Dr. Sahoo is the author of the books “Advanced Operations Research” published by Asian Books, New Delhi, “Advanced Optimization and Operations Research” published by Springer Nature, Singapore. He edited a book entitled “Real Life Applications of Multiple Criteria Decision – Making Techniques in Fuzzy Domain” published by Springer Nature and wrote several chapters from reputed publishers like Springer, IGI Global, CRC Press, Walter de Gruyter, McGraw-Hill and Elsevier. He is a fellow of ISROSET.

Rakhi Das, Department of Computer and Information Science, Raiganj University, Raiganj-733134, West Bengal, India

Rakhi Das received her B. Tech. from BIET Suri in 2006 & M. Tech. from NIT Durgapur in 2010. She is currently Pursuing Ph.D. in Computer and Information Science from Raiganj University since 2021. She has published two research paper in reputed international journal Mathematics published by MDPI and International Journal of Scientific Research in Mathematical and Statistical Sciences. Her main research work focuses on Graph Theory. She has 10 years of teaching experience.

References

Samanta, S., Pal, M., Mahapatra, R., Das, K., and Bhadoria, R. S. (2021). A study on semi-directed graphs for social media networks. International Journal of Computational Intelligence Systems, 14(1), 1034–1041.

Sporns, O. (2018). Graph theory methods: applications in brain networks. Dialogues in clinical neuroscience, 20(2), 111–121.

Thorup, M. (1997, October). Undirected single source shortest paths in linear time. In Proceedings 38th Annual Symposium on Foundations of Computer Science (pp. 12–21). IEEE.

Katerinis, P., and Tsikopoulos, N. (2005). Edge-connectivity and the orientation of a graph. SUT Journal of Mathematics, 41(1), 1–10.

Orlin, J. B., Madduri, K., Subramani, K., and Williamson, M. (2010). A faster algorithm for the single source shortest path problem with few distinct positive lengths. Journal of Discrete Algorithms, 8(2), 189–198.

Wang, Z, H., Shi, S, S., Yu, L, and C., Chen, W, Z., (2012). An efficient constrained shortest path algorithm for traffic navigation, In Advanced Materials Research, 356, 2880–2885.

Jicy, N., and Mathew, S. (2014). Some new connectivity parameters for weighted graphs. Journal of Uncertainty in Mathematics Science, 2014, 1–9.

Li, S., and Li, Y. (2019). Semi-dynamic shortest-path tree algorithms for directed graphs with arbitrary weights. arXiv preprint arXiv:1903. 01756.

Bonato, A., Delić, D., and Wang, C. (2016). The Structure and Automorphisms of Semi-directed Graphs. Journal of Multiple-Valued Logic & Soft Computing, 27, 161–173.

Mohammed, A, M., (2017). Mixed graph representation and mixed graph isomorphism. Journal of Science. 30 (1), 303–310.

Sotskov, Y. N. (2020). Mixed graph colorings: A historical review. Mathematics, 8(3), 385.

Deen, Zeen El., M. R., and Omar, N. A. (2021). Extending of edge even graceful labeling of graphs to strong r-edge even graceful labeling. Journal of Mathematics, 2021, 1–19.

Sahoo, L., Sen, S., Tiwary, K, S., Samanta, S., and Senapati, T., (2022). Modified Floyd–Wars hall’s Algorithm for Maximum Connectivity in Wireless Sensor Networks under Uncertainty. Discrete Dynamics in Nature and Society 2022, 1–11.

Singh, A., and Mishra, P. K., (2014). Performance Analysis of Floyd-Warshall Algorithm vs Rectangular Algorithm, International Journal of Computer Applications, 107(16), 23–27.

Brodnik, A., Grgurovic, M., and Pozar, R. (2022). Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time. Ars Math. Contemp., 22(1), 1.

Bukhori, D., and Dengen, N. (2018, April). Floyd-warshall algorithm to determine the shortest path based on android. In IOP Conference Series: Earth and Environmental Science (Vol. 144, No. 1, p. 012019). IOP Publishing.

Erdős, P., and Rényi, A. (1959). On random graphs I. Publ. math. debrecen, 6(290–297), 18.

Barabási, A. L., and Albert, R. (1999). Emergence of scaling in random networks. science, 286(5439), 509–512.

Drobyshevskiy, M., and Turdakov, D. (2019). Random graph modeling: A survey of the concepts. ACM computing surveys (CSUR), 52(6), 1–36.

Caimo, A., and Friel, N. (2011). Bayesian inference for exponential random graph models. Social networks, 33(1), 41–55.

Robins, G., Pattison, P., Kalish, Y., and Lusher, D. (2007). An introduction to exponential random graph (p*) models for social networks. Social networks, 29(2), 173–191.

Snijders, T. A., Pattison, P. E., Robins, G. L., and Handcock, M. S. (2006). New specifications for exponential random graph models. Sociological methodology, 36(1), 99–153.

Snijders, T. A. (2002). Markov chain Monte Carlo estimation of exponential random graph models. Journal of Social Structure, 3(2), 1–40.

Bollobás, B., and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica, 24(1), 5–34.

Aiello, W., Chung, F., and Lu, L. (2001). A random graph model for power law graphs. Experimental mathematics, 10(1), 53–66.

Nobari, S., Lu, X., Karras, P., and Bressan, S. (2011, March). Fast random graph generation. In Proceedings of the 14th international conference on extending database technology (pp. 331–342).

Garlaschelli, D. (2009). The weighted random graph model. New Journal of Physics, 11(7), 073005.

Janson, S., Łuczak, T., Turova, T., and Vallier, T. (2012). Bootstrap percolation on the random graph G_n,p.

Chung, F., and Lu, L. (2004). The average distance in a random graph with given expected degrees. Internet Mathematics, 1(1), 91–113.

Newman, M. E. (2009). Random graphs with clustering. Physical review letters, 103(5), 058701.

Isufi, E., Loukas, A., Simonetto, A., and Leus, G. (2017). Filtering random graph processes over random time-varying graphs. IEEE Transactions on Signal Processing, 65(16), 4406–4421.

Baccelli, F., Błaszczyszyn, B., and Haji-Mirsadeghi, M. O. (2011). Optimal paths on the space-time SINR random graph. Advances in Applied Probability, 43(1), 131–150.

Hassin, R., and Zemel, E. (1985). On shortest paths in graphs with random weights. Mathematics of Operations Research, 10(4), 557–564.

Bacco, C., Franz, S., Saad, D., and Yeung, C. H. (2014). Shortest node-disjoint paths on random graphs. Journal of Statistical Mechanics: Theory and Experiment, 2014(7), P07009.

Kryven, I., Duivenvoorden, J., Hermans, J., and Iedema, P. D. (2016). Random graph approach to multifunctional molecular networks. Macromolecular Theory and Simulations, 25(5), 449–465.

Van Der Hofstad, R., Hooghiemstra, G., and Van Mieghem, P. (2002). The flooding time in random graphs. Extremes, 5(2), 111–129.

Onat, F. A., and Stojmenovic, I. (2007, June). Generating random graphs for wireless actuator networks. In 2007 IEEE international symposium on a world of wireless, mobile and multimedia networks (pp. 1–12). IEEE.

Onat, F. A., and Stojmenovic, I. (2007, June). Generating random graphs for wireless actuator networks. In 2007 IEEE international symposium on a world of wireless, mobile and multimedia networks (pp. 1–12). IEEE.

Servetto, S. D., and Barrenechea, G. (2002, September). Constrained random walks on random graphs: Routing algorithms for large scale wireless sensor networks. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications (pp. 12–21).

Yang, Y., Guo, H., Tian, T., and Li, H. (2015). Link prediction in brain networks based on a hierarchical random graph model. Tsinghua Science and Technology, 20(3), 306–315.

Klootwijk, S., Manthey, B., and Visser, S. K. (2021). Probabilistic analysis of optimization problems on generalized random shortest path metrics. Theoretical computer science, 866, 107–122.

Kivimäki, I., Shimbo, M., and Saerens, M. (2014). Developments in the theory of randomized shortest paths with a comparison of graph node distances. Physica A: Statistical Mechanics and its Applications, 393, 600–616.

Downloads

Published

2024-04-16

How to Cite

Sahoo, L., & Das, R. (2024). Shortest Path of a Random Graph and its Application. Journal of Graphic Era University, 12(01), 53–76. https://doi.org/10.13052/jgeu0975-1416.1214

Issue

2024: Vol 12 Iss 1

Section

Articles