📂Graph Theory

Random Graphs

Definitions

Simple Definition

A graph that is created by a nondeterministic procedure or expressed according to some probability distribution is called a Random Graph.

Complex Definition

Given a probability space $( \Omega , \mathcal{F} , P)$, let $2^{\binom{n}{2}}$ represent the collection of all labeled graphs with $n$ vertices, known as a graph family.

A function $\mathbb{G} : \Omega \to 2^{\binom{n}{2}}$, which is $\mathcal{F}$-measurable, is called a Random Graph. In other words, $\mathbb{G}$ satisfies $\mathbb{G}^{-1} \left( B \right) \in \mathcal{F}$ for all Borel sets $B \in 2^{\binom{n}{2}}$ of (graphs).

Description

As network theory becomes increasingly applied across various fields in the 21st century, the discussion about Random Networks has also intensified. Like how a random variable in statistics signifies data, random networks in applied mathematics will signify the structure of some data we now hold, whether we like it or not.

For example, if a department views each student as a node and the SNS following status as links to create a network, it becomes a good example of a random network. While the rules for connecting nodes are clear, the actual form of the network cannot be accurately known until investigated (sampled). There would be a typical structure, but a different network would result each time the department is changed due to randomness.

However, this explanation is too naive for mathematical thinking. In the complex definition, random graphs are defined in probability theory using measure theory in exactly the same way as random variables are defined. After all, a Random Variable is a function that maps an action or experiment $\omega \in \Omega$ in reality to a Variable, and a Random Graph maps it to a Graph.

Writing it by hand makes it easier to understand. If there’s a specific graph $G_{0}$, and the probability that a randomly made graph will be $G_{0}$ is $3/4$, then it can be written as follows. $$P \left( \mathbb{G} = G_{0} \right) = {{ 3 } \over { 4 }}$$ In the above formula, the event is $\left\{ \mathbb{G} = G_{0} \right\} \in \mathcal{F}$. Always remember that what goes into the function of probability is always an event. Random graphs are just Random Elements in standard probability theory, with the only difference being that their codomain is a graph family.

Examples

Consider the property $\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$ that a simple graph has $n$ labeled vertices and $m$ edges.

A random graph with exactly $m$ links can be represented as $\mathbb{G}_{n, m} : \Omega \to \mathscr{G}_{n,m}$. The created graph, having $n$ nodes and $m$ links regardless of who creates it and the probability of doing so, ultimately doesn’t matter. In other words, no probability distribution has been assigned yet. The simplest probability distribution one can think of here is the uniform distribution where everyone has the same probability.

Since a simple graph must connect different nodes, choosing $2$ out of $n$ nodes can have $\binom{n}{2}$ links, and particularly choosing $m$ links to make $\displaystyle \left| \mathscr{G}_{n,m} \right| = \binom{\binom{n}{2}}{m}$. Hence, for all $G \in \mathscr{G}_{n,m}$, $$P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1}$$ This means that all graphs with $n$ nodes and $m$ links have an equal chance of being selected. Such a random graph $\mathbb{G}_{n, m}$ with this probability distribution is the famous Erdős–Rényi model.