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]$.

  • $\begingroup$ 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? $\endgroup$
    – Neal Young
    Aug 31, 2019 at 17:48
  • $\begingroup$ 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. $\endgroup$ Sep 1, 2019 at 20:03
  • $\begingroup$ 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... $\endgroup$
    – Neal Young
    Sep 2, 2019 at 0:36
  • $\begingroup$ Exactly. If the previous graph had thirty 3-degree nodes, then the new graph should also have thirty 3-degree nodes. $\endgroup$ Sep 2, 2019 at 8:29
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Sep 2, 2019 at 15:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.