Transportation Geography and Network Science/Algorithms

Dijkstra's algorithmEdit

The centrality measures requires finding the shortest path from one node to another. The most widely-used algorithm is Dijkstra's algorithm. A greedy algorithm, the Dijkstra's algorithm starts at the source node and gradually spans a tree to all nodes reachable. Nodes that provide the shortest distance in that round are added to the tree by sequence.

Dijkstra’s Algorithm is regarded as one of the most efficient algorithms to calculate the shortest path.

For the directed graph   defined previously, a shortest (travel time) path between origin node   to every other node in the network can be calculated using this algorithm. Let   be the distance matrix of   with   representing the length (travel time) of the links from node   to node  , if nodes   and  are not connected then the corresponding element in   is a very large number.

Say the set of nodes   is divided into two different subsets   and  , where   represents the set of nodes to which shortest path from   is known and the complementary set of   is  . Let represent a vector of permanent labels of nodes corresponding to every node in  . The permanent label of a node is the shortest distance of the node from the origin node  . Say   is the set of nodes that are adjacent to nodes in   along the shortest path. Let   be a vector of temporary labels of nodes corresponding to nodes in  . The steps involved in the algorithm are explained below.

  1. Initialize  , and all elements of   are assigned a large number.
  2. Find all the child nodes that are adjacent to any node   – parent node - in   that are not already in   using the distance matrix  . Then calculate a temporary label to each of the child node   by summing the permanent label of the parent node   from the vector   and length of the link  .
  3. Select the node with smallest temporary label and add it at the end of the set  , deleting it in  . Then add the corresponding parent node   at the end of the set   and corresponding temporary label to   . With the new   repeat the steps from 2 until there are no elements in  .

To get the length of the shortest path from the origin node r to any other node in the network, look for the position of the destination node in   and the corresponding element in gives the length of the shortest path. To get the shortest path itself, look for the position of the destination node s in   and read the element that occupies that same position in   then again look for the position of this new node in   and repeat the process until the node   is reached in  , i.e. tracing the shortest path backward until the origin is reached. The links that lie along the shortest path from origin node   to destination node s calculated this way are assigned to a set  .

The above algorithm is done for a single origin node r, but the shortest path from every node to every other node is required for trip distribution and traffic assignment. In that case perform Dijkstra’s algorithm for every node in the graph  .

Further details of the algorithm can be found in [1].

Community detectionEdit

The goal of community detection is to cluster the network into groups of nodes that have few connections between these nodes. [2]. A cluster is a collection of nodes that are similar in terms of connections. One basic algorithm to identify clusters is the hierarchical clustering algorithm which creates tree-structure hierarchy of clusters. The leaves are the nodes and the root is a single cluster consisting of all nodes. The hierarchies of leaves show the communities of different levels. The details about the algorithm can be found in Hierarchical clustering .

ReferencesEdit

  1. Dijkstra's algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
  2. Newman, M.E. Networks. 2010. Oxford: Oxford University Press.