Probability of Vertices: probDGraph()

A first simple scilab program translating the ideas of Caldarelli [39] is given below:

//**************************************
// Probability within directed graphs
// probDGraph()
//
//**************************************
// Authors: G.Doeben-Henisch
//
// First: Dec-17, 2012
// Last: Dec-17, 2012
//******************************************
// Idea
// We assume here directed graphs as models for possible paths in mazes
// We are interested in the probabilities within such graphs with regard to certain properties
// One important property is the probability to find the shortest path to a goal in the maze = vertex in the graph
//********************************************
// A directed graph is assumed to be a set of vertices V with directed edges E between the vertices. 
// An edge can have a weight w in W.

//*******************************************
// Example graphs see in file 'graph_models.sci'
//

//*********************************
// In-Degree of vertex
// degreeIn()
//
// G := Matrix of graph
// KI := Array of In-Degree of every vertex
// KI(i,2) := Frequencies of the degree in column 1
// MKI := Mean value of in-degrees

function [KI,MKI]=degreeIn(G)
    
    [r,c]=size(G)
    KI=zeros(r,2)
    for i=1:c, KI(i)=sum(G(:,i))
    end
    MKI=mean(KI(:,1))
endfunction

//***************************************
// Frequency of every In-Degree
// freqDegreeIn()
//

function [KI,MKI,KIF]=freqDegreeIn(G)
    
// Extract InDegree from Graph

[KI,MKI]=degreeIn(G)

// Find maximal Indegree

KIFmax=0,[r,c]=size(G),for i=1:c, if(KI(i)>KIFmax) then KIFmax=KI(i),end,end

//Prepare Frequency array

KIF=zeros(KIFmax,1)

// Compute Frequency distribution

for j=1:KIFmax,for i=1:c,if (KI(i,1)==j) then KIF(j)=KIF(j)+1,end,end,end

// Attach freuencies to values in KI

for j=1:KIFmax,for i=1:c,if KI(i,1)==j then KI(i,2)=KIF(j),end,end,end

endfunction




//*********************************
// probK()
// n := number of vertices in graph
// nk := number of vertices with k edges

function [P]=probK(nk,n)
    
    P=nk/n
endfunction

//******************************************************************
// Compute path stepwise
// by computing the dependent probability for two adjacent vertices
//
// pathProb()
//
// Prepare:
// (1) Partition the final graph into subgraphs following the 
// intended path
// (2) Collect all subgraphs in a list of increaqsing subgraphs
// (3) Compute for every subgraph the probability of the final vertex
// depending from the preceding subgraph

function [PrPATH]=pathProb(GLIST)

    [r,c]=size(GLIST)
    PrPATH=zeros(r,2)
    
    // Set i as index for subgraph with vertex i as predecessor
    for i=1:r,
        
        // Take next subgraph G from GLIST
        
       G=eval(GLIST(i)),
       [KI,MKI,KIF]=freqDegreeIn(G)
       
        // Compute nominator
         n=i+1,Nominator=KI(i,1)*KI(i+1)*  probK(KI(i,2),n)*  probK(KI(i+1,2),n)

        // Compute denominator
        Denominator=(MKI^2)*2 //The term '*2' is not from Caldarelli and shifts the results 'above' the empirical values

        // Compute final value
        PrPATH(i)=Nominator/Denominator
        
        // Calculate estimate for necessary steps
        PrPATH(i,2)=(1/PrPATH(i,1))* (i+1)

    end
endfunction

//************************************
// estimator()
// 
// Estimator takes the probabilities from PrPATH and multiplies these
// with the inherent number of steps (and with 100)

function [PrPATH]=estimator(PrPATH)
    
    
endfunction