I am dealing with the following problem:
Assume $G(V,E)$ being an underlying network and $M_1$, $M_2$ sets of disjoint subsets of $V$ (e.g. if $|M_1| = k$, $M_1 = \{U_1,U_2,\dots,U_k\}$, $\forall_{i\not=j} \, U_i \cap U_j = \emptyset$).
Given a range of such $M$, I run pairwise comparisons, testing each $U_i \in M_1$ against $U_j \in M_2$. Let $G_i$ b the induced subgraph over $U_i$ and $G_j$ the induced subgraph over $U_j$, if $U_i \cap U_j = U_{overlap} \not= \emptyset$, I want to decide whether certain graph-statistics (degree centrality, eigenvector centrality,...) observed for the set of nodes $U_{overlap}$ with respect to $G_i$ and $G_j$ significantly differ from scores reached by vertices not in the overlap, but in either $U_i$ or $U_j$.
Cardinalities of $U$ in my practical setting range from $3$ to approx. $2000$, naturally affecting how "coarse-grained" the discrete probability distribution over a certain graph-statistic is represented for either $G_i$ or $G_j$.
Likewise, $|U_{overlap}|$, over all instances of comparisons varies drastically (and so do the sizes of $U_{i,j} \setminus U_{overlap}$).
In a first approach, I just added up all values of a particular graph statistic for all overlap-nodes (and non-overlap-nodes) for all comparisons. However, I figure, due to the nature of the problem, this probably is not a valid approach: Think of an arbitrarily large $U_i$, with many non-overlapping nodes that show a particularly low degree distribution (one connection to a hub-which is in the set of overlapping nodes), while, the one overlapping node has a degree of $1$. Even if all the other comparisons showed no difference w.r.t. degree centrality of overlapping and non-overlapping nodes, having "inflated" the set of non-overlapping observations with arbitrarily many values close to $0$, by just looking at the distributions over degrees, I might conclude, that overlapping nodes are likely to show a higher degree.
So what I need is a valid way of "aggregating" over a large set of comparisons, e.g. through sampling exactly as many nodes from the non-overlap-sets as nodes found in the overlap-set (this, at least, would balance things out).
Still, degree distributions may vary a lot from one comparison to the other, which poses another problem, that needs to be handled during aggregating. So what I need is a measure, that rids of the differences in the distribution of graph-statistics across instances of comparisons. I though of computing how likely picking a certain configuration of nodes would be:
I.e. given the discrete distribution of values of a certain graph-statistic, calculate the likelihood of picking, say, $50$ nodes with values, at least as large as the observed ones. Here, I run into the problem that computing such likelihoods becomes infeasible to compute.
I would be glad if someone could point out a possible solution towards assessing "importance" or "significance" (using these terms loosely) of certain graph-statistics in such a setting.
