---- > [!theorem] Theorem. ([[in-degree distribution of node copying model is power-law]]) > The [[degree distribution|in-degree distribution]] of the [[node copying model for growing a DAG]] matches [[in-degree distribution of Price's model is a power law|that for]] [[Price's DAG growing model]] when we set the [[hyperparameter]] $a=c\left( \frac{1}{\gamma}- 1 \right)$. In particular, it asymptotically follows a [[power law]] [[power-law probability distribution|degree distribution]] $p_{q} \sim q^{-\alpha}, \ \ \alpha=2+\frac{a}{c}=1+\frac{1}{\gamma}.$ > [!note] > This does not, however, mean that the node-copying model generates [[network]]s identical to those generated by [[Price's DAG growing model|Price's model]] and preferential attachment more generally. It *does* mean that we need to be vigilant about not equating correlation with causation when discussing models of network formation— indeed, we have discovered two very different models having the exact same degree distribution. > [!proof]- Proof. ([[in-degree distribution of node copying model is power-law]]) > > First, we compute the [[probability]] that an existing node $i$ receives a new incoming edge upon the addition of a new node $\ell$ to the [[network]]. For $i$ to receive a new edge, either > 1. $i$ belongs to the bibliography of the 'template node' $j$ of $\ell$; > - See **case 1** below. > 2. A 'mutation' caused $\ell$ to point to $i$ > - See **case 2** below. > > **Case 1.** Suppose our node $i$ has [[degree|in-degree]] $q_{i}$, meaning that $q_{i}$ other nodes cite it. By model definition, the [[probability]] that a newly added node will choose one of these links as its 'template node' is uniform, i.e., is $\frac{q_{i}}{n}$. And the chance that the link from the chosen 'template node' to $i$ gets copied is $\gamma$, for a total probability of $\frac{\gamma q_{i}}{n}$ $\ell$ points to $i$ via case 1. > > **Case 2.** As $\ell$ attempts to copy the $c$ entries of the bibliography of its 'template node' $j$, it fails with probability $1-\gamma$ on each of $c$ trials. In such cases, the 'mutation' causes $\ell$ to cite $i$ with probability $\frac{1}{n}$. Thus the [[law of total probability]] that $\ell$ points to $i$ via case 2 is $\sum_{c \text{ terms}} (1-\gamma) \cdot \frac{1}{n}=\frac{(1-\gamma)c}{n}$ > > Therefore, $\ell$ points to $i$ with [[probability]] $\frac{\gamma q_{i}}{n}+ \frac{(1-\gamma)c}{n}=\frac{\gamma q_{i} + (1-\gamma)c}{n}.$ > Defining $p_{q}(n)$ to be the fraction of nodes with in-degree $q$ when the [[network]] has $n$ nodes, the [[expectation|expected]] total number of nodes with in-degree $q$ that receive a new edge is given by [^1] $np_{q}(n) \cdot \frac{\gamma q_{} + (1-\gamma)c}{n}=[\gamma q + (1-\gamma)c]p_{q}(n).$ > But now we notice that if we define a new constant $a$ by $a=c\left( \frac{1}{\gamma - 1} \right)$, then $\gamma=\frac{c}{c+a}$ and the equation above becomes $[\gamma q + (1-\gamma)c]p_{q}(n) = \frac{c(q+a)}{c+a} p_{q}(n),$ > which is exactly the same as the [[probability]] for the [[expectation|expected]] number of nodes with in-degree $q$ that receive an edge upon addition of a new node in [[Price's DAG growing model]] — see the work in [[in-degree distribution of Price's model is a power law]]. We can thus copy the remainder of that proof here (ironic) to obtain the claimed result. > ---- #### [^1]: To see this define $X$ to be a [[random variable]] denoting the number of nodes with in-degree $q$ that receive a new edge upon addition of a new node. There are For each node $i \in [n]$ define $X_{i}=\mathbb{1}_{\text{node }i \text{ has in-degree }q \text{ and received a new edge}}$; then $X=\sum_{i=1}^{n}X_{i}$ hence $\mathbb{E}[X]=\sum_{i=1}^{n}\mathbb{E}[X_{i}]= \sum_{i=1}^{n} \mathbb{P}(X_i=1)= \sum_{i=1}^{n} p_{q}(n) [\frac{\gamma q_{i} + (1-\gamma)c}{n}] $ and the result follows. (Are there any problematic assumptions regarding [[independent random variables|independence]] in this argument?) ----- #### References > [!backlink] > ```dataview TABLE rows.file.link as "Further Reading" FROM [[]] FLATTEN file.tags GROUP BY file.tags as Tag > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```