# Assessing Significance of Graph Statistics for a Selection of Vertices in a Network

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.

• 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. – sim Sep 25 '14 at 17:14
• 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? – Fraukje Sep 26 '14 at 7:36