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.


In all respect, I don't think your first approach was invalid. I hope I understood correctly what you were saying since it was a long story, but why would you want to correct for the fact that overlapping nodes might be more central or have a higher degree?

In most cases this is actually an intrinsic characteristic of these nodes and thus exactly what I think you want to investigate in your specific case.

| cite | improve this answer | |
  • $\begingroup$ Think of 11 nodes in one of the $U$s, with one having degree 1 and the others having degree 0.1. Then I would add "1" to my list of "overlapping-degree-values" and 10x 0.1 to my list of "non-overlapping-degree-values". Continuing with, say, 3 more comparisons, where I have 2 nodes each, 1 in the overlapping set and 1 in the non-overlapping set, both with a degree of 1, I would end up with [1,1,1,1] of degree values for overlapping nodes, and [0.1,0.1,...,0.1,1,1] for non-overlapping nodes. The distributions are entirely different, even though deg(v) was only of importance in one comparison. $\endgroup$ – sim Sep 25 '14 at 17:14
  • $\begingroup$ I'm still not sure if I entirely understand your question: do you determine your subsets U beforehand or do you determine them post-hoc based on overlapping or non-overlapping network characteristics? $\endgroup$ – Fraukje Sep 26 '14 at 7:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.