In this chapter, cities are conceptualized as high-dimensional complex networks with complicated interdependencies and interactions. We can represent a network as a graph to investigate its dynamics and complexity. Relative changes of cities can be deconstructed as changes occasioned by the growth/decline of their nodes and links. Through percolation theory,we can study changes in connectivity in cities by modeling various types of percolations on network nodes and links.Network dynamics can be studied from the perspectives of the dynamics of the networks themselves and the dynamics of interactions on networks. Considering uncertainty involved, we can model a city as a random graph which is a set of graphs furnished with a probability measure that depends on properties such as distance between vertices in some metric space.Parallel to the percolation of an adjacency graph, we can study the dynamics of a random graph through weighted percolation in which nodes and/or links are removed with heterogeneous weights. A random graph can be represented as a random matrix which in general is low rank and sparse. Because of the high dimensionality of the adjacency matrix, we need to recover simultaneously the low-rank and sparse components of the adjacency matrix via dimension reduction.