Mathematical Analysis Of Urban Spatial Networks

Contents
1 Complex Networks of Urban Environments . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Paradigm of a City . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Cities and Humans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Facing the Challenges of Urbanization . . . . . . . . . . . . . . . . . . 6
1.1.3 The Dramatis Personæ. How Should a City Look? . . . . . . . . 9
1.1.4 Cities Size Distribution and Zipf’s Law . . . . . . . . . . . . . . . . . . 15
1.1.5 European Cities: Between Past and Future . . . . . . . . . . . . . . . 17
1.2 Maps of Space and Urban Environments . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.1 Object-Based Representations of Urban Environments.
Primary Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2.2 Cognitive Maps of Space in the Brain Network . . . . . . . . . . . 19
1.2.3 Space-Based Representations of Urban
Environments. Least Line Graphs . . . . . . . . . . . . . . . . . . . . . . . 22
1.2.4 Time-based Representations of Urban Environments . . . . . . . 24
1.2.5 How Did We Map Urban Environments? . . . . . . . . . . . . . . . . 26
1.3 Structure of City Spatial Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.3.1 Matrix Representation of a Graph . . . . . . . . . . . . . . . . . . . . . . 29
1.3.2 Shortest Paths in a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.3.3 Degree Statistics of Urban Spatial Networks . . . . . . . . . . . . . . 32
1.3.4 Integration Statistics of Urban Spatial Networks . . . . . . . . . . 35
1.3.5 Scaling and Universality: Between Zipf and Matthew.
Morphological Definition of a City . . . . . . . . . . . . . . . . . . . . . 37
1.3.6 Cameo Principle of Scale-Free Urban Developments . . . . . . 40
1.3.7 Trade-Off Models of Urban Sprawl Creation . . . . . . . . . . . . . 42
1.4 Comparative Study of Cities as Complex Networks . . . . . . . . . . . . . . 46
1.4.1 Urban Structure Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.4.2 Cumulative Urban Structure Matrix . . . . . . . . . . . . . . . . . . . . . 49
1.4.3 Structural Distance Between Cities . . . . . . . . . . . . . . . . . . . . . 52
1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2 Wayfinding and Affine Representations of Urban Environments . . . . . 55
2.1 From Mental Perspectives to the Affine Representation of Space . . . 56
2.2 Undirected Graphs and Linear Operators Defined on Them . . . . . . . . 58
2.2.1 Automorphisms and Linear Functions
of the Adjacency Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.2.2 Measures and Dirichlet Forms . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.3 Random Walks Defined on Undirected Graphs . . . . . . . . . . . . . . . . . . 62
2.3.1 Graphs as Discrete time Dynamical Systems . . . . . . . . . . . . . 63
2.3.2 Transition Probabilities and Generating Functions . . . . . . . . . 63
2.3.3 Stationary Distribution of Random Walks . . . . . . . . . . . . . . . . 64
2.3.4 Continuous Time Markov Jump Process . . . . . . . . . . . . . . . . . 66
2.4 Study of City Spatial Graphs by Random Walks . . . . . . . . . . . . . . . . . 66
2.4.1 Alice and Bob Exploring Cities . . . . . . . . . . . . . . . . . . . . . . . . 67
2.4.2 Mixing Rates in Urban Sprawl and Hell’s Kitchens . . . . . . . . 68
2.4.3 Recurrence Time to a Place in the City . . . . . . . . . . . . . . . . . . 70
2.4.4 What does the Physical Dimension of Urban Space Equal? . 72
2.5 First-Passage Times: How Random Walks Embed Graphs into
Euclidean Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.5.1 Probabilistic Projective Geometry . . . . . . . . . . . . . . . . . . . . . . 74
2.5.2 Reduction to Euclidean Metric Geometry . . . . . . . . . . . . . . . 76
2.5.3 Expected Numbers of Steps are Euclidean Distances . . . . . . 78
2.5.4 Probabilistic Topological Space . . . . . . . . . . . . . . . . . . . . . . . . 80
2.5.5 Euclidean Embedding of the Petersen Graph . . . . . . . . . . . . . 80
2.6 Case study: Affine Representations of Urban Space . . . . . . . . . . . . . . 83
2.6.1 Ghetto of Venice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.6.2 Spotting Functional Spaces in the City . . . . . . . . . . . . . . . . . . 86
2.6.3 Bielefeld and the Invisible Wall of Niederwall . . . . . . . . . . . . 86
2.6.4 Access to a Target Node and the Random Target Access
Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
2.6.5 Pattern of Spatial Isolation in Manhattan . . . . . . . . . . . . . . . . . 92
2.6.6 Neubeckum: Mosque and Church in Dialog . . . . . . . . . . . . . . 98
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3 Exploring Community Structure by Diffusion Processes . . . . . . . . . . . . 101
3.1 Laplace Operators and Their Spectra . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.1.1 Random Walks and Diffusions on Weighted Graphs . . . . . . . 102
3.1.2 Diffusion Equation and its Solution . . . . . . . . . . . . . . . . . . . . . 103
3.1.3 Spectra of Special Graphs and Cities . . . . . . . . . . . . . . . . . . . . 104
3.1.4 Cheeger’s Inequalities and Spectral Gaps . . . . . . . . . . . . . . . . 109
3.1.5 Is the City an Expander Graph? . . . . . . . . . . . . . . . . . . . . . . . . 112
3.2 Component Analysis of Transport Networks . . . . . . . . . . . . . . . . . . . . 114
3.2.1 Graph Cut Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.2.2 Weakly Connected Graph Components . . . . . . . . . . . . . . . . . . 115
3.2.3 Graph Partitioning Objectives as Trace Optimization
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.3 Principal Component Analysis of Venetian Canals . . . . . . . . . . . . . . . 121
3.3.1 Sestieri of Venice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.3.2 A Time Scale Argument for the Number of Essential
Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.3.3 Low-Dimensional Representations of Transport Networks
by Principal Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.3.4 Dynamical Segmentation of Venetian Canals . . . . . . . . . . . . . 127
3.4 Thermodynamical Formalism for Urban Area Networks . . . . . . . . . . 129
3.4.1 In Search of Lost Time: Is there an Alternative for Zoning? . 129
3.4.2 Internal Energy of Urban Space . . . . . . . . . . . . . . . . . . . . . . . . 131
3.4.3 Entropy of Urban Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
3.4.4 Pressure in Urban Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4 Spectral Analysis of Directed Graphs and Interacting Networks . . . . . 137
4.1 The Spectral Approach For Directed Graphs . . . . . . . . . . . . . . . . . . . . 138
4.2 Random Walks on Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.2.1 A Time–Forward Random Walk . . . . . . . . . . . . . . . . . . . . . . . . 138
4.2.2 Backwards Time Random Walks . . . . . . . . . . . . . . . . . . . . . . . 139
4.2.3 Stationary Distributions on Directed Graphs . . . . . . . . . . . . . . 140
4.3 Laplace Operator Defined on the Aperiodic Strongly Connected
Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.4 Bi-Orthogonal Decomposition of Random Walks Defined
on Strongly Connected Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . 142
4.4.1 Dynamically Conjugated Operators of Random Walks . . . . . 142
4.4.2 Measures Associated with Random Walks . . . . . . . . . . . . . . . 143
4.4.3 Biorthogonal Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.5 Spectral Analysis of Self-Adjoint Operators Defined on Directed
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.6 Self-Adjoint Operators for Interacting Networks . . . . . . . . . . . . . . . . . 148
4.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
5 Urban Area Networks and Beyond . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.1 Miracle of Complex Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.2 Urban Sprawl – a European Challenge . . . . . . . . . . . . . . . . . . . . . . . . . 152
5.3 Ranking Web Pages, Web Sites, and Documents . . . . . . . . . . . . . . . . . 155
5.4 Image Processing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Bibligraphy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

Another Social Networks Books
Download