Since 2008, more than half of the world population lives in cities. To cope with this rapid urbanization in a sustainable manner, transit systems all around the world are likely to grow. By studying 33 networks in the world, this thesis identifies the properties and effects of metro network designs by using a graph theory approach. After the literature review, a new methodology was introduced to translate networks into graphs; it notably accounts for various transit specificities (e.g., presence of lines). Metro networks were then characterised according to their State, Form, and Structure; where State relates to the development phase of metros; Form investigates the link between metros and the built environment; Structure examines the intrinsic properties of metros, by notably looking at their connectivity. Subsequently, the complexity and robustness of metros were studied; metros were found to possess scale-free and small-world features although showing atypical topologies; robustness emphasizes on the presence of alternative paths. Three network design indicators (coverage, directness and connectivity) were then related to ridership (annual boardings per capita), and positive relations were observed, which suggests that network design plays an important role in their success. Finally, these concepts were applied to the Toronto metro plans announced by the Toronto regional transportation authority, Metrolinx; it was found that the grid-pattern nature of the plans could hinder the success of the metro; seven possible improvements were suggested. Overall, the topology of metro networks can play a key role in their success. The concepts presented here can particularly be useful to transit planners; they should also be used along with conventional planning techniques. New transit projects could benefit greatly from an analysis of their network designs, which in turn may play a relevant role in the global endeavour for sustainability.

Simple network models that focus only on graph topology or, at best, basic interactions are often insufficient to capture all the aspects of a dynamic complex system. In this thesis, I explore those limitations, and some concrete methods of resolving them. I argue that, in order to succeed at interpreting and influencing complex systems, we need to take into account  slightly more complex parts, interactions and information flows in our models.This thesis supports that affirmation with five actual examples of applied research. Each study case takes a closer look at the dynamic of the studied problem and complements the network model with techniques from information theory, machine learning, discrete maths and/or ergodic theory. By using these techniques to study the concrete dynamics of each system, we could obtain interesting new information. Concretely, we could get better models of network walks that are used on everyday applications like journal ranking. We could also uncover asymptotic characteristics of an agent-based information propagation model which we think is the basis for things like belief propaga-tion or technology adoption on society. And finally, we could spot associations between antibiotic resistance genes in bacterial populations, a problem which is becoming more serious every day.

Doctor of Philosophy / Department of Electrical and Computer Engineering / Caterina Scoglio / The science of complex networks has significantly advanced in the last decade and has provided valuable insights into the properties of real world systems by evaluating their structure and construction. Several phenomena occurring in real technological and social systems can be studied, evaluated, quantified, and remedied with the help of network science. The electric power grid is one such real technological system that can be studied through the science of complex networks. The electric grid consists of three basic sub-systems: Generation, Transmission, and Distribution. The transmission sub-system is of particular interest in this work because its mesh-like structure offers challenging problems to complex networks researchers. Cascading dynamics of power grids is one of the problems that can be studied through complex networks. The North American Electric Reliability Corporation (NERC) defines a cascading failure as the uncontrolled successive loss of system elements triggered by an incident at any location. In this dissertation, we primarily discuss the dynamics of cascading failures in the power transmission grid, from a complex networks perspective, and propose possible solutions for mitigating their effects. We evaluate the grid dynamics for two specific scenarios, load growth and random fluctuations in the grid, to study the behavior of the grid under critical conditions. Further, we propose three mitigation strategies for reducing the damage caused by cascading failures. The first strategy is intentional islanding in the power transmission grid. The aim of this method is to intentionally split the grid into two or more separate self- sustaining components such that the initial failure is isolated and the separated components can function independently, with minimum load shedding. The second mitigation strategy involves controlled placement of distributed generation (DG) in the transmission system in order to enhance robustness of the grid. The third strategy requires the addition of a link in the transmission grid by reduction of the average spectral distance, utilizing the Ybus matrix of the grid and a novel algorithm. Through this dissertation, we aim to successfully cover the gap present in the complex networks domain, with respect to the vulnerability analysis of power grid networks.

Picture the life of a modern person in the western world: They wake up in the morning and check their social networking sites; they drive to work on roads that connect cities to each other; they make phone calls, send emails and messages to colleagues, friends, and family around the world; they use electricity flowing through power-lines; they browse the Internet, searching for information. All of these typical daily activities rely on the structure of networks. A network, in this case, is a set of nodes (people, web pages, etc) connected by edges (physical connection, collaboration, etc). The term graph is sometimes used to represent a more abstract structure - but here we use the terms graph and network interchangeably. The field of network analysis concerns studying and understanding networks in order to solve problems in the world around us. Graph models are used in conjunction with the study of real-world networks. They are used to study how well an algorithm may do on a real-world network, and for testing properties that may further produce faster algorithms. The first piece of this dissertation is an experimental study which explores features of real data, specifically power-law distributions in degrees and spectra. In addition to a comparison between features of real data to existing results in the literature, this study resulted in a hypothesis on power-law structure in spectra of real-world networks being more reliable than that in the degrees. The theoretical contributions of this dissertation are focused primarily on generating realistic networks through existing and novel graph models. The two graph models presented are called HyperKron and the Triangle Generalized Preferential Attachment model. Both of the models incorporate higher-order structure - leading to more sophisticated properties not examined in traditional models. We use the second of our models to further validate the hypothesis on power-laws in the spectra. Due to the structure of our model, we show that the power-law in the spectra is more resilient to sub-sampling. This gives some explanation for why we see power-laws more frequently in the spectra in real world data.

Agglomeration of nanoparticles occurs in a number of colloidal systems related, for example, to material processing and drug delivery. The present work is motivated by the need to improve fundamental understanding of the agglomeration and structure formation processes that occur in catalyst inks used for the fabrication of polymer electrolyte fuel cells (PEMFCs). Particle dynamics simulations are performed to investigate agglomeration under various conditions. The interaction between particles is defined using realistic physical potentials, rather than commonly used potential models, and a novel analysis of the agglomeration and structure formation process is performed using network science concepts. The simulated systems correspond to catalyst inks consisting primarily of carbon nanoparticles in solution. The effect of various conditions such as different force magnitude, shape of the force function, concentration etc. are investigated in terms of network science parameters such as average degree and shortest path. An "agglomeration timescale" and a "restructuring timescale" introduced to interpret the evolution of the agglomeration process suggest that the structure, which has a strong impact on the performance of the eventual catalyst layer, can be controlled by tuning the rate at which particles are added based on the restructuring timescale. / Graduate

Cities are composed of multiple interconnected, interdependent infrastructure networks. These networks are expected to continuously operate at near 100\% of their designed service capacities. When the operation of just one of these networks is disrupted the effects are often not contained to a single network. How these networks function and interact is critically important in increasing urban community resilience when subjected to stochastic disruptions. Despite apparent differences in the physical qualities of both infrastructure and cities this work, uses principles of complex network analysis to reveal stunning similarities in the functional topology of infrastructure networks around the globe. Network based models are used to demonstrate how failures cascade between infrastructure networks. The severity of these cascades is shown to be influenced by population, design decisions, and localized variance within the larger infrastructure networks. These results are important for all design, maintenance, retrofitting, and resilience aspects of urban communities.

abstract: Teams are increasingly indispensable to achievements in any organizations. Despite the organizations' substantial dependency on teams, fundamental knowledge about the conduct of team-enabled operations is lacking, especially at the {\it social, cognitive} and {\it information} level in relation to team performance and network dynamics. The goal of this dissertation is to create new instruments to {\it predict}, {\it optimize} and {\it explain} teams' performance in the context of composite networks (i.e., social-cognitive-information networks). Understanding the dynamic mechanisms that drive the success of high-performing teams can provide the key insights into building the best teams and hence lift the productivity and profitability of the organizations. For this purpose, novel predictive models to forecast the long-term performance of teams ({\it point prediction}) as well as the pathway to impact ({\it trajectory prediction}) have been developed. A joint predictive model by exploring the relationship between team level and individual level performances has also been proposed. For an existing team, it is often desirable to optimize its performance through expanding the team by bringing a new team member with certain expertise, or finding a new candidate to replace an existing under-performing member. I have developed graph kernel based performance optimization algorithms by considering both the structural matching and skill matching to solve the above enhancement scenarios. I have also worked towards real time team optimization by leveraging reinforcement learning techniques. With the increased complexity of the machine learning models for predicting and optimizing teams, it is critical to acquire a deeper understanding of model behavior. For this purpose, I have investigated {\em explainable prediction} -- to provide explanation behind a performance prediction and {\em explainable optimization} -- to give reasons why the model recommendations are good candidates for certain enhancement scenarios. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2018

Physical systems modeled by networks are fully dynamic in the sense that the process of adding edges and vertices never ends, and no edge or vertex is necessarily eternal. Temporal networks enable to explicitly study systems with a changing topology by capturing explicitly the temporal changes. The controllability of temporal networks is the study of driving the state of a temporal network to a target state at deadline t_f within △t = t_f - t₀ steps by stimulating key nodes called driver nodes. In this research, the author aims to understand and analyze temporal networks from the controllability perspective at the global and nodal scales. To analyze the controllability at global scale, the author provides an efficient heuristic algorithm to build driver node sets capable of fully controlling temporal networks. At the nodal scale, the author presents the concept of Complete Controllable Domain (CCD) to investigate the characteristics of Maximum Controllable Subspaces (MCSs) of a driver node. The author shows that a driver node can have an exponential number of MCSs and introduces a branch and bound algorithm to approximate the CCD of a driver node. The proposed algorithms are evaluated on real-world temporal networks induced from ant interactions in six colonies and in a set of e-mail communications of a manufacturing company. At the global scale, the author provides ways to determine the control regime in which a network operates. Through empirical analysis, the author shows that ant interaction networks operate under a distributed control regime whereas the e-mails network operates in a centralized regime. At the nodal scale, the analysis indicated that on average the number of nodes that a driver node always controls is equal to the number of driver nodes that always control a node. <br>

This thesis presents an approach to the design and management of core networks where the packet transport is the main service and the backbone should be able to respond to unforeseen changes in network parameters in order to provide smooth and reliable service for the customers. Inspired by Darwin's seminal work describing the long-term processes in life, and with the help of graph theoretic metrics, in particular the "random-walk betweenness", we assign a survival value, the network criticality, to a communication network to quantify its robustness. We show that the random-walk betweenness of a node (link) consists of the product of two terms, a global measure which is fixed for all the nodes (links) and a local graph measure which is in fact the weight of the node (link). The network criticality is defined as the global part of the betweenness of a node (link). We show that the network criticality is a monotone decreasing, and strictly convex function of the weight matrix of the network graph. We argue that any communication network can be modeled as a topology that evolves based on survivability and performance requirements. The evolution should be in the direction of decreasing the network criticality, which in turn increases the network robustness. We use network criticality as the main control parameter and we propose a network management system, AutoNet, to guide the network evolution in real time. AutoNet consists of two autonomic loops, the slow loop to control the long-term evolution of robustness throughout the whole network, and the fast loop to account for short-term performance and robustness issues. We investigate the dynamics of network criticality and we develop a convex optimization problem to minimize the network criticality. We propose a network design procedure based on the optimization problem which can be used to develop the long-term autonomic loop for AutoNet. Furthermore, we use the properties of the duality gap of the optimization problem to develop traffic engineering methods to manage the transport of packets in a network. This provides for the short-term autonomic loop of AutoNet architecture. Network criticality can also be used to rank alternative networks based on their robustness to the unpredicted changes in network conditions. This can help find the best network structure under some pre-specified constraint to deal with robustness issues.

This thesis presents an approach to the design and management of core networks where the packet transport is the main service and the backbone should be able to respond to unforeseen changes in network parameters in order to provide smooth and reliable service for the customers. Inspired by Darwin's seminal work describing the long-term processes in life, and with the help of graph theoretic metrics, in particular the "random-walk betweenness", we assign a survival value, the network criticality, to a communication network to quantify its robustness. We show that the random-walk betweenness of a node (link) consists of the product of two terms, a global measure which is fixed for all the nodes (links) and a local graph measure which is in fact the weight of the node (link). The network criticality is defined as the global part of the betweenness of a node (link). We show that the network criticality is a monotone decreasing, and strictly convex function of the weight matrix of the network graph. We argue that any communication network can be modeled as a topology that evolves based on survivability and performance requirements. The evolution should be in the direction of decreasing the network criticality, which in turn increases the network robustness. We use network criticality as the main control parameter and we propose a network management system, AutoNet, to guide the network evolution in real time. AutoNet consists of two autonomic loops, the slow loop to control the long-term evolution of robustness throughout the whole network, and the fast loop to account for short-term performance and robustness issues. We investigate the dynamics of network criticality and we develop a convex optimization problem to minimize the network criticality. We propose a network design procedure based on the optimization problem which can be used to develop the long-term autonomic loop for AutoNet. Furthermore, we use the properties of the duality gap of the optimization problem to develop traffic engineering methods to manage the transport of packets in a network. This provides for the short-term autonomic loop of AutoNet architecture. Network criticality can also be used to rank alternative networks based on their robustness to the unpredicted changes in network conditions. This can help find the best network structure under some pre-specified constraint to deal with robustness issues.