CS代写|PCS810 Complex Networks

Geometric branching process: Consider a Galton-Watson branching process with geometric offspring distribution with parameter $p$, i.e.,
$$
\mathbb{P}(\xi=k)=p^k(1-p)
$$
(A) Compute the probability of extinction occuring in generation $n$ (using generating functions).
(B) Give a general expression for the probability of extinction.
*(C) Derive an expression for the generating function of
$$
W=\lim _{n \rightarrow \infty} X_n /(\mathbb{E}(\xi))^n
$$
where $X_n$ is the number of individuals in generation $n$.

Chernoff bound: Consider a coin with probability $p$ of landing heads and probability $1-p$ of landing tails. Suppose the coin is flipped $n$ times, and let $X_i \sim \operatorname{Bernoulli}(p)$ be the indicator random variable that the $i^{\text {th }}$ flip lands heads.
(A) Show that the rate function $h(a)$ corresponding to a $\operatorname{Bernoulli}(p)$ random variable is
$$
h(a)=a \log \left(\frac{a}{p}\right)+(1-a) \log \left(\frac{1-a}{1-p}\right) .
$$
(B) Use a Chernoff bound to determine a value for $n$ so that the probability that more than half of the coin flips come out heads is less than 0.001 .

Subgraphs of random graphs: Fix the probability of any given link forming in an Erdos-Renyi network to be $p$ with $0<p<1$. Fix some arbitrary network $g$ on $k$ nodes. Now, consider a sequence of random networks indexed by the number of nodes $n$, as $n \rightarrow \infty$. Show that the probability that a copy of the $k$-node network $g$ is a subnetwork of the random network on the $n$ nodes goes to 1 as $n$ goes to infinity.
[Hint: Partition the $n$ nodes into as many separate groups of $k$ nodes as possible (with some leftover nodes) and consider the subnetworks that form on each of these groups. Using independence of link formation, show that the probability that none of these match the desired network goes to 0 as n grows.]

Cliques in random graphs: A $k$-clique in a graph is a subset of $k$ vertices such that any two of them are directly connected by an edge (i.e., there are $\left(\begin{array}{c}k \ 2\end{array}\right)$ edges in a $k$-clique). Cliques are important objects in many computing problems and they also have simple combinatorial properties that allows one to analyze them well. This exercise guides you towards understanding how they may appear in a random graph.

In this exercise, we always work with a sequence of Erdos-Renyi random graphs $G(n, p)$. We seek a threshold for the event that $G_n$ contains a $k$-clique. That is, we will find a function $t(n)$ such that:

• Property (i): $\lim _{n \rightarrow \infty} \mathbb{P}\left(G_n\right.$ contains a $k$-clique $)=0$ if $p(n)=o(t(n))$
• Property (ii): $\lim _{n \rightarrow \infty} \mathbb{P}\left(G_n\right.$ contains a $k$-clique $)=1$ if $p(n)=\omega(t(n))$.

(A) What can you say about cliques of size 1 and 2? Can you define a threshold function for them? Prove that your answers satisfy the definition of a threshold.

We now consider the case $k=4$. It is not as easy to directly characterize the probability of having at least one 4-clique, and we will need to use the second-moment method to prove the existence of any threshold.

Let $N_n$ be the number of 4-cliques in the graph $G(n, p)$. Since the edges of $G(n, p)$ appear randomly, $N_n$ is an $\mathbb{N}$-valued random variable. To be precise, there are $L_n=\left(\begin{array}{l}n \ 4\end{array}\right)$ number of choices of 4 elements in the $n$ veritices of $G(n, p)$, and any of these can potentially form a 4-clique provided that the associated edges happen to be present. Denote by $C_1, \ldots, C_{L_n}$ all of these possible choices of 4 elements and for a subset $C_l$, let $X_l$ be the indicator random variable that $C_l$ is a clique. That is,
$$
X_l= \begin{cases}1 & \text { if } C_l \text { is a clique } \ 0 & \text { otherwise }\end{cases}
$$
Note that $N_n=\sum_{l=1, \ldots, L_n} X_l$ as a sum of random variables.
(B) Are the variables $\left{X_l\right}_{l=1, \ldots, L_n}$ mutually independent? Are they identically distributed?
(C) What is $\mathbb{E}\left[X_l\right]$ for a given $l$ ? What is $\mathbb{E}\left[N_n\right]$ ?

(D) Use this average analysis to determine a threshold function $t(n)$ for the existence of a 4-clique.
(E) Using Markov’s inequality, prove that $t(n)$ satisfies property (i).
(F) For this value of the threshold, if we assume that $p(n)=\omega(t(n))$ then what can be said about the expectation of $N_n$ as $n \rightarrow \infty$ ? Why is this not sufficienty fo conclude that property (ii) is satisfied?

Now recall the following property of the variance of the sum of ${0,1}$-valued random variables:
$$
\operatorname{Var}\left[N_n\right] \leq \mathbb{E}\left[N_n\right]+\sum_{l \neq m} \operatorname{Cov}\left(X_l, X_m\right)
$$
where $\operatorname{Cov}(X, Y)=\mathbb{E}\left[\left(X-\mu_X\right)\left(Y-\mu_Y\right)\right]$ with $\mu_X$ and $\mu_Y$ the mean of $X$ and $Y$, respectively. Note that $\operatorname{Cov}(X, Y) \leq \mathbb{E}[X Y]$ if $X$ and $Y$ are nonnegative random variables.

(G) Show that when $C_l$ and $C_m$ are either disjoint or share a single vertex, then $X_l$ and $X_m$ are independent. What can you conclude about $\operatorname{Cov}\left(X_l, X_m\right)$ ?
(H) Assuming that $C_l$ and $C_m$ share exactly two vertices, give a bound on $\operatorname{Cov}\left(X_l, X_m\right)$. What if these subsets share exactly three vertices?
(I) Use the second-moment method to conclude that the threshold $t(n)$ satisfies property (ii).
(J) We now consider the most general case. Use an average analysis to propose a reasonable candidate for the threshold function $t(n)$ of the existence of a $k$-clique in $G(n, p)$. Prove that this threshold satisfies property (i) using Markov’s inequality. No proof of property (ii) is required.
*(K) Imagine we wish to apply the same method to determine when chordless cycles appear in a random graph. A cycle is a sequence of edges in the graph forming a path starting and ending in the same node, and is chordless if there are no edges between non-neighboring nodes (i.e., the cycle cannot be made shorter). Will a similar argument hold? Why or why not?
*3. Clustering in the configuration model: Consider a graph $g$ with $n$ nodes generated according to the configuration model with a particular degree distribution $P(d)$. Show that the overall clustering coefficient is given by
$$
C(g)=\frac{\langle d\rangle}{n}\left(\frac{\left\langle d^2\right\rangle-\langle d\rangle}{\langle d\rangle^2}\right)^2,
$$
where $\langle d\rangle$ is the expected degree under distribution $P(d)$, i.e., $\langle d\rangle=\sum_{d=1}^{\infty} d P(d)$ and similarly $\left\langle d^2\right\rangle=\sum_{d=1}^{\infty} d^2 P(d)$.