{'fraction_non_alphanumeric': 0.029750479846449136, 'fraction_numerical': 0.01171487193063737, 'mean_word_length': 4.62318570896911, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Intelligibility and First Passage Times In Complex Urban Networks

Topology of urban environments can be represented by means of graphs. We explore the graph representations of several compact urban patterns by random walks. The expected time of recurrence and the expected first passage time to a node scales apparently linearly in all urban patterns we have studied In space syntax theory, a positive relation between the local property of a node (qualified by connectivity or by the recurrence time) and the global property of the node (estimated in our approach by the first passage time to it) is known as intelligibility. Our approach based on random walks allows to extend the notion of intelligibility onto the entire domain of complex networks and graph theory.


Spatial networks of urban environments
More than half of all humans are now living in cities [Ash:2008 et al].
Cities are responsible for a great deal of global energy consumption and of greenhouse gas emissions. The global challenges of sustainable development call for a quantitative theory of urban organization. There is a well-established connection between the den-sity of an urban environment, and the need to travel within it [Wheeler:1998]. Good quality of itineraries is one of the necessary conditions for avoiding stagnation and collapse of a city.
Studies of urban transportation networks have a long history. In his famous paper on the seven bridges of Königsberg published in 1736, L. Euler had proven the first theorem of graph theory [Biggs:1986 et al]. In Euler's solution, each urban landuse mass is considered as a node of a planar graph, and the bridges connecting them are the edges. Euler had found that a route travelling along each edge in the planar graph representation of the ancient Königsberg did not exists. In the primary graph representation of urban transport networks originated from the work of Euler, the relationships between the different components of urban environments are often measured along streets and routes considered as edges, while the traffic end points and street junctions are treated as nodes. In the last century, primary city graphs have been used extensively in many studies devoted to the improving of transportation routes, the optimization of power grids, and the surveys of human mobility patterns.
Another graph representation of urban transport networks is based on the ideas of traffic engineering and queueing theory invented by A.K. Erlang (see [Brockmeyer:1948 et al]). It arises naturally when we are interested in how much time a pedestrian or a vehicle would spend while travelling through a particular place in a city. In such a secondary graph representation, any space of motion is considered as a service station of a queuing network characterized by some time of service, and the relations between streets, squares, and roundabouts are traced through their junctions. Travellers arriving to a place are either moving through it immediately or queuing until the space becomes available. Once the place is passed through, the traveller is routed to its next station, which is chosen according to a probability distribution among all other open spaces linked to the given one in the urban environment.
In general, the secondary graph representations of urban environments are not planar. Moreover, they are essentially similar to those of "dual information representation" of a city map introduced by [Rosvall:2005 et al] and to the "dual graphs" extensively investigated within the concept of space syntax, a theory developed in the late 1970s, that seeks to reveal the mutual ef-fects of complex spatial urban networks on society and vice versa, [Hillier:1984et al, Hillier:1999.
In space syntax theory, built environments are treated as systems of spaces of vision subjected to a configuration analysis. Being irrelevant to the physical distances, dual graphs representing the urban environments are removed from the physical space. Spatial perception shapes peoples understanding of how a place is organized and eventually determines the pattern of local movement, [Hillier:1999]. The aim of the space syntax study is to estimate the relative proximity between different locations and to associate these distances to the densities of human activity along the links connecting them, [Hansen:1959, Wilson:1970, Batty:2004. The surprising accuracy of predictions of human behaviour in cities based on the purely topological analysis of different urban street layouts within the space syntax approach attracts meticulous attention [Penn:2001]. Space syntax proves its usefulness for the planning and redevelopment of certain city districts around the world, the designing of commercial centres, museums, railway stations, and airports where easy wayfinding is a significant issue.
The decomposition of urban spatial networks into the complete sets of intersecting open spaces can be based on a number of different principles. In [Jiang:2004 et al], while identifying a street over a plurality of routes on a city map, the named-street approach has been used, in which two different arcs of the primary city network were assigned to the same identification number (ID) provided they share the same street name. The main problem of the approach is that the meaning of a street name could vary from one district or quarter to another even within the same city. For instance, some streets in Manhattan do not meet the continuity principle rather playing the role of local geographical coordinates.
In [Porta:2006 et al], an intersection continuity principle (ICN) has been used: two edges forming the largest convex angle in a junction on the city map are assigned the highest continuity and therefore were coupled together, acquiring the same street identification number (ID). The main problem with the ICN principle is that the streets crossing under convex angles would artificially exchange their identifiers, which is not crucial for the study of the probability degree statistics [Porta:2006 et al], but makes it difficult to interpret the results if the dynamical modularity of the city is detected [Volchenkov:2007a et al]. It is also important to mention that the number of street IDs identified within the ICN principle usually exceeds substantially the actual number of street names in a city. In [Cardillo:2006, the probability degree statistics and some centrality measures in different world cities have been investigated for a number of one square mile representative samples. However, the decision on which a square mile would provide an adequate representation of a city is always questionable.
In [Figueiredo:2005 et al], the approach of [Cardillo:2006 has been improved in the sense that two intersecting lines of vision were aggregated into the same node of the dual graph representation if and only if the angle between the linear continuation of the first line and the second line was less than or equal to a predefined threshold. If more than one continuation was available, the line forming the smaller angle was chosen.
In our paper, we take a "named-streets"-oriented point of view on the decomposition of urban spatial networks into the complete sets of intersecting open spaces following our previous works [Volchenkov:2007aet al, Volchenkov:2007b. Being interested in the statistics of random walks defined on spatial networks of urban patterns, we assign an individual street ID code to each continuous segment of a street. The secondary graph is then constructed by mapping all edges of the primary graph shared the same street ID into nodes and all intersections among each pair of edges of the primary graph into the edges of the secondary graph connecting the corresponding nodes.

The scope of the study and results
In the present paper, we explore the secondary graph representations of different compact urban patterns (the Venetian channel network, the city of Paris, enclosed by the Peripheral Boulevard, and the almost regular street grid in Manhattan) by means or random walks.
In the forthcoming section (Sec. 3) we discuss the connectivity statistics of secondary graphs representing urban environments. In general, compact urban patterns have been developed under the deficits of physical space and therefore bear the multiple finger-prints of the physical landscapes being scale dependent in general. However, the large urban patterns which have not been spatially restricted during their development could constitute a highly heterogeneous scalable spatial networks as we demonstrate for the spatial network of the city of Paris bounded by the Peripheral Boulevard.
In the Sec. 4, we explain how random walks can be used in order to explore complex networks.
In Subsec. 4.1, we demonstrate that the transition operator of a random walk appears naturally as the representation of the group of graph automorphisms in a class of stochastic matrices. Random walks provide us with an effective tool for the detailed structural analysis of connected undirected graphs exposing their symmetries. It is well known that while being defined on an undirected graph, random walks determine a unique stationary probability distribution for every node [Lovasz:1993]. In Sec. 4.2, we show that each node of a connected undirected graph can be characterized with respect to random walks by the expected recurrence time and the expected first passage time. The expected recurrence time is simply the inverse of the stationary probability distribution of random walks for the given node and is therefore the local property of the node. The expected first passage time figures out a global relation between the node and other nodes of the given graph accounting for all possible random paths toward the node accordingly to their respective probabilities.
In Sec. 4.3, we show that for any undirected graph, it is possible to define a linear self-adjoint operator and then use its nice spectral properties in order to extract the information about the graph structure. In particular, we demonstrate that the complete set of orthonormal eigenvectors of the symmetric transition operator can be used in order to introduce the structure of Euclidean space on the graph.
In Sec. 4.4, we show that any node of the graph can be represented as a vector in the (N − 1)-dimensional vector space and that Euclidean distances and angles between nodes have clear probabilistic interpretations. In particular, the square of the norm of the vector representing a node of the graph equals to the expected first passage time to it by random walkers. We can conclude that random walks embed connected undirected graphs into (N − 1)-dimensional Euclidean space.
The main result of our paper is explained in Sec. 5, where we have shown that the expected recurrence time scale apparently linear with the expected first passage times in compact urban environments we have studied. A similar strong positive relation between the local property of a place and its global properties with respect to other places in the dual graph of a city was known for a long time in the framework of spaces syntax theory [Hillier:1999]. Our approach based on investigation of complex networks by means of random walks allows us to extend the notion of intelligibility far beyond space syntax onto the entire domains of complex networks and the general theory of graphs.

Connectivity statistics in secondary graphs representing urban environments
The degree of a node representing a place in the secondary graph representation of an urban environment is the number of locations directly adjacent to the given one in the city. In space syntax theory, the degree of a node (i.e. connectivity) is considered as a local characteristic quantifying how well the space is connected to others in the urban pattern, [Klarqvist:1993].
The probability degree distribution, suggests that a node selected uniformly at random has a certain degree k with the probability P (k). The probability degree distribution is an important concept characterizing the topology of complex networks. It originates from the early studies of random graphs by Erdös and Rényi, [Erdos:1959 et al] It has been reported earlier by [Jiang:2004et al, Volchenkov:2007a et al] that the secondary graphs representing the urban environments under the street-name identification principle exhibit the small-world property [Newman:2001 et al], but the scale-free probability degree distributions pertinent to the scale-free graphs can hardly be recognized. In general, compact city patterns do not provide us with sufficient data to conclude on the universality of degree statistics.
To give an example, we display in Fig. 1 the log-log plot of the numbers of Venetian channels vs. the numbers of their junctions k. The solid line indicates the cumulative empirical probability degree distribution, NP(k) = N k ′ =k N(k ′ )/N, where N = 96 is the total number of Venetian channels (including those in the Giudecca island), and N(k ′ ) is the number of channels crossing precisely k ′ other channels. It is remarkable that the empirical probability de- gree distributions observed for the secondary graphs are usually broad indicating that the itineraries can cross different numbers of other routes. Nevertheless, the distributions usually have a clearly recognizable maximum corresponding to the most probable number of junctions an average transport route has in the city. The distributions usually have a long right tail that decays faster then any power law due to just a few routes that cross many more others than in average, [Volchenkov:2007a et al]. This conclusion has been recently supported by [Figueiredo:2007 et al] where it has been suggested that in general the probability degree distributions of secondary graphs are scale-dependent.
It is important to note that in the relatively large secondary graphs which may contain many thousands of nodes a power law tail can be observed in the probability degree distributions. In Fig. 2 The probable reason for the similarity is that highly complex, self-sustaining structures, whether cells, organisms, or cities con-stitute of an immense number of units are organized in a form of self-similar hierarchical branching networks, which grow with the size of the organism [Enquist:1998 et al]. A generic social dynamic underlying the scaling phenomena observed in cities implies that an increase in productive social opportunities, both in number and quality, leads to quantifiable changes in individual behaviours of inhabitants integrating them into a complex dynamical network [Macionis:1998 et al].
The famous rank-size distribution of city sizes over many countries is known as Zipf's Law [Zipf:1949]. If we calculate the natural logarithm of the city rank in some countries and of the city size (measured in terms of its population) and then plot the resulting data in a diagram, we obtain a remarkable linear pattern with the slope of the line equals −1 (or +1, if cities have been ranked in the ascending order), [Soo:2002]. The similar centrality-rank distributions for the values of a space syntax measure quantifying the centrality of nodes in the secondary graphs of compact urban patterns have been recently reported by us in [Volchenkov:2007b et al].

Exploration of graphs by random walks
A graph naturally arises as the outcome of a categorization, when we abstract any real world system by eliminating all but one of its features and by grouping things (or places) sharing a common attribute by classes or categories. For instance, the common attribute of all open spaces in a city is that we can move through them. All open spaces found in a city are considered as physically identical, so that we can regard them as nodes of a secondary graph G(V, E), in which V is the set of all such spaces, and E is the set of all interconnections between them. For each graph G(V, E), there exists a unique, up to permutations of rows and columns, adjacency matrix A. In the special case of a finite simple graph (an undirected graph with no self-loops), the adjacency matrix is a {0, 1}-matrix such that A ij = 1 if i = j, i ∼ j, and A ij = 0 otherwise. The degree of a node i ∈ V is therefore given by For weighted undirected graphs, the adjacency matrix A is replaced by a symmetric positive affinity matrix w.

Why random walks?
The set of graph automorphisms Aut(G), the mappings of the graph to itself which preserve all of its structure, is specified by the symmetric group S N that includes all admissible permutations Π ∈ S N taking the node i ∈ V to some other node Π(i) ∈ V . The representation of S N consists of all N × N matrices Π Π , such that (Π Π ) i, Π(i) = 1, and (Π Π ) i,j = 0 if j = Π(i).
A linear transformation of the adjacency matrix for any Π ∈ S N . It is clear that the relation (4) is satisfied if the entries of the tensor F in (3) meet the following symmetry property: for any Π ∈ S N . Since the action of S N preserves the conjugate classes of index partition structures, it follows that any appropriate tensor F satisfying (5) can be expressed as a linear combination of the following tensors: {1, δ ij , δ is , δ il , δ js , δ jl , δ sl , δ ij δ js , δ js δ sl , δ sl δ li , δ li δ ij , δ ij δ sl , δ is δ jl , δ il δ js , δ ij δ il δ is } . By substituting the above tensors into (3) and taking account on the symmetries, we obtain that any arbitrary linear permutation invariant function Z (A) defined on a simple undirected graph G(V, E) must be of the following form, where k j = deg G (j), and a 1,2,3,4 being arbitrary constants. If we impose, in addition, that the linear function Z preserves the connectivity, it follows that a 1 = a 2 = 0 (since the contributions of a 1 N and a 2 are indeed incompatible with (7)) and the remaining constants should satisfy the relation 1 − a 3 = a 4 . By introducing the new parameter β ≡ a 4 > 0, we can reformulate (6) in the following form, It is important to note that (7) can be interpreted as a probability conservation relation, and therefore the linear function Z (A) can be interpreted as a stochastic process. By substituting (8) into (9), we obtain in which the operator T (β) ij is nothing else but the generalized random walk transition operator for β ∈ [0, 1]. The operator T (β) ij defines "lazy" random walks for which a random walker stays in the initial vertex with probability 1 − β, while it moves to another node randomly chosen among the nearest neighbors with probability β/k i . In particular, for β = 1, the operator T (β) ij describes the standard random walks extensively studied in classical surveys [Lovasz:1993], [Aldous et al].

Recurrence and first passage times
Simple discrete time random walks are the stochastic processes where the position of a walker at time t depends only on its position at time t − 1. The attractiveness of random walks methods in relies on the fact that the distribution of the current node of any undirected non-bipartite graph after t ≫ 1 steps tends to a well-defined stationary distribution π, which is uniform if the graph is regular.
Since the matrix T (β) ij for any β ∈ [0, 1] is a real positive stochastic matrix, it follows from the Perron-Frobenius theorem [Horn:1990 et al] that its maximal eigenvalue is simple and equals 1. The left eigenvector, π T (β) = π, associated with the maximal eigenvalue 1 is positive, and satisfies the normalization condition i∈V π i = 1 independently of β ∈ [0, 1]. The left eigenvector π is interpreted as the unique stationary distribution of this random walk. If the graph G is not bipartite, any density function σ (σ i ≥ 0, i∈V σ i = 1) asymptotically tends to the stationary distribution π under the actions of the transition operator T Let us consider a random walk starting from some node x 0 ∈ V chosen randomly among all nodes of the undirected graph G. It is clear from (11) that for long enough random walks the probability to find a random walker in a certain node i ∈ V equals π i that is proportional to the degree of node k i . The expected recurrence timem i to i ∈ V is given bym i = π −1 i , and therefore depends on the local property of the node (its degree).
The first passage timen i is the expected number of steps required for the random walker to reach the node i for the first time starting from a node randomly chosen among all nodes of the graph G. This characteristic time is calculated as an average over all random paths toward the node taken into account in accordance with their respective probabilities. Being the global characteristic of the node, n i estimates the level of accessibility to the node from the rest of the graph.
Let us now calculate the first passage time to a node by using spectral analysis of a self-adjoint transition operator.
Probably, Lagrange was the first scientist who investigated a simple dynamical process (diffusion) in order to study the properties of a graph, [Lagrange:1867]. He calculated the spectrum of the Laplace operator defined on a chain (a linear graph) of N nodes in order to study the discretization of the acoustic equations. The idea of using the spectral properties of self-adjoint operators in order to extract information about graphs is standard in spectral graph theory [Chung:1997] and in theory of random walks on graphs [Lovasz:1993], [Aldous et al]. In the following calculations, we take β = 1 in the transition operator (10). This choice allows us to compare our results directly with those known from the classical surveys on random walks [Lovasz:1993], [Aldous et al].

Euclidean embedding of graphs by random walks
The stationary distribution of random walks π defines a unique measure on the set of nodes V with respect to which the transition operator ((10) for β = 1) is self-adjoint, where T ⊤ is the adjoint operator, and π is defined as the diagonal matrix diag (π 1 , . . . , π N ). In particular, when G is a simple undirected unweighted graph. The ordered set of real eigenvectors {ψ i } N i=1 of the symmetric transition operator T forms an orthonormal basis in Hilbert space H(V ). The components of the first eigenvector ψ 1 belonging to the largest eigenvalue µ 1 = 1, describes the connectivity of nodes. The Euclidean norm in the orthogonal complement of ψ 1 , N s=2 ψ 2 s,i = 1 − π i , gives the probability that a random walker is not in i. The eigenvectors, { ψ s } N s=2 , belonging to the ordered eigenvalues 1 > µ 2 ≥ . . . µ N ≥ −1 describe the connectedness of the entire graph G. The orthonormal system of functions ψ s is useful for decomposing normalized functions defined on V .
The symmetric transition operator T projects any density σ ∈ H(V ) on the eigenvector ψ 1 related to the stationary distribution π, σ T = ψ 1 + σ ⊥ T , σ ⊥ = σ − ψ 1 , in which σ ⊥ is the vector belonging to the orthogonal complement of ψ 1 characterizing the transient process toward the stationary distribution π induced by σ.
Given two different densities σ, ρ ∈ H, it is clear that with respect to random walks they differ only on their transient parts, but not on the final stationary state π. Therefore, we can compare any two densities defined on V by means of random walks. Since all components ψ 1,i > 0, it is convenient to rescale the densities by dividing their components by ψ 1,i , such that for example σ T = 1 + σ ⊥ T . Then we define the squared Euclidean distance between any two densities with respect to random walks by the sum over all times t ≥ 0, where we have used Dirac's bra-ket notations especially convenient for working with inner products and rank-one operators in Hilbert space. In order to perform the summation over time in (17), it is convenient to use the spectral representation of T , We conclude the description of the (N − 1)-dimensional Euclidean space structure induced by random walks defined on G by mentioning that every density σ ∈ H(V ) can be characterised by the (N − 1)-dimensional vector with the norm defined by Moreover, given two densities σ, ρ ∈ H(V ), we can introduce a scalar product in the (N − 1)-dimensional Euclidean space by so that the angle between σ, ρ ∈ H(V ) can be calculated as

First passage time as the Euclidean norm of a node
Random walks embed connected undirected graphs into the Euclidean space R N −1 . This embedding can be used directly in order to calculate the first passage times to individual nodes.
Indeed, let us consider the vector e i = {0, . . . 1 i , . . . 0} that represents the node i ∈ V in the canonical basis as a density function. In accordance to (19), the vector e i has the squared norm of e i associated to random walks is It is important to note that in the theory of random walks [Lovasz:1993] the r.h.s. of (22) is known as the spectral representation of the first passage timen i to the node i ∈ V from a node randomly chosen among all nodes of the graph accordingly to the stationary distribution π. The first passage time,n i = e i 2 T , can be directly used in order to characterize the level of accessibility of the node i.
The Euclidean distance between any two nodes of the graph G calculated in the (N − 1)−dimensional Euclidean space associated to random walks, also gets a clear probabilistic interpretation as the spectral representation of the commute time, the expected number of steps required for a random walker starting at i ∈ V to visit j ∈ V and then to return back to i, [Lovasz:1993]. The commute time can be represented as a sum, is the first hitting time which quantifies the expected number of steps a random walker starting from the node i needs to reach j for the first time, [Lovasz:1993]. The scalar product (e i , e j ) T estimates the expected overlap of random paths towards the nodes i and j starting from a node randomly chosen in accordance with the stationary distribution of random walks π. The normalized expected overlap of random paths given by the cosine of an angle calculated in the (N −1)−dimensional Euclidean space associated to random walks has the structure of Pearson's coefficient of linear correlations that reveals it's natural statistical interpretation. If the cosine of an angle (21) is close to 1 (zero angles), it indicates that the expected random paths toward both nodes are mostly identical. The value of cosine is close to -1 if the walkers share the same random paths but in the opposite direction. Finally, the correlation coefficient equals 0 if the expected random paths toward the nodes do not overlap. It is important to mention that as usual the correlation between nodes does not necessary imply a direct causal relationship (an immediate connection) between them.

The first passage time and intelligibility of complex urban networks
It is intuitive that the time of recurrence to a node,m i , has to be positively related to the first passage time to it,n i : the faster a random walker hits the node for the first time, the more often he is expected to visit it in future. This intuition is supported by (22) from which it follows thatn i ∝m i provided the sum N s=2 ψ 2 s,i / (1 − µ s ) is uniformly independent of the connectivity for all nodes. The possible relation between the local and global properties of nodes is the most profound feature of a complex network. It is interesting to note that this nontrivial property of eigenvectors seems to be true for the secondary graphs representing complex urban networks: the first passage times to the nodes scale apparently linearly with their connectivity. In Fig. 3, we have sketched the 2-dimensional projection of the Euclidean space of 355 locations in Manhattan (New York) set up by random walks. Nodes of the secondary graph are shown by disks with radiuses taken proportional to the connectivity of the places. Broadway, a wide avenue in Manhattan which also runs into the Bronx and Westchester County, possesses the highest connectivity and located at the centre of the graph shown in Fig. 3. Other places are located at their Euclidean distances from Broadway calculated accordingly (23), and (21) has been used in order to compute angles between Broadway and other places.
A part-whole relationship between local and global properties of the spaces of motion is known in space syntax theory as an intelligibility property of urban pattern [Hillier:1984 et al], [Hillier:1999]. The adequate level of intelligibility is proven to be a key determinant of the human behaviour in urban environments encouraging peoples way-finding abilities, [Jiang:2004 et al]. In space syntax theory, the local property of an open space is qualified by its connectivity, while its global property is estimated by a special space syntax measure called 'integration'. In the traditional space syntax analysis [Hillier:1999], the integration of a place into urban environments is estimated by the normalized sum of all graph theoretical distances toward the place from all other places in the city. In [Jiang:2004 et al], the integration of a place has been estimated by means of the centrality of the node in the dual graph representation of the urban environment.
The first passage time to a node which we use in the present paper in order to quantify the relation of the node with other nodes in the graph has an immediate connection to neither the traditional space syntax integration measure discussed in [Hillier:1984 et al], [Hillier:1999] nor the centrality measure investigated in [Jiang:2004 et al]. However, the first passage time indicates a strong positive relation between the local and global properties of the spaces of motion in urban environments (see Fig 4) in a pretty same way as it has been demonstrated in the classical space syntax analysis.
The approach based on investigation of complex networks by means of random walks allows us to extended the notion of intelligibility far beyond the urban studies where it has been originally invented onto the entire domains of complex networks and the general theory of graphs.

Acknowledgment
The work has been supported by the Volkswagen Foundation (Germany) in the framework of the project "Network formation rules, random set graphs and generalized epidemic processes" (Contract no Az.: I/82 418).