Take a directed graph denoted by its adjacency matrix $\mathbf{A}$. It is a probabilistic graph -- the nodes of $\mathbf{A}$ might be linked, and the entries are probabilities between 0 and 1.
Say I select $N$ nodes. What is the expectation of the number of links to selected nodes, for a random node?
More concretely: say I have Sneeches on Beaches. None have stars. They might know each other, hence the probabilistic adjacency matrix. I pick $N$ and give them stars. For a random Sneech, how many starred Sneeches do I expect that she knows?
Is this possible analytically, or do I need to go and simulate?
Edit: what I'm really looking for is $E[X] = f(N)$, where $X$ is the number of links to selected nodes $S$, and $N$ is the number of selected nodes in the network.
Edit2: I suppose that I could do it analytically in the following inefficient way:
- Construct $\mathbf{S_N}\equiv$all possible $S$ vectors for a given $N$
- Take the mean of the row-wise means of $\mathbf{S_N'A}$
But the size of $\mathbf{S}$ will generally be huge.
Let $G = (V, E)$ be a graph and let $S \subseteq V$ be the given vertex set.
Denote by $p_{uv}$ the probability of having an edge between two vertices $u$ and $v$. Let $I_{uv} = 1$ if $u, v$ are neighbors, and $0$ otherwise. And let $X_v$ be a random variable corresponding to the number of neighbors in $S$ of some vertex $v$.
Using linearity of expectation, the expected value is
$$\mathbb{E}[X_v] = \mathbb{E} \left[ \sum_{u \in S} I_{uv} \right] = \sum_{u \in S}\mathbb{E} [I_{uv}] = \sum_{u \in S} p_{uv}$$
That's for a specific $v$. Now, let $X$ be the random variable for the number of neighbors of a randomly picked vertex. I assume that each vertex has an equal probability $1/n$ of being chosen, $n$ being the number of vertices in $V$.
We have
$$ \mathbb{E}[X] = \sum_{v \in V} \frac{1}{n} \mathbb{E}[X_v] = \frac{1}{n} \sum_{v \in V} \sum_{u \in S} p_{uv} $$
So in the end, you can just sum up the values in the $S$ columns of your matrix, then divide that by $n$.