Set up
Let $G$ be a graph with $n$ vertex: $\{ e_i \}_{i=1}^n = E$. Define, for all $i$ and $j$ from $1$ to $n$,
$e_{i,j}: E \times E \rightarrow \{0,1\}$,
the random variable which takes $1$ if the edge between $i$ and $j$ exists and $0$ otherwise.
I'm interested in calculating the expectation of $e_{i,j}$ ($\mathbb{E}(e_{i,j})$) and the independence of these variables ($Var(e_{i,j}, e_{k,l})$), knowing the "class" of the graph I'm dealing with.
For example for an Erdos-Renyi graph with probability $p$, it's trivial to show:
$\mathbb{E}(e_{i,j})=p$ and $Var(e_{i,j}, e_{k,l})=0$ for all $(i,j) \neq (k,l)$.
Questions
- Is it possible to estimate these quantities for, let's say, a scale free graph with fixed degree distribution?
- Do other classes of graphs exist, as the ER-graph, with "easy" computations?
- Even if in general the variance will be strictly positive, I have the intuition that for a large class of graphs, it can be bounded. Is there any result about that?
Example: Scale free network case
Naively I thought that, if I want to know the probability of the existence of a certain vertex, let's say $e_{i,j}$, knowing that the edge $e_i$ as $k$ connections, I should just compute:
$\mathbb{P}($ existence of $e_{i,j}\,| \, \|e_i\|=k<n) = \tfrac{k}{n}$ so that
$\mathbb{E}(e_{i,j})= \mathbb{P}($ existence of $e_{i,j}) = \sum_{l=0}^n \mathbb{P}($ existence of $e_{i,j}\,| \, \|e_i\|=l) \mathbb{P}(\| e_i \| = l) = \sum_{l=0}^n \tfrac{l}{n} \tfrac{A}{l^{\gamma}} \approx \tfrac{A}{n} \sum_{l=1}^n \tfrac{1}{l^{\gamma-1}}$, with $A>0$ normalizing constant and $\gamma$ the fixed exponent for the degree distribution.
Is it correct? How can I estimate the variance know?
A general Example: configuration model
We can take a configuration model, which includes the previous case, chosing the degree sequence to follow a power law distribution. Reading here Probability that exists at least an edge in the configuration model, it gives me an hint, saying that the probability $p_{ij}$ that exists at least an edge between two vertices $i$ and $j$ is evaluated as $p_{ij} = \frac{k_i k_j}{2m}$, where $k_i$ and $k_j$ denote the degrees of two particular vertices in the network and $2m = \sum_i k_i $.
(in particular, following the same reference notes: Let $v$ be an array of length $2m$ and let us write the index of each vertex $i$ exactly $k_i$ times in the vector $v$. Each of these entries will represent a single edge stub attached to vertex $i$. Then, we take a random permutation of the entries of $v$ and read the contents of the array in order, in pairs. For each pair that we read, we add the corresponding edge to the network.)
Is the expectation made by computing this sum: $\mathbb{E}(e_{i,j})= \sum_{i,j}^n p_{i,j} \mathbb{P}(k_i) \mathbb{P}(k_j)$ ?
How can I compute the variance?