# 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
```

Gerd Doeben-Henisch 2013-01-14