Ranjan, Gyan2013-07-262013-07-262013-05https://hdl.handle.net/11299/154184University of Minnesota Ph.D. dissertation. May 2013. Major: Computer Science. Advisor: Dr. Zhi-Li Zhang. 1 computer file (PDF); xii, 140 pages, appendices A-C.This dissertation is an attempt at understanding the structural properties of static and dynamic networks from the perspective of robustness towards multiple random failures and targeted attacks. In order to characterize the robustness of a static network, abstracted as a graph, towards random failures and targeted attacks, we transform it into a geometric object by embedding it into a Euclidean space spanned by the eigen vectors of the Moore-Penrose pseudo-inverse of the combinatorial Laplacian. This Euclidean space, endowed with a metric distance function, has several interesting properties. The nodes of the network are now transformed into discrete points in this space, each represented in terms of an n-dimensional co-ordinate (n being the number of entities), centered at the origin. We demonstrate that the position and the connectedness of an entity (node) in the network is well determined by its distance from the origin in this space. Closer a node is to the origin, more topological central it is, greater its tendency to lie in the larger sub- network when multiple edge failures lead to a breaking up of the network into disjoint components, thus greater its robustness in disruptive failure scenarios. We extend the same notion of centrality to the set of links (relationships) in the network as well. Last but not the least, the volume of the embedding, determined by the sum of squared lengths of the position vectors of all the nodes, yields a measure of robustness for the network as a whole. We call this the Kirchhoff index of the network. Once again, lower the Kirchhoff index of a network, more geometrically compact its embedding, and more difficult it is to break the network into two equal sized sub-networks; which, if possible, disrupts the greatest number of pairwise communications. The Kirchhoff index can, therefore, be used to compare the relative robustness properties of two networks with the same number of entities and relationships. Next, we broaden our perspective by studying the sub-structures of a network within the geometric framework described above. First, on the computational front, we discuss an incremental methodology for computing the pseudo-inverse in a divide-and-conquer fashion, thus offsetting the otherwise high computational costs to within manageable limits. Secondly, it takes our geometric framework to the realm of dynamic, time- evolving, networks. We then apply the geometrical and topological understanding to the case of in- terdependent networks where the structural interplay between two or more networks determine the robustness of the overall system. Here again our geometric and topologi- cal indices provide interesting and somewhat counter-intuitive insights. We demonstrate that the manner in which interdependencies are introduced between two inter-dependent networks plays a significant role in determining the robustness of the overall system. In particular, diffusing and distributing inter-dependencies among a large number of (geo- graphically dispersed) node pairs (sites of attachment) in the two constituent networks produces more robust systems. Finally, we study the case of a cellular data service network (CDSN), where a dif- ferent form of interdependence exists between the radio infrastructure (cellular towers) and the underlying IP (data) - network. One of the challenges in studying this class of networks is the absence of publicly available topology information, owing to security and privacy concerns. We thus motivate a means of inferring the topology through user geo-intent queries (e.g. location based services), thereby gaining some visibility in the inner workings of a CDSN. We observe that vast geo-physical territories in the radio layer map to relatively fewer and centralized IP network elements (such as NAS-gateway servers), thereby indicating potential of wide scale disruptions in the case of geo-physical attack scenarios. Last but not the least, we study the limitations of using cellular net- work traces to inferring human mobility patterns with an eye on urban infrastructure planning. We demonstrate that naive use of cellular traces can potentially lead to a biased view of user mobility that, in turn, may affect inferences of dynamic populations in urban areas. We demonstrate, however, that such biases can both be quantified and corrected for using an imposed sampling process, thereby obtaining better estimates.en-USCellular networksDynamic time-evolving networksKirchhoff factorMoore-Penrose pseudo-inverse of the LaplacianPreferential attachmentTopological centralityThesis or Dissertation