Infinite Ergodic Walks in Finite Connected Undirected Graphs ^†

Abstract

The micro-canonical, canonical, and grand canonical ensembles of walks defined in finite connected undirected graphs are considered in the thermodynamic limit of infinite walk length. As infinitely long paths are extremely sensitive to structural irregularities and defects, their properties are used to describe the degree of structural imbalance, anisotropy, and navigability in finite graphs. For the first time, we introduce entropic force and pressure describing the effect of graph defects on mobility patterns associated with the very long walks in finite graphs; navigation in graphs and navigability to the nodes by the different types of ergodic walks; as well as node’s fugacity in the course of prospective network expansion or shrinking.

1. Introduction

The precursor of a concept of statistical ensembles and the related ergodic hypothesis formulated by Boltzmann [1,2] were met with a violently negative reaction by the great majority of scientists for clumsiness, absurd, and paradoxical consequences [3], although it allowed the theoretical calculation of the equations of state for the first time. The study of statistical ensembles related to graphs and networks suffers from a similar inhospitable reception from scientists playing cup-and-ball with a swarm of heuristic parameters and giving any importance to their connection with each other, which is often responsible for spurious conclusions on the graph’s structure and function. The thermodynamic approach to graphs was initiated in complex network theory concerned with the thermodynamic limit of infinitely large graph size $N\to \infty$ [4], in which a graph’s structural “fluctuations” become negligible. The major result of the theory on structurally homogeneous infinite graph (random trees) is the Bose–Einstein condensation mechanism explaining the growth of complex evolving networks as a topological phase transition between a “rich-get-richer” phase and a “winner-takes-all” phase [5,6,7]. In contrast to complex network theory, we consider the statistical ensembles of walks defined on a finite connected undirected graph in the thermodynamic limit of very long walks $n\to \infty ,$ which has previously never been addressed. Statistics of lengthy walks elucidates the graph structure, quantifies navigability of the graph, and evaluates the fugacity of graph nodes with respect to the entire system of infinite paths available in the graph—all of these characteristics are introduced and discussed in our work for the first time. The probability measuring the tendency of a graph to shrivel or expand at a node follows the Fermi–Dirac distribution function. Although we have sketched a set of “ideal gas laws” for the structure of networks and graphs (in the last section of our work), we have not formulated a comprehensive structural "equation of sate" for graphs and networks yet.

The probability we assign to an event depends on whether we count it as one of many, considered all at once, or as a single event of its kind. In other words, an estimated likelihood of events hinges on their assumed membership in an ensemble described by some probability distribution. The famous Two-Child Paradox [8] serves a good example for this point: “Mr. Smith has two children. At least one of them is a boy. What is the probability that both children are boys?” Given that a child is either a boy (B) or a girl (G) with equal probability $\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.,$ two incompatible answers may be given to this question, depending on the assumptions taken.

On the one hand, as the probability of getting a boy equals $Pr\left(B\right)=\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$ uniformly and unconditionally for all families, using the Bayes’ Theorem, we obtain that the probability of having at least one boy in a two-kid family will be the same as just having a boy, viz.,

$$Pr\left(B\&B|B\right)=Pr\left(B|B\&B\right)\times \frac{Pr(B\&B)}{Pr\left(B\right)}=1\times \frac{\left(\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$4$}\right.\right)}{\left(\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}=\frac{1}{2}.$$

On the other hand, as having a boy in an ensemble of two-child families with at least one boy obviously comprises three possible events, i.e., $B\&B$, or $G\&B$, or $B\&G$, the probability of getting a boy in a family of two equals $Pr\left(B\right)=Pr(B\&B)+Pr(B\&G)+Pr(G\&B)=\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$4$}\right.+\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$4$}\right.+\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$4$}\right.=\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$4$}\right.$, and therefore

$$Pr\left(B\&B|B\right)=Pr\left(B|B\&B\right)\times \frac{Pr(B\&B)}{Pr\left(B\right)}=1\times \frac{\left(\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$4$}\right.\right)}{\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$4$}\right.\right)}=\frac{1}{3}.$$

The ensemble interpretation, in which each admissible event in a family of two with a boy appears equally probable, is preferable in the context of ergodic hypothesis blind to family history. In the context of the Two-Child Paradox, there is no way in probability theory to discern if the gender composition in such a family stays put, or children change their sex exploring possible gender identities during an infinite lifetime provided at least one of them stays a boy. The ergodic hypothesis helps to avoid this awkward question by equating the ensemble and time averages while replacing a dynamic description of identity changes by the probabilistic description within the ensemble over a very long period of time. Switching temporal and ensemble perspectives under the spell of ergodic hypothesis is assumed in thermodynamics, equilibrium statistical mechanics, and the theory of dynamical systems.

The concepts of ensembles and ergodicity have a long history [3]. Boltzmann introduced a "monode", a family of possible stationary probability distributions over a single cyclic trajectory of a system of gas particles on an energy surface in the phase space as early as in 1844 [1,2]. According to the Boltzmann hypothesis (1), the time spent by a system in some region of the phase space is proportional to the volume of this region, so that all accessible microstates are equiprobable over a long period of time, viz.,

$$\underset{T\to \infty }{lim}\frac{dt}{T}=\frac{\sigma ds}{\int \sigma ds},$$

(1)

where $\sigma$ is the probability density of microstates on the iso-energetic surface, whose area element is $ds$. With this hypothesis, Boltzmann [1,2] and later Helmholtz [9,10] were able to explain the classical equilibrium thermodynamics, which successfully describes the behavior of gases. The concept of thermodynamic ensembles was further developed and coined into the English-speaking world by Gibbs [11].

In our work, we review three classical thermodynamic ensembles defined by Gibbs [11]—the microcanonical (Section 2), canonical (Section 4), and grand canonical (Section 8) ensembles of very long walks defined in finite connected undirected graphs—and demonstrate that the concept of ergodic ensembles might be applied to quite abstract objects of discrete mathematics. The thermodynamic limit in our approach is defined as the limit of very long walks $n\to \infty$ in a finite graph rather than the limit for a large number of graph nodes N. In the limit $N\to \infty$, “fluctuations” of graph structural features are negligible, and therefore the graph can be considered as structurally homogeneous across all scales—random, in the limit $n\to \infty$ fluctuations of the growth rate of the number of distinguishable, long walks in the graph can be ignored, and then graph’s topological entropy $\mu ={log}_2{\alpha }_{max}$ (the log of graph’s spectral radius) and the corresponding Perron eigenvector of the graph adjacency matrix describe the degree of structural complexity, anisotropy, and navigability of the graph.

Each thermodynamic ensemble permits specific statistical behavior. For example, the microcanonical ensemble representing an isolated system (with constant energy) is defined by assigning equal probability to every walk of a given length existing in the graph. All very long walks that fit some probability distribution over graph’s nodes constitute a macrostate in the canonical ensemble of walks defined in the graph. For example, the series of intrinsic random walks (introduced in Section 5) make up equal probabilities to all walks of a given length starting at a node providing an example of the canonical ensemble of walks defined on the finite graph. This canonical ensemble contains not only the very well-known isotropic nearest-neighbor random walks on finite graphs [7,12], but also infinitely many types of less known anisotropic random walks on graphs—and the Ruelle–Bowen random walk [13,14] making up all infinite walks starting at each node equally probably is one among them. While the ergodic theory for isotropic random walks on finite graphs is well developed [15,16] (We profoundly thank our referee for this remark), the ergodic properties of anisotropic random walks, including their statistical confinement in the best structurally integrated sub-graphs (see Section 5 and Section 7), have not been discussed in literature yet. Finally, in an open system of long walks represented by the grand canonical ensemble, chemical potential (free energy absorbed by a very long walk seizing graph’s edge) is kept fixed and equal the graph’s topological entropy $\mu$.

We also discuss applications of ergodic walks to the structural analysis of and navigation through finite undirected connected graphs. Graph’s structural defects and boundaries repel very long walks that can be be expressed in terms of entropic pressure and force (Section 3). Intrinsic random walks forming the canonical ensemble in a graph can be used to measure the degree of graph’s structural anisotropy (Section 5), to estimate the amount of predictable (navigable) information about present navigator’s location (Section 6) and assess the navigability to each graph node in proportion to its relative visiting frequency (Section 7). Navigation focuses on locating a navigator’s position compared to known locations, paths, and structural patterns [17]. The navigability to a node comprises two information components compatible with two major navigation strategies, known as path integration (that allows for keeping track of the position and heading while exploring a new space) and landmark-based piloting (re-calculating position when in a familiar environment), working in concert during navigation in humans and animals [17]. Finally, the grand canonical ensemble describes the statistics of local fluctuations of the growth rate of the numbers of long walks around the chemical potential as $n\to \infty$ (Section 8). The distribution of these fluctuations follows Fermi–Dirac statistics and marks graph’s defects and boundary nodes hosting dramatically less very long walks than others.

We conclude in the last section.

2. The Micro-Canonical Ensemble of Equiprobable Walks in Finite Connected Undirected Graphs

The number of walks of length n (i.e., n–walks) in a lattice ${\mathbb{Z}}^d$ in d-dimensional space grows exponentially with n, ${\mathcal{N}}_n=2^{nd}$. The micro-canonical ensemble is defined by assigning equal probability to every n–walk, viz.,

$${\wp }_n=\frac{1}{2^{nd}}=exp\left(-\frac{nd}{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$ln2$}\right.}\right)\equiv exp\left(\frac{{\mathcal{F}}_n}{kT}\right),$$

(2)

where the (Boltzmann constant and) temperature $kT\equiv \raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$ln2$}\right.$, the free energy of the n–walks is

$${\mathcal{F}}_n\equiv -{log}_2{\wp }_n=-kTln{\mathcal{N}}_n\equiv -kT{\mathcal{H}}_n=nd,$$

(3)

and ${\mathcal{H}}_n\equiv ln{\mathcal{N}}_n=ndln2$ is the entropy in a micro-canonical ensemble. As the free energy ${\mathcal{F}}_n$ is the Legendre transformation of the internal energy $U_n$, with $kT$ as the independent variable [18,19], viz.,

$${\mathcal{F}}_n\equiv U_n-kT{\mathcal{H}}_n,$$

comparing this definition with (3), we conclude that the internal energy of all n–walks is $U_n=0$ in a micro-canonical ensemble.

We also readily extend the statistical description of micro-canonical ensemble of equiprobable walks to $\kappa$-regular graphs, in which every vertex has the same number of neighbors, $\kappa =2^d$, by using the substitution $d={log}_2\kappa$. As the free energy value (3) grows linearly with n, the intensive free energy (per absorbed edge), viz.,

$$\mu \equiv \underset{n\to \infty }{lim}\frac{{\mathcal{F}}_n}{n}=kT\underset{n\to \infty }{lim}\frac{{\mathcal{H}}_n}{n}={log}_2\kappa =d,$$

(4)

plays the role of chemical potential describing the change to free energy after absorbing a new edge to a very long walk in a $\kappa$-regular graph in a micro-canonical ensemble.

Given a finite connected undirected graph $G(V,E$) where V, $\left|V\right|=N$, is a set of vertices, and $E\subseteq V\times V$ is a set of edges, we assume that its adjacency matrix (such that $A_{i,j}=1$, $\left(i,j\right)\in E$, and $A_{i,j}=0$, otherwise) has the following spectral decomposition $A_{ij}={\sum }_{s=1}^N{\alpha }_s{u}_{is}{u}_{sj},$ with ordered eigenvalues ${\alpha }_{max}\equiv {\alpha }_1>{\alpha }_2\ge \cdots \ge {\alpha }_N$. The free energy in the micro-canonical ensemble equals

$$\begin{array}{ccc}{\mathcal{F}}_n\hfill & =& {log}_2{\mathcal{N}}_n={log}_2\sum _{ij}{A}_{ij}^n={log}_2\sum _{ij}\left(\sum _{s=1}^N{\alpha }_s^n{u}_{is}{u}_{js}\right)\hfill \\ \hfill & =& {log}_2\sum _{s=1}^N{\alpha }_s^n{\gamma }_s^2={log}_2{\gamma }_1^2{\alpha }_{max}^n\left(1+\sum _{s=2}^N\frac{{\gamma }_s^2}{{\gamma }_1^2}{\left(\frac{{\alpha }_s}{{\alpha }_{max}}\right)}^n\right),{\gamma }_s\equiv \sum _{i=1}^N{u}_{is},\hfill \end{array}$$

(5)

and, since $\left(\raisebox{1ex}{${\alpha }_s$}\!\left/ \!\raisebox{-1ex}{${\alpha }_{max}$}\right.\right)<1,$ the intensive free energy amounts to the logarithm of the spectral radius ${\alpha }_{max}$ of the graph, viz.,

$$\mu =\underset{n\to \infty }{lim}\frac{{\mathcal{F}}_n}{n}=\underset{n\to \infty }{lim}\frac{1}{n}{log}_2{\gamma }_1^2{\alpha }_{max}^n\left(1+\sum _{s=2}^N\frac{{\gamma }_s^2}{{\gamma }_1^2}{\left(\frac{{\alpha }_s}{{\alpha }_{max}}\right)}^n\right)={log}_2{\alpha }_{max}\equiv d_G.$$

(6)

In Section 8, the quantity (6) plays the role of chemical potential of an edge absorbed by a very long walk. For a $\kappa$—regular graph, its spectral radius ${\alpha }_{max}=\kappa$, so that ${\mu =log}_2\kappa =d,$ in accordance with (4). The log of graph spectral radius (6) is also called the topological entropy of the graph [20,21] because it is the exponential growth rate of the number of distinguishable walks, being a measure of complexity of the graph structure. According to (4), the topological entropy of the graph $\mu$ can also be interpreted as the effective dimension of space of the graph, $d_G,$ in a micro-canonical ensemble of very long walks.

3. Entropic Pressure and Force in Micro-Canonical Ensemble of Walks

Missing nodes and edges might dramatically reduce the number of very long walks available in a graph, reshaping the global mobility patterns in a micro-canonical ensemble of walks. Statistical changes in mobility patterns due to graph defects that can be described in terms of entropic pressure and entropic force are as follows.

Namely, a missing node depletes the number of very long walks available in the graph, and therefore reduces the corresponding free energy, ${\mathcal{F}}_n={log}_2{\sum }_{ij}{A}_{ij}^n,$ by the following amount of local energy,

$$\begin{array}{ccc}{\mathcal{E}}_i^{\left(n\right)}\hfill & =& {log}_2\sum _j{\left(A^n\right)}_{ij}\hfill \\ \hfill & =& {log}_2{\alpha }_{max}^n{u}_{i1}{\gamma }_1\left(1+\sum _{s=2}^N{\left(\frac{{\alpha }_s}{{\alpha }_{max}}\right)}^n\left(\frac{u_{is}}{u_{i1}}\right)\left(\frac{{\gamma }_s}{{\gamma }_1}\right)\right),\hfill \end{array}$$

(7)

corresponding to the number of very long walks anchoring at i, viz.,

$${\delta }_i{\mathcal{F}}_n\equiv \left({\mathcal{F}}_n-{\mathcal{E}}_i^{\left(n\right)}\right).$$

(8)

In the thermodynamic limit $n\to \infty$, the resulting local increment of free energy measuring its sensitivity to the disappearance of node from the graph is as follows:

$$\begin{array}{ccc}{\left.\mathsf{\Delta }\mathcal{F}\right|}_i\hfill & =& \underset{n\to \infty }{lim}\left({\delta }_i{\mathcal{F}}_n-{\mathcal{F}}_n\right)=-\underset{n\to \infty }{lim}{log}_2\left(\frac{{\sum }_{ij}{\left(A^n\right)}_{ij}-{\sum }_j{\left(A^n\right)}_{ij}}{{\sum }_{ij}{\left(A^n\right)}_{ij}}\right)\hfill \\ \hfill & =& -{log}_2\left(1-\frac{u_{i1}}{{\gamma }_1}\right)\equiv {\mathcal{P}}_i.\hfill \end{array}$$

(9)

We call the resulting quantity (9) entropic pressure ${\mathcal{P}}_i$, as it accounts for the local stress characterizing the transfer of walker’s mobility from i to the rest of the graph if i is not available (see Figure 1 Left).

Similarly, by eliminating an edge $\left(i,j\right)\in E$ from the graph, we reduce the local energy ${\mathcal{E}}_i^{\left(n\right)}$ of the node $i\in V$ (7) by the following amount, $\delta {\mathcal{E}}_{i,j}^{\left(n\right)}={log}_2\left({\sum }_s{A}_{is}^n-A_{ij}\left[{\sum }_k{\left(A^{n-1}\right)}_{jk}\right]\right),$ corresponding to the number of $\left(n-1\right)$-walks available from the node $j\in V$ adjacent to i, viz.,

$$\begin{array}{ccc}{\left.\mathsf{\Delta }\mathcal{E}\right|}_{i\to j}\hfill & =& \underset{n\to \infty }{lim}-{log}_2\left(\frac{{\sum }_s{\left(A^n\right)}_{is}-A_{ij}{\sum }_k{\left(A^{n-1}\right)}_{ik}}{{\sum }_s{\left(A^n\right)}_{is}}\right)\hfill \\ \hfill & =& \underset{n\to \infty }{lim}-{log}_2\left(1-\frac{A_{ij}{\sum }_k{\left(A^{n-1}\right)}_{jk}}{{\sum }_s{\left(A^n\right)}_{is}}\right)\hfill \\ \hfill & =& -{log}_2\left(1-\frac{A_{ij}{u}_{j1}}{{\alpha }_{max}{u}_{i1}}\right)=-{log}_2\left(1-W_{ij}^{(\infty )}\right)\equiv {\mathcal{F}}_{ij}.\hfill \end{array}$$

(10)

The direction dependent entropic force ${\mathcal{F}}_{ij}$ introduced in (10) emerges from the statistical tendency of very long walks to follow the preferential transition $W_{ij}^{(\infty )}$ to the neighboring nodes hosting many infinitely long walks, as in the Ruelle–Bowen random walk (19) [13,14]. It is worth-mentioning that the expression for the entropic force (10) has the structure of a Laplacian operator ${\mathcal{L}}_{ij}=\left(1-W_{ij}^{(\infty )}\right)$ related to random walks defined in the graph G by the transition matrix $W_{ij}^{(\infty )}$.

In Figure 1, we have presented a membrane graph with a defect and highlighted its nodes according to the values of entropic pressure (9) (left) and the elements of Perron eigenvector of the matrix ${\mathcal{F}}_{ij}$ (10) (right) in the membrane graph.

In Figure 2, we use the graph representation of Lubbock, TX, USA acquired from the OpenStreetMap service (The OpenStreetMap database is publicly available at https://dataverse.harvard.edu/dataverse/osmnx-street-networks). To construct the spatial graph of the city, we used Python’s lxml library to parse the raw data and obtain the spatial graph adjacency matrix. The data set was cleaned further by removing disconnected neighborhoods, such as the Preston Smith International airport that is not a structural part of the city. The resulting connected city graph of Lubbock contains 10,421 nodes representing all spaces of movement, including but not limited to residential, secondary, tertiary roads, trunk links, and highways.

The value of entropic pressure in the spatial graph of Lubbock attains maximum at the contemporary structural focus of the city, far apart from the city historical downtown (Figure 2 Left). The nodes of the city spatial graph on the right-hand side of Figure 2 are highlighted according to elements of the Fiedler eigenvector belonging to the second largest eigenvalue of the entropic force matrix ${\mathcal{F}}_{ij}$ (i.e., the second smallest eigenvalue of the associated Laplacian matrix ${\mathcal{L}}_{ij}$). The Fiedler eigenvector is used in spectral graph partition, as it bisects the graph into only two connected communities based on the sign of the second vector entry. The Fiedler eigenvector indicates the direction of the fastest decrease of the entropic force over the city spatial graph of Lubbock (Figure 2 Right). The entries of the Fielder eigenvector are zero everywhere, except for a narrow band extended from the historical city center (where the magnitudeof entropic force is positive) toward the contemporary structural focus of the city (where the magnitude of entropic force is negative). The structural focus of the city absorbs very long walks while the historical center anchored at the abolished city railway station expels long walks. Although railway construction enhanced the city status of Lubbock in early days, its maintenance has a continuing negative impact on the urban development, since railways barricade streets, dramatically cutting down the number of possible paths people can drive or walk and create isolated neighborhoods [22].

4. The Canonical Ensemble of Walks in Finite Connected Undirected Graphs

The canonical ensemble represents the possible states of a system in equilibrium that does not evolve over time, even though the underlying system might be in constant motion [11]. The canonical ensemble is a collection of very long walks (microstates) of length $n={\sum }_{r=1}^s{n}_r\gg 1$, where $n_r$ counts the number of visits paid by a walker to the r-th vertex of a connected undirected graph $G,$ compatible with a $\pi$-macrostate, a discrete probability density vector ${\left\{{\pi }_r\right\}}_{r=1}^N$, ${\sum }_{r=1}^N{\pi }_r=1$, taken over the set of graph vertices, viz., $n_r/n{⟶}_{n\to \infty }{\pi }_r$.

The total number of microstates (i.e., long walks) lumped into a single $\pi$-macrostate is then given by the following multinomial coefficient:

$$M\left(n,s\right)=\frac{n!}{n_1!\cdots n_s!}=\frac{n!}{\left(n{\pi }_1\right)!\cdots \left(n{\pi }_s\right)!}$$

(11)

Using Stirling’s approximation, $lnn!\approx -n+nlnn,$ we readily obtain that

$$\begin{array}{ccc}lnM\left(n,s\right)\hfill & \approx & \left(n-nlnn\right)-\left(n_1-n_{1}ln{n}_1\right)\cdots -\left(n_s-n_{s}ln{n}_s\right)\hfill \\ \hfill & =& n\sum _{r=1}^s\frac{n_r}{n}·ln\frac{n_r}{n},\hfill \end{array}$$

(12)

and therefore, as $n\to \infty$

$$M\left(n,s\right)\approx exp\left(n\sum _{r=1}^s\frac{n_r}{n}·ln\frac{n_r}{n}\right)\approx exp\left(n\sum _{r=1}^s{\pi }_r·ln{\pi }_r\right)\approx exp\left(-nH\right),$$

(13)

in which

$$H\equiv -\sum _{r=1}^N{\pi }_r·ln{\pi }_r,0·log0=log{0}^0=log1=0,$$

(14)

is the Boltzmann–Gibbs–Shannon entropy [23,24] in the canonical ensemble. If every very long walk lumped to the $\pi$-macrostate is chosen with equal probability among the other walks suited for the same macrostate, ${\wp }_n\approx expnH$, then the most probable walks would be those compatible with the uniform density ${\pi }_r=\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$N$}\right.,$$r=1,\dots ,N$, maximizing the value of entropy (14), $H_{max}=lnN.$ The free energy over the canonical ensemble of very long $\pi$-walks ($n\to \infty$) is given by

$${\mathcal{F}}_n=-kTln{\wp }_n\approx kT·nH,$$

(15)

and, therefore, the intensive free energy (chemical potential) equals

$$\mu =\underset{n\to \infty }{lim}\frac{{\mathcal{F}}_n}{n}=kT·H=-\sum _{r=1}^N{\pi }_r·{log}_2{\pi }_r\equiv I\left(\pi \right),$$

(16)

where $I\left(\pi \right)$ is the amount of information (in bits) revealed at every step of the $\pi$ -walk.

5. The Canonical Ensemble of Intrinsic Random Walks in Finite Connected Undirected Graphs

Discrete time random walks $\mathcal{W}=\left\{X_n\in V:n\in \mathbb{Z}\right\}$ defined in a finite connected undirected graph $G(V,E)$ by an irreducible row -stochastic transition probability matrix $W_{ij}=$$Pr\left(X_{n+1}=j|X_n=i\right)>0$, $i,j\in V,$$\left(i,j\right)\in E$ are the natural candidates for the $\pi$-macrostates in the canonical ensemble of walks. Indeed, as the row-stochastic transition matrix $W_{ij}$ does not evolve over time, the unique stationary distribution of the random walk $\mathcal{W}$ is the major left eigenvector ${\pi =\left\{{\pi }_r\right\}}_{r=1}^N$ of the transition matrix, such that ${\sum }_{s=1}^N{\pi }_r{W}_{rs}={\pi }_s$.

Given the graph adjacency matrix $A_{i,j}=1,$$\left(i,j\right)\in E,$ and $A_{i,j}=0$ otherwise, we define the $n^{th}$-order degree of the vertex $i\in V$ as the number of n-walks available at $i\in V,$ viz.,

$${\kappa }_i^{\left(n\right)}\equiv \sum _{j=1}^N{\left(A^n\right)}_{ij},{\kappa }_i^{\left(0\right)}=1.$$

(17)

Taking further into account that ${\kappa }_i^{\left(n+1\right)}={\sum }_{j=1}^N{A}_{ij}{\kappa }_j^{\left(n\right)}$, we derive an infinite sequence of transition probability matrices [25], viz.,

$$W_{ij}^{\left(n\right)}=\frac{A_{ij}{\kappa }_j^{\left(n\right)}}{{\kappa }_i^{\left(n+1\right)}}=\frac{A_{ij}{\sum }_{s=1}^N{\left(A^n\right)}_{js}}{{\sum }_{s=1}^N{A}_{is}{\sum }_{s=1}^N{\left(A^n\right)}_{sr}},\sum _{j=1}^N{W}_{ij}^{\left(n\right)}=1,n\in \mathbb{N},$$

(18)

defining a countable set of intrinsic random walks in the graph G.

The first order intrinsic random walk defined by the transition matrix $W_{ij}^{\left(1\right)}=\raisebox{1ex}{$A_{ij}$}\!\left/ \!\raisebox{-1ex}{${\kappa }_i^{\left(1\right)}$}\right.$ has been discussed in literature for more than a century [12,26]. The walk $W_{ij}^{\left(1\right)}$ is locally isotropic, as the random walker chooses the next node to visit among all nearest neighbors of the current node with equal probability. In Figure 3, we presented densities of nodes in the membrane graph with respect to the different types of intrinsic random walks. Density of nodes with respect to $W_{ij}^{\left(1\right)}$ is proportionate to their degree centrality, i.e., the numbers of links incident upon the nodes (Figure 3, left). Other intrinsic random walks following the transition probabilities, $W_{ij}^{\left(n\right)}$, $n>1,$ make all ${\kappa }_i^{\left(n\right)}$n-walks starting at the node i to occur with equal probability. These random walks are locally biased (anisotropic), as transitions to the nearest neighbors providing more lengthy walks are more preferable under (18) for $n>1$ [25]. In the limit $n\to \infty$, the series of transition matrices $W_{ij}^{\left(n\right)}$ converges [25] to the Ruelle–Bowen random walk [21] (also known as the maximal entropy random walk [27]), viz.,

$$W_{ij}^{\left(\infty \right)}=\underset{n\to \infty }{lim}{W}_{ij}^{\left(n\right)}=\underset{n\to \infty }{lim}\frac{A_{ij}{\kappa }_j^{\left(n\right)}}{{\kappa }_i^{\left(n+1\right)}}=\underset{n\to \infty }{lim}\frac{A_{ij}{\alpha }_{max}^n{u}_{j1}{\gamma }_1}{{\alpha }_{max}^{n+1}{u}_{i1}{\gamma }_1}=\frac{A_{ij}{u}_{j1}}{{\alpha }_{max}{u}_{i1}}.$$

(19)

The anisotropic random walk $W_{ij}^{\left(\infty \right)}$ is confined in the central nodes of the membrane graph (Figure 3, right). The stationary distribution for the intrinsic random walks (18) reads as follows [25]:

$${\pi }_i^{\left(n\right)}=\frac{{\kappa }_i^{\left(n\right)}{\kappa }_i^{\left(n-1\right)}}{{\sum }_{s=1}^N{\kappa }_s^{\left(n\right)}{\kappa }_s^{\left(n-1\right)}}.$$

(20)

For the isotropic random walks $W_{ij}^{\left(1\right)}$, the stationary distribution ${\pi }_i^{\left(1\right)}=\raisebox{1ex}{${\kappa }_i^{\left(1\right)}$}\!\left/ \!\raisebox{-1ex}{$2E$}\right.$, where E is the total number of edges in the graph [12], and ${\pi }_i^{\left(\infty \right)}=u_{i1}^2$, for the Ruelle–Bowen random walks [27]. The stationary distribution ${\pi }_i^{\left(1\right)}$ reports on the degree centrality of the graph nodes (i.e., the number of links incident upon a node), and ${\pi }_i^{\left(\infty \right)}$ is naturally related to the eigenvector centrality $u_{i1}$ of the node i in the graph G [28].

The time until a random walk approaches the stationary distribution (Figure 3) (i.e., the mixing time) is determined by the spectral gap, the difference between the two largest eigenvalues of the transition matrix. Spectral gaps is maximum (mixing time is minimum) over the canonical ensemble of intrinsic random walks for the anisotropic random walk $W_{ij}^{\left(\infty \right)}$ (Figure 4).

The relative entropy rate [29] between two Markov chains defined by their transition matrices,

$$\begin{array}{ccc}\eta \left(n\right)\hfill & =& \sum _{i=1}^N{\pi }_i^{\left(1\right)}\sum _{j=1}^N{W}_{ij}^{\left(1\right)}{log}_2\frac{W_{ij}^{\left(1\right)}}{W_{ij}^{\left(n\right)}}=\frac{1}{2E}\sum _{i,j}{A}_{ij}{log}_2\frac{{\kappa }_i^{\left(n\right)}}{{\kappa }_j^{(n-1)}{\kappa }_i^{\left(1\right)}}\hfill \\ \hfill & =& \frac{1}{2E}\sum _{i,j}\left(A_{ij}{log}_2\frac{{\kappa }_i^{\left(n\right)}}{{\kappa }_j^{(n-1)}}-{\delta }_{ij}{log}_2{\kappa }_i^{\left(1\right)}\right)\equiv \frac{1}{2E}\sum _{i,j}\left(A_{ij}{\mathsf{\Delta }}_{ij}^{\left(n\right)}-{\delta }_{ij}{d}_i\right),\hfill \end{array}$$

(21)

can be used for measuring information divergence over the canonical ensemble of intrinsic random walks in connected undirected graphs and the degree of graph directional anisotropy [25].

In (21), we have introduced $d_i\equiv {log}_2{\kappa }_i^{\left(1\right)},$ a local counterpart of the space dimension parameter (4), and its generalization to n-walks, the directional graph space dimension tensor

$${\mathsf{\Delta }}_{ij}^{\left(n\right)}\equiv {log}_2\frac{{\kappa }_i^{\left(n\right)}}{{\kappa }_j^{(n-1)}}$$

(22)

measuring the degree of directional anisotropy in transitions of the intrinsic random walks making up all n-walks available from the node i with equal probability. For $n=1$, the graph space dimension tensor (22) reduces to the space dimension, ${\mathsf{\Delta }}_{ij}^{\left(1\right)}=d_i$, as ${\kappa }_i^{\left(0\right)}=1$ for all nodes. In the thermodynamic limit $n\to \infty ,$ the graph space dimension tensor reduces to a direction dependent counterpart of the effective space dimension of the graph $d_G$ (6) (or the graph topological entropy), viz.,

$${\mathsf{\Delta }}_{ij}^{(\infty )}={log}_2\frac{{\alpha }_{max}{u}_{i1}}{u_{j1}}.$$

(23)

6. Navigation through Graphs over Canonical Ensembles of Walks

The problem of effective navigation in graphs and networks can be considered in the framework of canonical ensemble of walks, since the navigator location prediction requires a density of locations that is known. Frequently visited sites are predicted more efficiently than little frequented, especially in the long-run [30].

Given a $\pi$ -walk $\mathcal{W}=\left\{X_t\in V:t\in \mathbb{Z}\right\}$ defined in a connected undirected graph $G(V,E)$, Bayes’ theorem [29,31] describes the probability of navigator’s present location X based on prior knowledge of her previous location t steps before, $X_{-t}\stackrel{t}{\to }X.$ Namely, $X_{-t}$ may be a t-step precursor of X with the following probability:

$$Pr\left(X_{-t}|X\right)=\frac{Pr\left(X_{-t}\stackrel{t}{\to }X\right)\pi \left(X_{-t}\right)}{\pi \left(X\right)},$$

(24)

where $Pr\left(X_{-t}\stackrel{t}{\to }X\right)$ is the probability of walking from $X_{-t}$ to X precisely in t steps; $\pi \left(X_{-t}\right)$ and $\pi \left(X\right)$ are the densities of locations $X_{-t}$ and X with respect to the $\pi$-walk, respectively. $Pr\left(X_{-t}|X\right)$ is a density of the t-step precursors for the location X induced by the density of walks $\pi$. If $Pr\left(X_{-t}|X\right)=\pi \left(X_{-t}\right),$ it follows from (24) that the location X is unpredictable (as any other location $X_{-t}$ is a precursor for X). The available information about visiting the location X at present is therefore scattered over the entire graph in the past and can be assessed by observing all possible t-step precursors $X_{-t}$, viz.,

$$\mathcal{P}\left(X\right)=Pr\left(X_{-t}|X\right){log}_2\frac{Pr\left(X_{-t}|X\right)}{\pi \left(X_{-t}\right)}$$

(25)

The information divergence [29] (25) vanishes if and only if the density of t-step precursors $Pr\left(X_{-t}|X\right)$ for the location X over the graph G is identical to $\pi \left(X_{-t}\right)$, so that visiting the location $X_{-t}$ in the past is statistically independent of visiting the present location X t steps later, and therefore $X_{-t}$ is not a t-step precursor of X [30]. The amount of information (25) attains its maximum value, viz.,

$$max{\mathcal{P}}_t\left(X\right)=-{log}_2\pi \left(X\right),$$

(26)

whenever the marginal probability $\pi \left(X\right)$ is the major left eigenvector of the t-step transition matrix $Pr\left(X_{-t}\stackrel{t}{\to }X\right)$, so that $Pr\left(X_{-t}|X\right)=1,$ for all t and $X_{-t}$, i.e., visiting any location in the graph G by $\pi$-walk with probability 1 is a predictor for visiting any other location X t steps later.

According to the Boltzmann equation (1), for ergodic observables, the time average of the maximal information (26) over the entire history of $\pi$-walks equals the entropy of the $\pi$-walk (16), viz.,

$$\underset{t\to \infty }{lim}\frac{1}{t}\sum _{\tau =0}^{t}max{\mathcal{P}}_{\tau }\left(X\right)=-\sum _{\left\{X\right\}}\pi \left(X\right){log}_2\pi \left(X\right)=kT·H\left(X\right)\equiv I\left(\pi \right).$$

(27)

However, the actual amount of predictable (navigable) information about present navigator’s location may be quite modest, much less than the amount information revealed at every step of the $\pi$-walk ((16) and (27)): different graphs have different degrees of navigability.

7. Navigability of Graphs and Graph Nodes over Canonical Ensembles of Walks

The information function (27) can be represented as a sum of the predictable and unpredictable information components [32], viz.,

$$I\left(\pi \right)=P\left(\pi \right)+U\left(\pi \right).$$

(28)

The predictable information component $P\left(\pi \right)$ measures the amount of apparent uncertainty about the navigator’s location that can be resolved with some navigation strategy compatible with the $\pi$-walks, and $U\left(\pi \right)$ gauges the amount of true uncertainty about the navigator’s location that cannot be inferred anyway. In the following, we attribute the predictable information component $P\left(\pi \right)$ to the navigability of the graph G by the $\pi$-walk.

Assuming that both information components in (28) have the same form as the information function (27), viz.,

$$P\left(\pi \right)=-\sum _{r=1}^N{\pi }_r·{log}_2{\phi }_r,\mathtt{and}U\left(\pi \right)=-\sum _{r=1}^N{\pi }_r·{log}_2{\psi }_r,$$

(29)

with some partition functions ${\phi }_r$ and ${\psi }_r$, such that ${\pi }_r={\phi }_r{\psi }_r$, we obtain

$$I\left(\pi \right)=-\sum _{r=1}^N{\pi }_r·{log}_2{\phi }_r{\psi }_r,{\phi }_r=\raisebox{1ex}{${\pi }_r$}\!\left/ \!\raisebox{-1ex}{${\psi }_r$}\right..$$

(30)

We call the partition function ${\phi }_r$ the navigability to the node $r\in V$ in the graph G by the $\pi$-walk. Obviously, the navigability to the node ${\phi }_r$ is proportional to its relative visiting frequency ${\pi }_r$—as the more frequent the location, the higher its forecast accuracy—and inverse proportional to the partition function ${\psi }_r$ assessing uncertainty of visiting the node r by the $\pi$-walk.

There are two major navigation strategies—landmark-based piloting and walk integration—working in concert during wayfinding in humans and animals [17]. First, the next visit location $X_{t+1}$ can be guessed from the present navigator’s position $X_t$ in the graph, and the degree of accuracy of such a guess can be assessed by the mutual information between the present and future navigator’s location conditioned on the walk history, $I\left(X_t;X_{t+1}|X_{t-1},\dots X_1\right)$. This strategy can be naturally associated with landmark-based piloting.

If the $\pi$-walk is a random walk defined by a transition matrix $W_{ij}$, the conditional mutual information for such a Markov chain depends only upon the immediate past navigator’s location $X_{t-1}$, but not on the entire historical sequence of locations visited by the navigator in the more distant past [32], so that

$$\begin{array}{ccc}I\left(X_t;X_{t+1}|X_{t-1}\right)\hfill & =& H\left(X_{t+1}|X_{t-1}\right)-H\left(X_t|X_{t-1}\right)\hfill \\ \hfill & =& \sum _{k=1}^N{\pi }_k\sum _{r=1}^N\left(W_{kr}{log}_2{W}_{kr}-W_{kr}^2{log}_2{W}_{kr}^2\right).\hfill \end{array}$$

(31)

Second, some degree of uncertainty about the navigator’s future location $X_{t+1}$ might be resolved after all revisiting, and a possible correlation between walks are taken into account in the course of walk integration over the presumably infinite motion history of $\pi$-walk. The latter quantity is given by the excess entropy [33,34,35],

$$E\left(\pi \right)=I\left(\pi \right)-h\left(\pi \right)$$

(32)

where the entropy rate [29],

$$h\left(\pi \right)=\underset{t\to \infty }{lim}\frac{1}{t}\sum _{k=1}^{t}H\left(X_t|X_{t-1},\dots X_1\right)$$

(33)

quantifies the mean amount of uncertainty consisting in the whole (infinite) path history of the $\pi$-walks. However, it is intuitive that the values of conditional entropies $H\left(X_t|X_{t-1},{\dots X}_1\right)$ in the r.h.s. of (33) do not increase with the length of walks and, therefore, $I\left(\pi \right)\ge h\left(\pi \right)$, so that $E\left(\pi \right)\ge 0$.

For a random walk defined by a transition matrix $W_{ij}$, the Markov property simplifies the expression for the entropy rate (33), viz.,

$$\begin{array}{ccc}h\left(\pi \right)\hfill & =& \underset{t\to \infty }{lim}\frac{1}{t}\sum _{k=1}^{t}H\left(X_t|X_{t-1},\dots X_1\right)\hfill \\ \hfill & =& \underset{t\to \infty }{lim}\left[\frac{1}{t}H\left(X_1\right)+\frac{1}{t}\left(H\left(X_2|X_1\right)+H\left(X_3|X_2\right)+\dots \right)\right]\hfill \\ \hfill & =& \underset{t\to \infty }{lim}\left[\frac{1}{t}H\left(X_1\right)+\frac{t-1}{t}H\left(X_2|X_1\right)\right]\hfill \\ \hfill & =& H\left(X_2|X_1\right)=-\sum _{k=1}^N{\pi }_k\sum _{r=1}^N{W}_{kr}{log}_2{W}_{kr},\hfill \end{array}$$

(34)

so that the excess entropy (32) reads as follows:

$$E\left(\pi \right)=-\sum _{k=1}^N{\pi }_k·\left({log}_2{\pi }_k+\sum _{r=1}^N{W}_{kr}{log}_2{W}_{kr}\right).$$

(35)

By summing (31) and (35), we obtain the total amount of predictable information $P\left(\pi \right)$ revealed by the $\pi$-walk in the graph G, viz.,

$$\begin{array}{ccc}P\left(\pi \right)\hfill & =& E\left(\pi \right)+I\left(X_t;X_{t+1}|X_{t-1}\right)\hfill \\ \hfill & =& -\sum _{k=1}^N{\pi }_k·\left({log}_2{\pi }_k+\sum _{r=1}^N{W}_{kr}^2{log}_2{W}_{kr}^2\right)\hfill \\ \hfill & =& -\sum _{k=1}^N{\pi }_k·{log}_2\left({\pi }_k·\prod _{r=1}^N{W}_{kr}^{2W_{kr}^2}\right),\hfill \end{array}$$

(36)

so that the navigability to the node r in the graph G by the random walks defined by the transition matrix $W_{ij}$ is

$${\phi }_k={\pi }_k·\prod _{r=1}^N{W}_{kr}^{2W_{kr}^2}$$

(37)

Navigability to a node evaluated by the partition function (37) depends on the strategy of walkers. In Figure 5, we illustrate the difference by highlighting the nodes of the membrane graph according to the degrees of navigability by the isotropic random walks $W_{ij}^{\left(1\right)}$ (left) and anisotropic random walks $W_{ij}^{(\infty )}$ (right). For the isotropic random walks, the movement of walkers along the low-dimensional boundaries and at the corners of the graph are more predictable than their movements in the bulk, as all bulky locations of the same connectivity are visited with equal probability by the random walk $W_{ij}^{\left(1\right)}$. In contrast with the isotropic random walks, a navigator following the anisotropic strategy $W_{ij}^{(\infty )}$ is statistically confined within the region hosting the most of infinitely long paths available in the graph, where the navigator’s position is very likely.

As demonstrated in [32], the entropy function $I\left(\pi \right)\equiv H\left(X_t\right)$ allows for the following decomposition involving the conditional entropies:

$$\begin{array}{cc}H\left(X_t\right)\hfill & \equiv H\left(X_t\right)-H\left(\left.X_{t+1}\right|X_t\right)+H\left(\left.X_{t+1}\right|X_t\right)\hfill \\ \hfill & =\left(H\left(X_t\right)-H\left(X_{t+1}\right|X_t)\right)+H\left(X_{t+1}|X_t\right)+\left\{H\left(X_t|X_{t-1}\right)-H\left(X_t|X_{t-1}\right)\right\}\hfill \\ \hfill & +\left\{H\left(X_{t+1}|X_{t-1}\right)-H\left(X_{t+1}|X_{t-1}\right)\right\}\hfill \\ \hfill & =\underset{E\left(\pi \right)}{\underbrace{\left(H\left(X_t\right)-H\left(X_{t+1}|X_t\right)\right)}}+\underset{I\left(\left.X_t;X_{t+1}\right|X_{t-1}\right)}{\underbrace{\left(H\left(\left.X_{t+1}\right|X_{t-1}\right)-H\left(\left.X_t\right|X_{t-1}\right)\right)}}\hfill \\ \hfill & +\underset{U\left(\pi \right)}{\underbrace{\left(H\left(\left.X_{t+1}\right|X_t\right)+H\left(\left.X_t\right|X_{t-1}\right)-H\left(\left.X_{t+1}\right|X_{t-1}\right)\right)}}.\hfill \end{array}$$

(38)

Therefore, the remaining part of the information function (28), the last part in the decomposition (38), is the conditional entropy of the present navigator’s location conditioned on her past and future locations, viz.,

$$U\left(\pi \right)=I\left(\pi \right)-P\left(\pi \right)=H\left(X_t|X_{t-1}\right)+H\left(X_t|X_{t-1}\right)-H\left(X_{t+1}|X_{t-1}\right)$$

(39)

assesses the amount of true uncertainty about a navigator’s location that can neither be inferred from integrating over the past history of the $\pi$-walk nor have any repercussion for the navigator walk in the future [34]. For a random walk defined by the transition matrix $W_{ij}$, we readily obtain that

$$\begin{array}{ccc}U\left(\pi \right)=-\sum _{k=1}^N{\pi }_k·{log}_2{\psi }_k\hfill & =& -\sum _{k=1}^N{\pi }_k·{log}_2\left(\frac{{\pi }_k}{{\phi }_k}\right)\hfill \\ \hfill & =& -\sum _{k=1}^N{\pi }_k·{log}_2\left(\prod _{r=1}^N{W}_{kr}^{-2W_{kr}^2}\right),\hfill \end{array}$$

(40)

where the partition function ${\psi }_k$ assesses the amount of uncertainty about navigator’s visiting the node $k\in V$.

8. A Grand-Canonical Ensemble of Ergodic Walks in Finite Connected Undirected Graphs

The grand canonical ensemble represents the possible states of a system exchanging energy and particles with a heat bath in thermodynamic equilibrium [11]. The growth rate of the number of distinguishable paths in a graph tends to its topological entropy $\mu ={log}_2{\alpha }_{max}$ in the thermodynamic limit $n\to \infty$. However, the local growth rate of the number of distinguishable paths available from a node, ${log}_2{\alpha }_{max}{\gamma }_1{u}_{i1},$ might differ from the graph topological entropy. In the grand canonical ensemble, the probability to observe such a "fluctuation" of the long paths growth rate inferior to the topological entropy at the node i is taken to be

$${\mathfrak{P}}_i^{\left(n\right)}=\frac{1}{{\mathcal{Z}}_n}exp\left(\frac{{\delta }_i{\mathcal{F}}_n}{kT}\right),{\mathcal{Z}}_n\equiv \sum _{j=1}^{N}exp\left(\frac{{\delta }_j{\mathcal{F}}_n}{kT}\right),$$

(41)

where ${\delta }_i{\mathcal{F}}_n=\left({\mathcal{F}}_n-{\mathcal{E}}_i^{\left(n\right)}\right)$ is a fluctuation of free energy (8) associated with heterogeneity of growth rate of the number of very long walks in the graph. The grand partition function ${\mathcal{Z}}_n$ amasses the fugacity $exp\left(\frac{{\delta }_j{\mathcal{F}}_n}{kT}\right)$ of all nodes in the graph, playing the role of a normalization factor in (41). In the thermodynamic limit $n\to \infty$, ${lim}_{n\to \infty }{\mathcal{F}}_n=$${lim}_{n\to \infty }{log}_2{\sum }_{ij}{A}_{ij}^n$= ${lim}_{n\to \infty }{log}_2{\alpha }_{max}^n$$=n\mu$, and ${lim}_{n\to \infty }{\mathcal{E}}_i^{\left(n\right)}$$={lim}_{n\to \infty }{log}_2{\alpha }_{max}^n{u}_{i1}{\gamma }_1$, so that the expression for the node’s fugacity takes the following form:

$$\begin{array}{ccc}exp\left(\frac{{\delta }_i\mathcal{F}}{kT}\right)\hfill & =& \underset{n\to \infty }{lim}exp\left(\frac{n\mu -{\mathcal{E}}_i^{\left(n\right)}}{kT}\right)\hfill \\ \hfill & =& exp\left(\frac{[{log}_2{\alpha }_{max}^n-{log}_2{\alpha }_{max}^n{u}_{i1}{\gamma }_1]}{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$ln2$}\right.}\right)\hfill \\ \hfill & =& \frac{{\alpha }_{max}^n}{{\alpha }_{max}^n{u}_{i1}{\gamma }_1}=\frac{1}{u_{i1}{\gamma }_1},{\gamma }_1\equiv \sum _{j=1}^N{u}_{j1},\hfill \end{array}$$

(42)

the grand partition function reads as follows:

$$\mathcal{Z}\equiv \underset{n\to \infty }{lim}{\mathcal{Z}}_n=\frac{1}{{\gamma }_1}\sum _{j=1}^N\frac{1}{u_{j1}},{\gamma }_1\equiv \sum _{i=1}^N{u}_{i1},$$

(43)

and, finally, the grand canonical probability (41) takes the form of a Fermi–Dirac distribution in the thermodynamic limit $n\to \infty$, viz.,

$${\mathfrak{P}}_i=\underset{n\to \infty }{lim}{\mathfrak{P}}_i^{\left(n\right)}=\frac{\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$u_{i1}$}\right.}{{\sum }_{j=1}^N\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$u_{j1}$}\right.}=\frac{1}{1+{\sum }_{j\ne i}^N\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$u_{j1}$}\right.}.$$

(44)

The grand potential $\mathrm{\Omega }$ playing the role of free energy with respect to the grand partition function $\mathcal{Z}$ in grand-canonical ensemble equals:

$$\mathrm{\Omega }=-kTln\mathcal{Z}={log}_2\left(\frac{1}{{\gamma }_1}\sum _{j=1}^N\frac{1}{u_{j1}}\right).$$

(45)

Having a form of the relative fugacity of a node, the grand canonical probability (44) can be regarded as measuring the ease of separation of the vertex from the rest of graph with respect to the entire system of infinite paths. The nodes with the long paths growth rate inferior to the topological entropy are insufficiently integrated into the graph structure and might be lost or acquire new connections in the course of prospective graph structural modifications.

In Figure 6, we have presented the membrane graph (left) and the spatial graph of the city of Lubbock, Texas (right), with their nodes colored according to values of grand canonical probabilities (44). The nodes located on the low-dimensional graph boundaries, at the corners of membrane graph and in the loosely connected south suburbs of the city of Lubbock have distinctly higher relative fugacity than others. These nodes can also be regarded as the points of prospective network growth in where the graph as a system of infinite paths remains open. Interestingly, the highlighted nodes in the spatial graph of Lubbock (Figure 6 right) mark the city neighborhoods currently under construction.

9. Discussion and Conclusions

We have defined three major thermodynamic ensembles of ergodic walks in connected undirected graphs, in the thermodynamic limit of infinitely long walks and showed that the ergodic mindset might be applied not only to particles of ideal gases, but also to quite abstract objects of discrete mathematics, such as graphs.

We have demonstrated that graph structural defects and irregularities, such as missing nodes and edges, might dramatically reduce the number of available very long paths, globally reshaping the mobility patterns in the entire graph. In the framework of micro-canonical ensembles, we may consider their effect as resulting from actions of the entropic pressure and force repelling walkers from structural irregularities and boundaries toward the best integrated region of the network: the laxer the connection, the stronger the repelling. Perhaps, the cumulative effect of entropic forces generated by railways and other structural obstacles along with the unbalanced growth of urban neighborhoods might be responsible for the urban decay process in the historical districts of some cities.

We have also shown that the problem of effective navigation [36] in graphs and networks can be considered with respect to a canonical ensemble of walks, as an effective location prediction of a navigator’s position, and requires a density of locations in the walk be known. According to the probabilistic setting, frequently visited sites are predicted more efficiently than little frequented, especially in the long run: the more frequent a node, the more predictable the navigator’s position visiting it. Regular lattices and homogeneous graphs lacking structural salience and landmarks might also be confusing environments dramatically, reducing predictability of navigator’s position.

Finally, we have studied the grand canonical ensemble of very long paths describing the statistics of fluctuations of the local path growth rate with respect to the graph topological entropy. In the thermodynamic limit of infinite paths, the distribution of the relative fugacity over the graph nodes takes the form of Fermi–Dirac distribution function. The high relative fugacity value of a node assumes that the degree of its integration into the system of infinite paths is insufficient, indicating that the graph is open for the prospective structural modifications associated with the node. In the urban spatial graphs, the nodes of high fugacity might be concentrated in the neighborhood under construction, marking the points of city network growth.

Future research should consider a comprehensive structural "equation of sate" for networks and graphs.