As buildings evolve towards the envisioned smart building paradigm, smart buildings' cyber-security issues and physical security issues are mingling. Although research studies have been conducted to detect and prevent physical (or cyber) intrusions to smart building systems(SBS), it is still unknown (1) how one type of intrusion facilitates the other, and (2) how such synergic attacks compromise the security protection of whole systems. To investigate both research questions, the author proposes a graph-based testbed to simulate cyber-physical attacks on smart buildings. The testbed models both cyber and physical accesses of a smart building in an integrated graph, and simulates diverse cyber-physical attacks to assess their synergic impacts on the building and its systems. In this thesis, the author presents the testbed design and the developed prototype, SHSIM. An experiment is conducted to simulate attacks on multiple smart home designs and to demonstrate the functions and feasibility of the proposed simulation system. / Master of Science / A smart home/building is a residence containing multiple connected devices which enable remote monitoring, automation, and management of appliances and systems, such as lighting, heating, entertainment, etc. Since the early 2000s, this concept of a smart home has becomequite popular due to rapid technological improvement. However, it brings with it a lot of security issues. Typically, security issues related to smart homes can be classified into two types - (1) cybersecurity and (2) physical security. The cyberattack involves hacking into a network to gain remote access to a system. The physical attack deals with unauthorized access to spaces within a building by damaging or tampering with access control. So far the two kinds of attacks on smart homes have been studied independently. However, it is still unknown (1) how one type of attack facilitates the other, and (2) how the combination of two kinds of attacks compromises the security of the whole smart home system. Thus, to investigate both research questions, we propose a graph-based approach to simulate cyber-physical attacks on smart homes/buildings. During the process, we model the smart home layout into an integrated graph and apply various cyber-physical attacks to assess the security of the smart building. In this thesis, I present the design and implementation of our tool, SHSIM. Using SHSIM we perform various experiments to mimic attacks on multiple smart home designs. Our experiments suggest that some current smart home designs are vulnerable to cyber-physical attacks

We consider edge-colorings and flows problems in Graph Theory that are hard to solve for Class 2 graphs. Most of them are strongly related to some outstanding open conjectures, such as the Cycle Double Cover Conjecture, the Berge-Fulkerson Conjecture, the Petersen Coloring Conjecture and the Tutte's 5-flow Conjecture. We obtain some new restrictions on the structure of a possible minimum counterexample to the former two conjectures. We prove that the Petersen graph is, in a specific sense, the only graph that could appear in the Petersen Coloring Conjecture, and we provide evidence that led to propose an analogous of the Tutte's 5-flow conjecture in higher dimensions. We prove a characterization result and a sufficient condition for general graphs in relation to another edge-coloring problem, which is the determination of the palette index of a graph.

The problem considered here is one of finding the minimal Hamiltonian chain of a graph. A single chain must traverse all 𝑛 vertices of a graph with the minimal distance. The proposed procedure reduces a large problem into several smaller problems and uses a branch and bound algorithm to find the minimal Hamiltonian chain of each partitioned subproblem. The graph is decomposed and partitioned into subproblems with the use of necessary conditions for the existence of a Hamiltonian chain. This process is only applicable to graphs with relatively few incident edges per vertex. The branch and bound algorithm makes use of concepts developed by Nicos Christofides. Hamiltonian chains are derived by using minimal spanning trees. / Master of Science

Microgrid deployment in electric grids improves reliability, efficiency, and quality, as well as the overall sustainability and resiliency of the grid. Specifically, microgrids alleviate the effects of power outages. However, microgrid implementations impose additional challenges on power systems. Microgrid protection is one of the technical challenges implicit in the deployment of microgrids. These challenges occur as a result of the unique properties of microgrid networks in comparison to traditional electrical networks. Differential protection is a fast, selective, and sensitive technique. Additionally, it offers a viable solution to microgrid protection concerns. The differential zone protection scheme is a cost-effective variant of differential protection. To implement a differential zone protection scheme, the network must be split into different protection zones. The reliability of this protection scheme is dependent upon the number of protective zones developed. This thesis proposes a new differential zone protection scheme using a graph partitioning algorithm. A graph partitioning algorithm is used to partition the microgrid into multiple protective zones. The IEEE 13-node microgrid is used to demonstrate the proposed protection scheme. The protection scheme is validated with MATLAB Simulink, and its impact is simulated with DIgSILENT PowerFactory software. Additionally, a comprehensive comparison was made to a comparable differential zone protection scheme. / Master of Science / A microgrid is a group of connected distributed energy resources (DERs) with the loads to be served that acts as a local electrical network. In electric grids, microgrid implementation enhances grid reliability, efficiency, and quality, as well as the system's overall sustainability and resiliency. Microgrids mitigate the consequences of power disruptions. Microgrid solutions, on the other hand, bring extra obstacles to power systems. One of the technological issues inherent in the implementation of microgrids is microgrid protection. These difficulties arise as a result of microgrid networks' distinct characteristics as compared to standard electrical networks. Differential protection is a technique that is fast, selective, and sensitive. It also provides a feasible solution to microgrid protection problems. This protection scheme, on the other hand, is more expensive than others. The differential zone protection scheme is a cost-effective variation of differential protection that lowers protection scheme expenses while improving system reliability. The network must be divided into different protection zones in order to deploy a differential zone protection scheme. The number of protective zones generated determines the reliability of this protection method. Using a network partitioning technique, this thesis presents a new differential zone protection scheme. The microgrid is divided into various protection zones using a graph partitioning algorithm. The proposed protection scheme is demonstrated using the IEEE 13-node microgrid. MATLAB Simulink is used to validate the protection scheme, while DIgSILENT PowerFactory is used to simulate its impact. A comparison of a similar differential zone protection scheme was also done.

The WWW (World Wide Web) is a great place to share information - information can be shared across the entire world. By studying the characteristics of the WWW, we can make this information easier to find and access. Information on the web is accessed by use of web crawlers, like the search engine Google. A user types in what he/she is searching for and search results are displayed, where the user can click on a result and be taken to the corresponding website. In order for the search engine to come up with these results, algorithms must be created to search through the web and find websites relevant to the user's query. These algorithms must be quick, since web users often want information right away. They also must be accurate; A user does not want to have to weed through search results for what he/she wants; the user may get frustrated or lose interest. To create algorithms that are quick and that display accurate results, certain characteristics of the WWW must be discovered and considered. The web must be searched and the pages and hyperlinks must be stored to perform these algorithms and to discover these characteristics. The intention of this thesis is to present a library of functions in C++ for building and manipulating large graphs. These functions can be used to discover properties of graphs like degree distribution and diameter, which can be useful when studying graphs and subgraphs of the WWW.

Resting-state functional MRI(rs-fMRI) represents a powerful means to assess brain functional connectivity in healthy subjects and in neuropsychiatric patients. Aberrant functional connectivity has been observed in subjects affected by Alcohol Use Disorders (AUD) and other forms of substance dependence, a major health issue worldwide with limited treatment options. Despite intense investigation, the specific neuronal substrates involved and the functional implications of aberrant connectivity in these patients remain unknown. Moreover, it is unclear whether treatment can reverse these alterations, and normalize functional connectivity. Several methodological and conceptual questions in the analysis of functional connectivity are still open, and contribute to this uncertainty. Functional connectivity is defined in terms of correlated MR-signal fluctuations, and in-scanner patient motion and other nuisance signals can introduce spurious correlations, thus representing substantial confounding factors. At a more general level, understanding the effects of complex conditions, like AUD, on brain connectivity and their functional implications requires a deep comprehension of the brain organizational principles at multiple scales, a tremendous challenge that is at the heart of modern neuroscience. In this PhD dissertation I address some of the outstanding questions in the analysis and interpretation of aberrant functional connectivity in AUD. To this end, I have embraced the formalism of graph-theory, a powerful framework to assess the effects of alcohol abuse on the local and global topological organization of resting state connectivity. On the methodological side, I have investigated the effects of subject’s motion on the structure of resting state networks, and compared efficacy of different approaches to remove motion-related confounds. Moreover, I demonstrate the importance of network sparsification to remove spurious connections from the graph while maximizing the structural information that can be extracted from the system. Leveraging these methodological developments, I have evaluated functional alterations in different samples of AUD patients. In two independent studies, I demonstrated specific alterations in the topological organization of the insular cortex and subcortical basal structures in recently detoxified alcoholics. Interestingly, protracted abstinence appears to partially normalize functional connectivity, thus suggesting that alcohol-induced alterations in connectivity may be amenable to treatment. Based on these findings, I have studied the effects on brain functional networks of a putative novel treatment based on deep Transcranial Magnetic Stimulation (TMS). Specifically, I analyzed resting state connectivity in AUD patients subjected to repetitive TMS of the bilateral insula and of the anterior cingulate cortex (ACC), and demonstrated treatment-induced changes that may underlie the efficacy of this potential treatment in surrogate clinical read-outs.

The closed neighbourhood of a vertex in a graph is the vertex together with the set of adjacent vertices. A di®erentiating-dominating set, or identifying code, is a collection of vertices whose intersection with the closed neighbour- hoods of each vertex is distinct and nonempty. A di®erentiating-dominating set in a graph serves to uniquely identify all the vertices in the graph. Chapter 1 begins with the necessary de¯nitions and background results and provides motivation for the following chapters. Chapter 1 includes a summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de- ¯nes co-distinguishable graphs and determines bounds on the number of edges in graphs which are distinguishable and co-distinguishable while Chap- ter 3 describes the maximum number of vertices needed in order to identify vertices in a graph, and includes some Nordhaus-Gaddum type results for the sum and product of the di®erentiating-domination number of a graph and its complement. Chapter 4 explores criticality, in which any minor modi¯cation in the edge or vertex set of a graph causes the di®erentiating-domination number to change. Chapter 5 extends the identi¯cation parameters to allow for orientations of the graphs in question and considers the question of when adding orientation helps reduce the value of the identi¯cation parameter. We conclude with a survey of complexity results in Chapter 6 and a collection of interesting new research directions in Chapter 7. / Mathematical Sciences / PhD (Mathematics)

Networked systems have attracted great interests from the control society during the last decade. Several issues rising from the recent research are addressed in this dissertation. Connectedness is one of the important conditions that enable distributed coordination in a networked system. Nonetheless, it has been assumed in most implementations, especially in continuous-time applications, until recently. A nonlinear weighting strategy is proposed in this dissertation to solve the connectedness preserving problem. Both rendezvous and formation problem are addressed in the context of homogeneous network. Controllability of heterogeneous networks is another issue which has been long omitted. This dissertation contributes a graph theoretical interpretation of controllability. Distributed sensor networks make up another important class of networked systems. A novel estimation strategy is proposed in this dissertation. The observability problem is raised in the context of our proposed distributed estimation strategy, and a graph theoretical interpretation is derived as well. The contributions of this dissertation are as follows: It solves the connectedness preserving problem for networked systems. Based on that, a formation process is proposed. For heterogeneous networks, the leader-follower structure is studied and sufficient and necessary conditions are presented for the system to be controllable. A novel estimation strategy is proposed for distributed sensor networks, which could improve the performance. The observability problem is studied for this estimation strategy and a necessary condition is obtained. This work is among the first ones that provide graph theoretical interpretations of the controllability and observability issues.

Military analysis is becoming more reliant on constructive simulations for campaign modeling. Requirements for force-level capabilities, distributed command and control architectures, network centric operations, and increased levels of systems and operational integration are straining the analysis tools of choice. The models constructed are becoming more complex, both in terms of their composition and their behavior. They are complex in their composition because they are constituted from a large number of entities that interact nonlinearly through non-trivial networks and in their behavior because they display emergent characteristics. The modeling and simulation paradigm of choice for analyzing these systems of systems has been agent-based modeling and simulation. This construct is the most capable in terms of the characteristics of complex systems that it can capture, but it is the most demanding to construct, execute, verify and validate. This thesis is focused around two objectives. The first is to study the possibility of being able to compare two or more large-scale system architectures' capabilities without resorting to full-scale agent-based modeling and simulation. The second objective is to support the quantitative identification of the critical systems that compose the large-scale system architecture. The second objective will be crucial in the cases where a constructive simulation is the only option to capture the required behaviors of the complex system being studied. The enablers for this thesis are network modeling, graph theory, and in particular, spectral graph theory. The first hypothesis, stemmed from the first objective, states that if the capability of an architecture can be described as a series of functional cycles through the systems that compose them, then a simple network modeling construct can be employed to compare the different architectures' capabilities. The objective led to the second hypothesis, which states that a ranking based on the spectral characteristics of the network of functional interactions indicates the most critical systems. If modeling effort is focused on these systems, then the modeler can obtain the maximum fidelity model for the minimum effort.

Depuis plusieurs années, l’aéronautique est confrontée à une mutation majeure due à l’émergence des matériaux composites. Ce changement, justifié par les excellentes propriétés mécaniques des matériaux composites et un gain de masse important, implique une révision complète des réseaux de retour de courant. Pour faciliter cette révision, la thèse propose de lier au travers de l’analyse spectrale des graphes les performances des réseaux électriques avec leur topologie. Deux objectifs couplés sont étudiés : un dimensionnement topologique visant un bon compromis masse/robustesse et une stratégie de surveillance de ces réseaux. / The principles of the electrical system design in future aircrafts have to be reconsidered due to the emergence of new composite materials. The use of these materials for the aircraft structure has indeed implied a complete revision of on-board current return path networks. To facilitate this revision, it is proposed to link through the spectral graph analysis the performances of electrical networks with their topology. The aim of this thesis is to give topological drivers that could help the aeronautical engineers during the design process and then to propose a monitoring methodology.