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)
    for i=1:c, KI(i)=sum(G(:,i))

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

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


// 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


// 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


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

function [P]=probK(nk,n)

// 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)

    // Set i as index for subgraph with vertex i as predecessor
    for i=1:r,
        // Take next subgraph G from GLIST
        // 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
        // Calculate estimate for necessary steps
        PrPATH(i,2)=(1/PrPATH(i,1))* (i+1)


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

function [PrPATH]=estimator(PrPATH)

Gerd Doeben-Henisch 2013-01-14