Optimal and Critical Path Analysis of State Transportation Network Using Neo4J

Authors: Pallavi Bhogaram, Xiaolong Wu, Min He, Onyedikachi Okenwa

Abstract:

A transportation network is a realization of a spatial network, describing a structure which permits either vehicular movement or flow of some commodity. Examples include road networks, railways, air routes, pipelines, and many more. The transportation network plays a vital role in maintaining the vigor of the nation’s economy. Hence, ensuring the network stays resilient all the time, especially in the face of challenges such as heavy traffic loads and large scale natural disasters, is of utmost importance. In this paper, we used the Neo4j application to develop the graph. Neo4j is the world's leading open-source, NoSQL, a native graph database that implements an ACID-compliant transactional backend to applications. The Southern California network model is developed using the Neo4j application and obtained the most critical and optimal nodes and paths in the network using centrality algorithms. The edge betweenness centrality algorithm calculates the critical or optimal paths using Yen's k-shortest paths algorithm, and the node betweenness centrality algorithm calculates the amount of influence a node has over the network. The preliminary study results confirm that the Neo4j application can be a suitable tool to study the important nodes and the critical paths for the major congested metropolitan area.

Keywords: Transportation network, critical path, connectivity reliability, network model, Neo4J application, optimal path, critical path, edge betweenness centrality index, node betweenness centrality index, Yen’s k-shortest paths.

References:

[1] Yu Gu, Xiao Fu, Zhiyuan Liu, Xiangdong Xu, Anthony Chen, “Performance of transportation network under perturbations: reliability, vulnerability, and resilience” November 2019.
[2] I. M. Obeidat and S. Y. Berkovich, "Reliability of network connectivity," 2008 First International Conference on the Applications of Digital Information and Web Technologies (ICADIWT), Ostrava, 2008, pp. 435-441.
[3] I. K. Isukapati and G. F. List, "Using travel time reliability measures with individual vehicle data," 2016 IEEE 19th International Conference on Intelligent Transportation Systems (ITSC), Rio de Janeiro, 2016, pp. 2131-2136.
[4] W. J. Rueger, "Reliability Analysis of Networks with Capacity-Constraints and Failures at Branches & Nodes," in IEEE Transactions on Reliability, vol. 35, no. 5, pp. 523-528, Dec. 1986.
[5] C. Tanguy, "Exact two-terminal reliability of some directed networks," 2007 6th International Workshop on Design and Reliable Communication Networks, La Rochelle, 2007, pp. 1-8.
[6] "What Is a Graph Database and Property Graph | Neo4j", Neo4j Graph Database Platform. (Online). Available: https://neo4j.com/developer/graph-database/. (Accessed: 04- Sep- 2019).
[7] "Cypher Query Language Developer Guides & Tutorials", Neo4j Graph Database Platform. (Online). Available: https://neo4j.com/developer/cypher-query-language/. (Accessed: 22- Sep- 2019).
[8] M. Needham and A. Hodler, "Graph Algorithms in Neo4j: Neo4j Graph Analytics", Neo4j Graph Database Platform, 2018. (Online). Available: https://neo4j.com/blog/graph-algorithms-in-neo4j-neo4j-graph-analytics/. (Accessed: 20- Oct- 2019).
[9] Mark Needham, A., n.d. Graph Algorithms. (Online). O’Reilly Online Learning. Available at: (Accessed: 6 November 2019).
[10] Amy E. Hodler, M., 2018, “A Comprehensive Guide to Graph Algorithms in Neo4j”, (ebook) Neo4j, p.34. Available at: (Accessed: 11 February 2020).
[11] “Betweenness_centrality - NetworkX 1.10 documentation", Networkx.github.io, (Online). Available: https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.centrality.betweenness_centrality.html. (Accessed: 19- Oct- 2019).
[12] Ulrik Brandes, "A Faster Algorithm for Betweenness Centrality", Journal of Mathematical Sociology, vol. 25, no. 2, pp. 163-177, 2001.
[13] “Edge_betweenness_centrality — NetworkX 1.10 documentation", Networkx.github.io. (Online). Available: https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.centrality.edge_betweenness_centrality.html#networkx.algorithms.centrality.edge_betweenness_centrality. (Accessed: 23- Sep- 2019).
[14] “9.4.6. The Yen’s K-shortest paths algorithm - 9.4. Path finding algorithms", Neo4j.com. (Online). Available: https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/yen-s-k-shortest-path/. (Accessed: 17- Oct- 2019).