Table of Contents


File

simple_dijkstra.m

Name

simple_dijkstra

Synopsis

simple_dijkstra - Implements the Dijkstra algorithm and returns the distance from a single vertex to all others, but does not save the path.

Introduction

NOTE: PART OF A SET OF 8 RELATED FILES:

To investigate the dynamic propagation of systemic risk, the authors measure the direction of the relationship between institutions using Granger causality. Specifically, the authors analyze the pairwise Granger causalities between the t and t + 1 monthly returns of the 4 indexes; they say that X Granger-causes Y if c1 has a p-value of less than 5%; similarly, they say that Y Granger-causes X if the p-value of b1 is less than 5%. They adjust for autocorrelation and heteroskedasticity in computing the p-value.

License

=============================================================================

Copyright 2011, Dimitrios Bisias, Andrew W. Lo, and Stavros Valavanis

COPYRIGHT STATUS: This work was funded in whole or in part by the Office of Financial Research under U.S. Government contract TOSOFR-11-C-0001, and is, therefore, subject to the following license: The Government is granted for itself and others acting on its behalf a paid-up, nonexclusive, irrevocable, worldwide license to reproduce, prepare derivative works, distribute copies to the public, perform and display the work.
All other rights are reserved by the copyright owner.

THIS SOFTWARE IS PROVIDED "AS IS". YOU ARE USING THIS SOFTWARE AT YOUR OWN RISK. ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHORS, CONTRIBUTORS, OR THE UNITED STATES GOVERNMENT BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

=============================================================================

Inputs

A
Name:
A
Description:

Adjacency matrix of the network indicating inter-institutional Granger causal relationships. It is generated as output arg connection_matrix from dynamic_causality_index.m. Note: values are yes/no flags, represented as 1/0 values, respectively.

Type:
float
Range:
{0, 1}
Dimensions:

KxK matrix

  1. Rows represent institutions.
  2. Columns represent institutions..

node
Name:
node
Description:

The node of origin from which the shortest paths to any destination node will be calculated.

Type:
integer
Range:
{1,...,+K}
Dimensions:

scalar


Outputs

distances
Name:
distances
Description:

Shortest path lengths from the origin node (parameter) to destination nodes.

Type:
integer
Range:
{1,...,+inf}
Dimensions:

Kx1 matrix

  1. Rows represent destination nodes.

Code

% Run warning message
warning('OFRwp0001:UntestedCode', ...
    ['This version of the source code is very preliminary, ' ...
     'and has not been thoroughly tested. Users should not rely on ' ...
     'these calculations.']);



num_nodes = size(A,1);
% Initialize all the distances to inf
distances = inf*ones(1,num_nodes); % distance s-all nodes
% Self-distance is 0
distances(node) = 0;

T = 1:num_nodes;    % node set with shortest paths not found yet

while ~(isempty(T))
    [d_min,index] = min(distances(T));

    for j=1:length(T)
        % If there is connection and current distance is closer, update it 
        if A(T(index),T(j))>0 && distances(T(j))>distances(T(index)) ...
                +A(T(index),T(j))
            distances(T(j))=distances(T(index))+A(T(index),T(j));
        end
    end

    T = setdiff(T,T(index));
end

Examples

NOTE: Numbers used in the examples are arbitrary valid values.
They do not necessarily represent a realistic or plausible scenario.

 Visual representation of the graph used:

         N4
         |  \
    N1 - N2 - N3    N6  <-- not connected
      \      /
       \   /
         N5

Adjacency_matrix may be symmetric or non-symmetric as granger relationships can be unidirectional or bidirectional between nodes.

 adjacency_matrix = [0,1,0,0,1,0; ...
                     1,0,1,1,0,0; ...
                     0,1,0,1,1,0; ...
                     0,1,1,0,0,0; ...
                     1,0,1,0,0,0; ...
                     0,0,0,0,0,0];

 node = 1;

 distances = simple_dijkstra(adjacency_matrix,node);

References

Billio et al. (2010). Econometric measures of systemic risk in the finance and insurance sectors (No. w16223). National Bureau of Economic Research.

Bisias et al. (2012). A survey of systemic risk analytics (Working paper #0001). Washington, DC: Office of Financial Research, 65-69.