Mapping the Jams: Traffic Analysis Using Graph Theory

Graph theory has plenty of applications in real-life problems such as social networks, molecular biology, or geospatial data. Today, I’ll present the last one, analyzing city’s road layout to predict critical streets, junctions, and how changes to the infrastructure can affect it. But first, let’s start with the basics. <h1>Graphs and their centrality measures</h1> Graphs are sets of vertices and their edges: <img alt="" src="https://miro.medium.com/v2/resize:fit:700/1*0-BL4a7R8Rfaxx7Iv5WuHw.png" style="height:54px; width:700px" /> Set E is subset of unordered tuples (x, y) where x and y are vertices of the graph and x is not equal to y. [Image by the author] Where the edges represent connections between the nodes. If edges do not have directions, we call a graph undirected. A real-life example of an undirected graph can be a chemical molecule, where the vertices are atoms, and bonds are represented as edges. <img alt="" src="https://miro.medium.com/v2/resize:fit:392/1*evyY_-YJ6bx-qxgh2Rz83w.png" style="height:310px; width:392px" /> Serotonin molecule is an example of a simple undirected graph. [<a href="https://commons.wikimedia.org/wiki/File:Serotonin-Spartan-HF-based-on-xtal-3D-balls-web.png" rel="noopener ugc nofollow" target="_blank">source</a>] However, sometimes we need information about whether the edge goes from u to v, from v to u, or both ways. For example, if Mark likes Alice, it doesn’t necessarily mean it’s mutual  In those situations, we can define the edge as an ordered tuple instead of unordered one. <a href="https://towardsdatascience.com/mapping-the-jams-traffic-analysis-using-graph-theory-a387135ea748">Click Here</a>