On Properties of Several Random Networks
Open AccessThis study explores the probabilistic and statistical properties of several popular random networks. We focus on (random) Apollonian networks, their sister structures k-trees, and preferential (dynamic) attachment circuits. We also study Apollonian processes, a class of Polya processes obtained via embedding Apollonian networks in continuous time. These random structures and processes originate from or are motivated by various disciplines, including geometry, biology, computer science, economics, etc.One main point in this research is to develop a series of probabilistic and combinatorial methods not only to study the properties of random networks presented in this dissertation, but also to be applicable to the analysis of other random structures. Chapter 1 is about the history and evolution of random graphs and network models. To conform with the aim and scope of the dissertation, we concentrate on the development of Apollonian networks and preferential attachment circuits. Chapter 2 gives some key techniques and theories that we frequently use in this study, such as Polya urn models and martingale structures. A particular type of triangular Polya urns appears in our networks, and we develop exact and asymptotic results for it. Chapter 3 presents several properties of Apollonian networks and their sister structures k-trees, such as the degree profile and total weight. Phase transitions of the asymptotic mean of the degree of nodes are also discussed. Similar results carry over to k-trees, with minor modification in the proof methods, done mutatis mutandis. Chapter 4 is about preferential attachment circuits. The asymptotic distribution of the number of terminal nodes is shown to follow a Gaussian law, and the exact distribution of a node with a fixed label is determined via a system of different Polya-Eggenberger urns with ``hiccups'' in between. Chapter 5 considers an equivalent view of random networks in continuous time. Properties of Apollonian processes are investigated as an example. Chapter 6 is for further development of studies of random networks and their applications to other disciplines.Portions of this research have been accepted for publication and appear in journals and refereed proceedings of conferences. The research in Section 2.1 is published in [123]. The research in Chapter 3 appears in [121]. The research in Chapter 4 is presented in [120] and is being prepared for a journal submission. The research in Chapter 5 has been submitted; see [122].
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.