In our previous post we looked at the concept of a Random Walk on a graph and how they can be put to use. In this post we continue our exploration of different ways to move around a Graph by looking at Graph Search Algorithms that allow us to find a specific node and even determine the path to reach it.
We will introduce and compare Depth First Search, Breath First Search and Dijkstra’s Algorithm using Zachary’s Karate Club Network a well known (and small) network before applying Dijkstra’s algorithm to the OpenStreetMap of Manhattan to generate turn by turn directions.
We’d also like to take this opportunity to let you know that this coming Tuesday, March 9, we’re organizing an online webinar on Graph and Network Algorithms that you might find interesting. We hope to see you there!
Zachary’s Karate Club Network
In 1977 Wayne Zachary publish a seminal paper analyzing the way in which the social network of a local Karate Club evolved following a rift between the two main instructors. The…
