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 '19 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$ – Morten Movik Sep 1 '19 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 '19 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$ – Morten Movik Sep 2 '19 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 '19 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.