Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Doctor of Philosophy

Program

Mathematics

Supervisor

Hall, Chris

Abstract

The theory of random graphs describes the interplay between probability and graph theory: it is the study of the stochastic process by which graphs form and evolve. In 1959, Erdős and Rényi defined the foundational model of random graphs on n vertices, denoted G(n, p) ([ER84]). Subsequently, Frank and Strauss (1986) added a Markov twist to this story by describing a topological structure on random graphs that encodes dependencies between local pairs of vertices ([FS86]). The general model that describes this framework is called the exponential random graph model (ERGM).

In the past, determining when a probability distribution has strong negative dependence has proven to be difficult ([Pem00, BBL09]). The negative dependence of a probability distribution is characterized by properties of its corresponding generating polynomial ([BBL09]). This thesis bridges the theory of exponential random graphs with the geometry of their generating polynomials, namely, when and how they satisfy the stable or Lorentzian properties ([Wag09, BBL09, BH20, AGV21]). We provide necessary and sufficient conditions as well as full characterizations of the parameter space for when this model has a stable or Lorentzian generating polynomial. This is done using a well-developed dictionary between probability distributions and their corresponding multiaffine generating polynomials.

In particular, we characterize when the generating polynomial of a random graph model with a large symmetry group is irreducible. We assert that the edge parameter of the exponential random graph model does not affect stability and that the triangle and k-star parameters are necessarily related if the model is stable or Lorentzian. We also provide full Lorentzian and stable characterizations for the model on K3 and a Lorentzian characterization for specializations of the model on K4.

Summary for Lay Audience

The story of random graphs begins with the understanding that networks exist ubiquitously in the world: social networks, electric networks, and networks within the human body to name a few. These networks grow and form relationships in a somewhat unpredictable way. This gives rise to the theory of random graphs. That is, we assign a probability or likelihood that some observed network represents the actual network. The theory started in 1959 when mathematicians Erdős and Rényi defined the foundational model of random graphs. Their model relies on independent structures within the graph. Although rich in theory in its own right, we take this theory in a different direction, in that we assume there exist dependencies between different relationships. For example, in the context of social networks, this means that if Bob and Sally are both friends with Amy, then we assign a high likelihood to the event that a friendship will form between Bob and Sally at some point in the near-future. This phenomenon also exists the physical world; the spins of atoms on a piece of metal depend on the spins of atoms nearby.

We take these random graph models that demonstrate dependence and determine when they exhibit some fruitful geometric and algebraic properties. It turns out that in order to ensure these properties, we can ignore some of the parameters. For the other parameters that are relevant, we determine which specific values give rise to such properties.

These nice properties have implications for the networks. Suppose that we use one of these models to predict how a real-world network grows and evolves (which has been done in the past as in [RPKL07]). If we know the parameters that give rise to such properties, this will help us better understand the evolution of these networks which will in turn lead to more accurate predictions about their structures.

This thesis focuses on these geometric and algebraic properties and determines when they hold for a large class of random graph models.

Creative Commons License

Creative Commons Attribution 4.0 License
This work is licensed under a Creative Commons Attribution 4.0 License.

Download

Share

COinS