Shortest Path of a Random Graph and its Application
DOI:
https://doi.org/10.13052/jgeu0975-1416.1214Keywords:
Random graph, shortest path, probability distribution, weighted graph, unweighted graphAbstract
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
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.