상세정보
Export to Refworks부가기능
Inhomogeneous Models for Random Graphs and Spreading Processes: Applications in Wireless Sensor Networks and Social Networks
상세 프로파일
| 자료유형 | 학위논문 |
|---|---|
| 서명/저자사항 | Inhomogeneous Models for Random Graphs and Spreading Processes: Applications in Wireless Sensor Networks and Social Networks. |
| 개인저자 | Eletreby, Rashad. |
| 단체저자명 | Carnegie Mellon University. Electrical and Computer Engineering. |
| 발행사항 | [S.l.]: Carnegie Mellon University., 2019. |
| 발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
| 형태사항 | 311 p. |
| 기본자료 저록 | Dissertations Abstracts International 81-06B. Dissertation Abstract International |
| ISBN | 9781687993496 |
| 학위논문주기 | Thesis (Ph.D.)--Carnegie Mellon University, 2019. |
| 일반주기 |
Source: Dissertations Abstracts International, Volume: 81-06, Section: B.
Advisor: Yagan, Osman. |
| 이용제한사항 | This item must not be sold to any third party vendors. |
| 요약 | Random graphs are of great interest as a modeling framework for a wide variety of real-world complex networks, such as social networks, information networks, scientific collaboration networks, and technological networks. In this thesis, we focus on two specific application areas of random graph theory, namely, i) modeling secure connectivity of large-scale wireless sensor networks utilizing random predistribution of cryptographic keys, and ii) modeling real-world social networks. Although these two areas are tied together with random graphs, they are inherently different and each one poses distinct research problems that rise naturally in the corresponding context. Hence, we will tackle each of them separately and focus on the relevant research problems in each area. In the first part of the thesis, we focus on the role of random graphs in providing a modeling framework for secure connectivity of large-scale, heterogeneous wireless sensor networks utilizing random predistribution of cryptographic keys. In this part, we propose a novel composite random graph obtained by the intersection of inhomogeneous random key graphs with Erdos-Renyi graphs as a model for a large scale wireless sensor network secured by the heterogeneous random key predistribution scheme under a uniform on-off channel model. We derive scaling conditions on the model parameters so that with high probability i) the network has no isolated nodes, ii) is connected, iii) the minimum node degree is no less than k, and iv) the network is k-connected. We then proceed by generalizing the uniform on-off channel model to a heterogeneous on-off channel model where the wireless link availability between two nodes is determined based on their respective classes. This induces a novel composite random graph model formed by the intersection of inhomogeneous random key graphs with inhomogeneous Erdos-Renyi graphs. We derive scaling conditions on the model parameters such that with high probability i) the network has no isolated nodes, and ii) is connected. We close this part by proposing inhomogeneous random K-out graphs as a novel modeling framework for secure connectivity of large-scale, heterogeneous wireless sensor networks utilizing random pairwise key predistribution schemes. We derive scaling conditions on the model parameters such that with high probability the resulting network is connected.In the second part of the thesis, we look at random graphs as models for real-world social networks. In contrast to the first part where we mainly focus on proposing novel random graph models, herein, we utilize existing random graph models of social networks to understand how infectious diseases (or, information) that entail evolutionary adaptations propagate in social contexts. In particular, we consider the propagation of inhomogeneous spreading processes, governed by the multiple-strain model, on contact networks modeled by i) random graphs with arbitrary degree distributions (generated by the configuration model) and ii) random graphs with clustering. The former graphs capture the skewed degree sequences observed in real-world social networks, yet it has a vanishing clustering coefficient in the limit of large network size. The latter model generalizes the former as it could also generate graphs with non-trivial clustering, hence, it resembles real-world social networks that are typically clustered. We start by investigating the propagation of spreading processes governed by the multiple-strain model on random graphs with arbitrary degree distributions. We propose a mathematical theory that characterizes the expected epidemic size and the epidemic threshold as functions of the structure of the underlying contact network, the properties of the spreading process, and the evolutionary pathways of the propagating object. We also present extensive simulation results on synthetic and real-world contact networks to validate our theory and reveal the significant shortcomings of the classical epidemic models that do not capture evolutionary adaptations. We then investigate the propagation of the same class of spreading processes, yet on random graphs with clustering. We propose a mathematical theory that accurately captures the probability of emergence (the probability that the spreading process would eventually reach a positive fraction of the nodes) and the epidemic threshold as functions of the structure of the underlying contact network (which takes clustering into consideration), the properties of the spreading process, and the evolutionary pathways of the propagating object. Our theoretical results are validated by a simulation study that also reveals the impact of clustering on the probability of emergence and the epidemic threshold.A common takeaway from both parts of the thesis is that homogeneous models are more resource-efficient than their inhomogeneous counterparts, despite the fact that the latter facilitate a broader modeling framework that accurately captures real-world networks and spreading processes. In particular, in the first part of the thesis, we show that in some cases, inhomogeneous random graph models require orders of magnitude more resources (e.g., number of cryptographic keys per sensor node) than their homogeneous counterparts to be connected with high probability. In addition, in the second part of the thesis, we show that inhomogeneous models for spreading processes entailing evolutionary adaptations (on random graphs with arbitrary degree distribution) could achieve (depending on the initial strain) a lower probability of emergence at a given mean degree as compared to a homogeneous spreading process without evolution. |
| 일반주제명 | Engineering. Mathematics. Computer science. |
| 언어 | 영어 |
| 바로가기 | 
: 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
