<p>I need to find the expected value of R in the random experiment below. 
<span class="math-container">$$ 
R = \frac{1}{K} \sum_{C \in \mathcal{H} } \ [\frac{1}{2} |V(C)| * (|V(C)| - 1) - |C|]
$$</span>
<span class="math-container">$\mathcal{H}$</span> is a partition on edges, such that each edge belongs to one and only one community C. V(C) is all the nodes touched by one or more edges in C. K is a constant. 
In other words: R is the sum of the number of node-pairs in each V(C) that does not have an edge between them belonging to C.</p>

<p>The <strong>random experiment</strong> is as follows:</p>

<p>We start out with some partition <span class="math-container">$\mathcal{H}$</span>, with edge-communities C. We then keep the nodes and the size of the edge-communities but randomly assign the edges of each community to nodes. The resulting partition will have edge-communities of the same size as <span class="math-container">$\mathcal{H}$</span> but the edges will be randomly placed so V(C) will change. </p>

<p>How can I find the expected value? I have tried to find the expected value of V(C), but I don't think it helps since <span class="math-container">$E[ |V(C)|*(|V(C)| -1)] \neq E[|V(C)|]*E[|V(C)| - 1]$</span>.</p>

CC BY-SA 4.0
2019-08-31T17:48:50.147Z
How are you randomly assigning the edges to nodes?  Each edge is independently assigned to a pair of different nodes chosen at random?  So the graph may have multi-edges?
Neal Young
CC BY-SA 4.0
2019-09-01T20:03:42.127Z
I'm also keeping the degrees of the nodes, sorry I forgot to write this. There should not be any multiedges. So I can shuffle the edges and then just assign them to nodes in any order. I'm intrested in using R - E(R) to judge the quality of a partition. Specifically when moving one edge from one edge-community to another. This is for a heuristic, so I can also use a solution that's not 100% correct, as long as it's close.
Morten Movik
CC BY-SA 4.0
2019-09-02T00:36:17.820Z
Okay, and how do you choose which node pairs will have an edge?  Do you choose a graph uniformly at random from those with the desired node degrees, and then shuffle the edges (with assigned edge communities) randomly?  It seems the answer will in any case depend highly on the given node degrees...
Neal Young
CC BY-SA 4.0
2019-09-02T08:29:23.457Z
Exactly. If the previous graph had thirty 3-degree nodes, then the new graph should also have thirty 3-degree nodes.
Morten Movik
CC BY-SA 4.0
2019-09-02T15:19:35.920Z
If you are looking for an approximation, it might be easier to use a different model, one in which, for each edge e, its community is chosen at random (independently from the other edges) so that the expected size of each community is what you want.  That might be easier to  analyze.
Neal Young
<graph-theory><randomness><st.statistics>
Expected value of a random experiment in a graph
Morten Movik
# Expected value of a random experiment in a graph

(Asked by: username_0 on 2019-08-27)

I need to find the expected value of R in the random experiment below.
$$
R = \frac{1}{K} \sum\_{C \in \mathcal{H} } \ [\frac{1}{2} |V(C)| \* (|V(C)| - 1) - |C|]
$$
$\mathcal{H}$ is a partition on edges, such that each edge belongs to one and only one community C. V(C) is all the nodes touched by one or more edges in C. K is a constant.
In other words: R is the sum of the number of node-pairs in each V(C) that does not have an edge between them belonging to C.

The **random experiment** is as follows:

We start out with some partition $\mathcal{H}$, with edge-communities C. We then keep the nodes and the size of the edge-communities but randomly assign the edges of each community to nodes. The resulting partition will have edge-communities of the same size as $\mathcal{H}$ but the edges will be randomly placed so V(C) will change.

How can I find the expected value? I have tried to find the expected value of V(C), but I don't think it helps since $E[ |V(C)|\*(|V(C)| -1)] \neq E[|V(C)|]\*E[|V(C)| - 1]$.

**Tags:** graph-theory, randomness, st.statistics
> **Comments:**
> **username_1**: How are you randomly assigning the edges to nodes?  Each edge is independently assigned to a pair of different nodes chosen at random?  So the graph may have multi-edges?  
> **username_0**: I'm also keeping the degrees of the nodes, sorry I forgot to write this. There should not be any multiedges. So I can shuffle the edges and then just assign them to nodes in any order. I'm intrested in using R - E(R) to judge the quality of a partition. Specifically when moving one edge from one edge-community to another. This is for a heuristic, so I can also use a solution that's not 100% correct, as long as it's close.  
> **username_1**: Okay, and how do you choose which node pairs will have an edge?  Do you choose a graph uniformly at random from those with the desired node degrees, and then shuffle the edges (with assigned edge communities) randomly?  It seems the answer will in any case depend highly on the given node degrees...  
> **username_0**: Exactly. If the previous graph had thirty 3-degree nodes, then the new graph should also have thirty 3-degree nodes.  
> **username_1**: If you are looking for an approximation, it might be easier to use a different model, one in which, for each edge e, its community is chosen at random (independently from the other edges) so that the expected size of each community is what you want.  That might be easier to  analyze.  

---

## 0 answers

