Message Boards

GROUPS:

Staff Picks Wolfram Science Mathematics Discrete Mathematics Geometry Graphs and Networks Wolfram Language Statistics and Probability Wolfram Summer School

Yousof Mardoukhi

[WWS21] Alexander Orbach Relation and Random Walks on Hypergraphs

Yousof Mardoukhi, University of Potsdam

Posted 1 year ago

2392 Views

1 Reply

2 Total Likes

Follow this post

Introduction

The theory of random walks provides one with a tool to understand and investigate the geometrical and dynamical properties of the underlying structure on which random walks takes place. For instance if the underlying structure is a graph, by investigating how far a random walk process has gone with respect to its initial position, one can extract useful information such as the connectivity between the nodes of the graph. WolframModels which have hypergraph representation, are interesting candidates to investigate the dynamics of such a process. This is of utmost importance, since the WolframModels have causal set representations. This causal sets thus can be faithfully embedded on Lorentzian manifolds. Thus in the continuum limit, the geometrical properties the manifold can be extracted from the embedded causal set and its algebraic structure and vice versa[4].Many properties of the random walk process are understood in terms of the site occupation and first-passage probabilities; with combinatorics and probability generating function of these quantities and knowing the probability transition matrix, such properties are studied for different variations of random walk processes. Here in this project the focus will be on the most generic type of random walk process called Pólya’s walk. Pólya’s walk is a random walk on a d-dimensional lattice which is homogeneous, which implies that the lattice is translationally invariant. Moreover, the Pólya’s walk is unbiased which implies the fact that, the probability of moving from one site to its neighbouring site is the same as if the walk was taking place the other way around. The formalism can be easily extended to the case where the underlying structure is graph. It is worth to mention that, in the case of graphs, the degree of nodes does not need necessarily to be the same as long as the translational invariance is not violated[1].The random walk theory not only provides one with insights about the geometry of the underlying structure and how a dynamical process would behave on such a structure, but naturally establishes a connection between those properties. One of such relations is the Alexander-Orbach (AO) relation which establishes a connection between the the Harmonic (spectral) dimension H, the dynamical exponent

and the Hausdorff dimension D for a random walk process on a connected graph which is embedded in a Riemannian manifold. The relation asserts that [1, 2, 3]

H=2

Dν

. (1)It is noteworthy to mention that the relation above does only hold true under conditions mentioned above. For instance, for the Koch curve, the AO relation remains valid on the contrary, it is violated for the random walk on Cantor dusts.The intention here is to address the validity of AO relation for hypergraphs and furthermore, if it is violated what are the possible extensions or considerations that have to be taken into account to propose a generalised relation such that it can establish connection between the geometry of the hypergraphs and the dynamics of the random walk process on them. This could potentially provide useful insights to establish isomorphism between the causal sets and the Lorentzian manifold on which they are embedded.

Preliminaries

A random walk of Pólya type on a hypergraph H=(V, E), where V is the set of all nodes and E is the set of hyperedges, is defined as random move from a given node

′

to a node v at the step n+1 described via the following

n+1

(v|

′

p(v|

′

)

(

′

)

(2)where

(v|

)

is the occupation probability of being at node

on the

step given that the random walk has started from the initial node

, and

p(v|

′

)

is the probability transition from the node

′

to the node

. The probability transition must by symmetric and moreover, it must be equally distributed amongst the neighbours of v, known as the degree of the node. Hence,

p(v|

′

deg(v)

′

is a neighbour of v; we denote the degree of v with deg(v).The walk is said to be homogeneous (the graph is translationally invariant) if for every

in V,

(v|v)

(which means the probability of being at node

after

step given that the random walk has started from the same node) is the same. This readily implies that no node is preferred to the other nodes.A hyperedge is a set of nodes that connects them. The number of nodes within each hyperedge is referred to as the degree of that hyperedge. This is a generalisation of the concept of edges in graphs that are incident on only two nodes, exactly. For instance a hyperedge of nodes

{1,2,3}

has degree of three. To make it clearer for the reader, consider the following hypergraphsE(H

)

={{1,2,3},{2,3,4,5}}

E(H

)

={{1,2},{1,3},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}}

The hypergraph H

is a normal graph. In other words, every hypergraph where the for every hyperedge within the set of hyperedges the degree is two, that hypergraph is a graph. Below are the plots of H

on the left hand side and H

on the right hand side.

hypg1={{1,2,3},{2,3,4,5}};hypg2={{1,2},{1,3},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}};GraphicsRow[{ResourceFunction["HypergraphPlot"][hypg1,"SubsetBoundary"False],ResourceFunction["HypergraphPlot"][hypg2,"SubsetBoundary"False]}]

Out[]=

Their corresponding projected graphs are shown in the following figure. Note that the graph representation of these two hypergraphs are isomorphic.

graph1=UndirectedGraph[ResourceFunction["HypergraphToGraph"][hypg1]];graph2=UndirectedGraph[ResourceFunction["HypergraphToGraph"][hypg2]];GraphicsRow[{GraphPlot[graph1,VertexLabelsAutomatic,PlotLabelMaTeX["\\mathcal{G}_1"]],GraphPlot[graph2,VertexLabelsAutomatic,PlotLabelMaTeX["\\mathcal{G}_2"]]}]

Out[]=

Thus, the random walk process on the projected graph of hypergraphs does not carry the same information, as during the transformation of the hypergraphs to their projected graphs, the information related to the hyperedges is lost. Therefore, a consideration has to be sought such that the structure of the hypergraphs are encoded in the probability transition matrix.

The natural distance on a graph is defined by the shortest path between two given nodes. It is denoted by d(u,v) for every pair of nodes u and v in V. If there is no path between the two nodes then d(u,v)=∞. Since in this project we are dealing with connected (hyper)graphs, the distance between every two given nodes is finite. Obviously d(v, v) = 0.

Probability Transition Matrix

In order to take into account the structure of the hypergraphs, it is required to understand the connectivity between the nodes that belong to the same hyperedge set and those nodes that are connected via the overlap of other hyperedges. Assume the hypergraph H

, notice that for the node 1, the probability of moving to the either node 2 or 3 is

. That is also reflected on the projected graph G

. Yet, the node 3 belongs to two different hyperedges; in the hyperedge

{1,2,3}

, the probability to move to either node 1 or 2 is again

while in the other hyperedge

{2,3,4,5}

the probability to move to other three nodes 2, 3 and 5 is

. Not surprisingly, it is seen that in G

, node 3 is connected to all other nodes and the probability of moving to each one of them is

. In order to incorporate the structure of the hypergraphs, initially it is required to define the incidence matrix[7]. Assuming the columns representing the hyperedges and the rows the nodes, the incidence matrix shows whether a node belongs to a specific hyperedge or not. It is said that a hyperedge is incident on a node if that node belongs to that given hyperedge. Therefore, the incidence matrix is an

nm

matrix where

is the number of nodes in the set

and

is the number of hyperedges in

. Thence, one can readily define the adjacency matrix and the hyperedge matrix by multiplying the transpose of the incidence matrix onto itself from right and left respectively[7]. For instance the incidence matrices for the hypergraphs H

and H

are given by the followings

incM1=Transpose[{{1,1,1,0,0},{0,1,1,1,1}}]//MatrixFormincM2=Transpose[{{1,1,0,0,0},{1,0,1,0,0},{0,1,1,0,0},{0,1,0,1,0},{0,1,0,0,1},{0,0,1,1,0},{0,0,1,0,1},{0,0,0,1,1}}]//MatrixForm

Out[]//MatrixForm=

1	0
1	1
1	1
0	1
0	1

Out[]//MatrixForm=

1	1	0	0	0	0	0	0
1	0	1	1	1	0	0	0
0	1	1	0	0	1	1	0
0	0	0	1	0	1	0	1
0	0	0	0	1	0	1	1

The probability transition matrix is achieved by knowing the adjacency matrix and the hyperedge matrix. For the hypergraph H

and H

the followings are their respective probability transition matrix. Note that, they are indeed different and the first matrix reflects the hyperedge structure of the hypergraph.

Out[]//MatrixForm=

0	1 2	1 2	0	0
2 13	0	5 13	3 13	3 13
2 13	5 13	0	3 13	3 13
0	1 3	1 3	0	1 3
0	1 3	1 3	1 3	0

Out[]//MatrixForm=

0	1 2	1 2	0	0
1 4	0	1 4	1 4	1 4
1 4	1 4	0	1 4	1 4
0	1 3	1 3	0	1 3
0	1 3	1 3	1 3	0

Random Walks on wm7714 WolfromWorld

The wm7714 WolframModel is chosen to investigate the validity of the AO relation.

hypgraph=ResourceFunction["WolframModel"][{{{1,2,2},{3,1,4}}{{2,5,2},{2,3,5},{4,5,5}}},{{1,1,1},{1,1,1}},1000,"FinalState"];graph=UndirectedGraph[ResourceFunction["HypergraphToGraph"][hypgraph]];dij=GraphDistanceMatrix[graph];HypergraphPlot[hypgraph]GraphPlot[graph]

Out[]=

The figure depicted at top is the hypergraph representation of wm7714 whilst the one at the bottom demonstrates its undirected projected graph which preserves the geodesic distance between the nodes. After arriving at the probability transition matrix associated with the hypergraph representation of wm7714, it is straight forward to simulate random walk process on the undirected projected graph using discrete Markov process, needless to say that a random walk of Polya’s type is a Markov process. Here the initial condition is chosen such that the random walk process starts at node 1 and takes a path of length 1000. An ensemble of 500 of such walks is sampled.

initialState=ConstantArray[0,{Length[vertices]}];initialState[[1]]=1;markovP=DiscreteMarkovProcess[initialState,hyperTransitionMatrix];data=RandomFunction[markovP,{0,1000},500];

Spectral Dimension and the Distinct Visited Nodes

In the dynamical theory of random walk, the number of distinct visited nodes is related to the spectral dimension

via the following relation[2]

<N>

H/2

(3)where

is the number of distinct visited nodes up to

discrete time step and

is the spectral dimension mentioned above. The barcket notation is to be understood as the ensemble average. The simulation shows the following

In[]:=

dsLogLine=ParallelTable[distinctVisitedSites[data,i],{i,1,500}];dspowerlawfit=NonlinearModelFit[dsLogLine,a*

,{a,b},x];dspowerlawfitdata=ParallelTable[dspowerlawfit[i],{i,1,500}];ListLogLogPlot[{dsLogLine,dspowerlawfitdata},AxesTrue,AxesLabel{"n","<N>"},PlotLegends{"Simulation","Power-law Fit"}]dspowerlawfit["ParameterTable"]

Out[]=

	Simulation
	Power-law Fit

Out[]=

	Estimate	Standard Error	t-Statistic	P-Value
a	0.766546	0.003408	224.926	0.
b	0.860018	0.000758752	1133.46	0.

which shows that the half of the spectral dimension has the value 0.86 and consequently the value 1.72 for H.

Dynamical Exponent

In order to estimate the dynamical exponent, the dynamical theory of random walk suggests that the distance that a random walk process has reached at step n, exhibits the following behaviour[2]

<|r(n)-r(0)|>∼

(4)where

is the dynamical exponent and

r(n)

is the distance the random walk process has reached with respect to the initial position it had at

n=0

. The simulation results shows the following trend in the logarithmic scale

In[]:=

meansq=ParallelTable[meanSquaredDisplacement[data,dij,i],{i,300}];msdpowerlawfit=NonlinearModelFit[meansq,a*

,{a,b},x];msdpowerlawfitdata=ParallelTable[msdpowerlawfit[i],{i,1,300}];ListLogLogPlot[{meansq,msdpowerlawfitdata}]msdpowerlawfit["ParameterTable"]

Out[]=

	Estimate	Standard Error	t-Statistic	P-Value
a	0.893354	0.00656322	136.115	2.45221× -270 10
b	0.501706	0.00140468	357.167	0.

which yields a value of 0.50 for

Hausdorff Dimension

In order to calculate the Hausdorff dimension, it is required to define the geodesic ball. The natural metric defined on hypergraph is the same as it is defined for graphs and it is discussed in the introduction. There is a debate whether the definition of the Hausdorff dimension has to be a local or global property of the structure. Bearing this in mind, the procedure below yields a global dimension for the Hausdorff dimension.Assume a random node of the hypergraph. The immediate neighbours of this node are the ones that have distance 1 with respect to this very node; they are called the nearest neighbours. Now take the union of the nearest neighbours and the initial node and seek the nearest neighbours of this new set. Iteratively continue this until all the nodes of the hypergraph are in the set which is formed by successive union operation. Denote the set of nodes at each iteration with

. The diameter of S denoted by diam(S) is the largest distance between the nodes that belong to this set. Consequently, we can define the mass distribution as the number of nodes that belong to the geodesic ball of diam(S). Thus[2, 3, 5],

ρ∼diam

(S)

(5)where ρ denotes the number of nodes. The simulation yields the following result given that the initial node was chosen to be 8.

In[]:=

vertexset={8};tuplearray={};For[i=0,i<500,i++,AppendTo[tuplearray,{Max[GraphDistanceMatrix[NeighborhoodGraph[graph,vertexset]]],Length[vertexset]}];vertexset=VertexList[NeighborhoodGraph[graph,vertexset]];If[Length[vertexset]Length[VertexList[graph]],Break[]];]dfpowerlawfit=NonlinearModelFit[tuplearray,a*

,{a,b},x];dfpowerlawfitdata=Table[{j,dfpowerlawfit[j]},{j,Table[tuplearray[[i]][[1]],{i,1,Length[tuplearray]}]}];ListLogLogPlot[{tuplearray,dfpowerlawfitdata}]dfpowerlawfit["ParameterTable"]

Out[]=

	Estimate	Standard Error	t-Statistic	P-Value
a	0.502128