Large-scale behavior of the partial duplication random graph
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2014
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911936664305664 |
|---|---|
| author | Hermann, Felix Pfaffelhuber, Peter |
| author_facet | Hermann, Felix Pfaffelhuber, Peter |
| contents | The following random graph model was introduced for the evolution of protein-protein interaction networks: Let $\mathcal G = (G_n)_{n=n_0, n_0+1,...}$ be a sequence of random graphs, where $G_n = (V_n, E_n)$ is a graph with $|V_n|=n$ vertices, $n=n_0,n_0+1,...$ In state $G_n = (V_n, E_n)$, a vertex $v\in V_n$ is chosen from $V_n$ uniformly at random and is partially duplicated. Upon such an event, a new vertex $v'\notin V_n$ is created and every edge $\{v,w\} \in E_n$ is copied with probability~$p$, i.e.\ $E_{n+1}$ has an edge $\{v',w\}$ with probability~$p$, independently of all other edges. Within this graph, we study several aspects for large~$n$. (i) The frequency of isolated vertices converges to~1 if $p\leq p^* \approx 0.567143$, the unique solution of $pe^p=1$. (ii) The number $C_k$ of $k$-cliques behaves like $n^{kp^{k-1}}$ in the sense that $n^{-kp^{k-1}}C_k$ converges against a non-trivial limit, if the starting graph has at least one $k$-clique. In particular, the average degree of a vertex (which equals the number of edges -- or 2-cliques -- divided by the size of the graph) converges to $0$ iff $p<0.5$ and we obtain that the transitivity ratio of the random graph is of the order $n^{-2p(1-p)}$. (iii) The evolution of the degrees of the vertices in the initial graph can be described explicitly. Here, we obtain the full distribution as well as convergence results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1408_0904 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | Large-scale behavior of the partial duplication random graph Hermann, Felix Pfaffelhuber, Peter Probability The following random graph model was introduced for the evolution of protein-protein interaction networks: Let $\mathcal G = (G_n)_{n=n_0, n_0+1,...}$ be a sequence of random graphs, where $G_n = (V_n, E_n)$ is a graph with $|V_n|=n$ vertices, $n=n_0,n_0+1,...$ In state $G_n = (V_n, E_n)$, a vertex $v\in V_n$ is chosen from $V_n$ uniformly at random and is partially duplicated. Upon such an event, a new vertex $v'\notin V_n$ is created and every edge $\{v,w\} \in E_n$ is copied with probability~$p$, i.e.\ $E_{n+1}$ has an edge $\{v',w\}$ with probability~$p$, independently of all other edges. Within this graph, we study several aspects for large~$n$. (i) The frequency of isolated vertices converges to~1 if $p\leq p^* \approx 0.567143$, the unique solution of $pe^p=1$. (ii) The number $C_k$ of $k$-cliques behaves like $n^{kp^{k-1}}$ in the sense that $n^{-kp^{k-1}}C_k$ converges against a non-trivial limit, if the starting graph has at least one $k$-clique. In particular, the average degree of a vertex (which equals the number of edges -- or 2-cliques -- divided by the size of the graph) converges to $0$ iff $p<0.5$ and we obtain that the transitivity ratio of the random graph is of the order $n^{-2p(1-p)}$. (iii) The evolution of the degrees of the vertices in the initial graph can be described explicitly. Here, we obtain the full distribution as well as convergence results. |
| title | Large-scale behavior of the partial duplication random graph |
| topic | Probability |
| url | https://arxiv.org/abs/1408.0904 |