Hypothesis testing for higher density in subsets of a network/graph

Question

I have a network with over 40k nodes and about 12 million edges (float weights) and have about 10k subsets of this network that I want to test for increased density.

I can think of the following options:

1. Binarizing the network and form the problem as a chi square test of local density (sub-region) vs. global network density. By Binarizing I mean edges having weights 1 or 0 (edge exist or not).

   Disadvantage: have to binarize the network and requires setting a magic threshold for removing/keeping edges.

   Advantages: Computationally cheaper than the second option.

2. Avoid binarizing and perform ranksum test between edge weight of local network vs. global

   Disadvantage: computationally expensive, and harder to decide on whether to call a sub-region significantly enriched if it has a few high-weight edges or a lot of medium-weight edges, or both?

   Advantage: no magic threshold.

I'd need to perform many permutations and use a FWER controlling procedure or FDR, so probably the first option is better than the second, but I really dislike the magical cutoff idea.

Is there any other/better way to approach this?

Answer 1

Just looking at the global weight density or weight distribution, respectively, corresponds to the null hypothesis that there is no structure in the network whatsoever and edges are assigned randomly. For example, this null hypothesis implies that your network contains no hubs, i.e., nodes that feature more or stronger connections than to be expected by chance. As you described your application, this null hypothesis is flawed. For example, one of your subnetworks may exhibit a link density that is significantly high according to this null hypothesis just because it happens to contain one more hub than a random subnetwork of this size, while it would not be significant according to a more appropriate null hypothesis that takes into account the presence of hubs.

While such a null model is tedious and most often impossible to describe analytically, you can often easily obtain instances of this null model (surrogates) by some sort of bootstrapping: In the most simple case, these surrogates would be subnetworks consisting of $n$ random nodes, where $n$ is the number of nodes of the subnetwork you want to investigate. Note that what I propose is surrogates for subnetworks, not for the entire network (which would be unchanged). Also note that if you have some a-priori knowledge about your subnetworks, e.g., that they are all connected, your surrogates should be chosen to comply with this a-priori knowledge as well (which may be challenging). I am not entirely sure whether this applies to your application.

Once you have your surrogate subnetworks, all you have to do is to compare their link densities to those of the subnetworks you actually want to investigate. For example, if your original subnetwork’s link density (or whatever measure you fancy) is higher than that of $m=19$ subnetwork surrogates, your subnetwork has a significantly high link density with $p=0.05=\tfrac{1}{m+1}$^‡. I wouldn’t see any advantage provided by binarisation when following this procedure. Even if you choose to have 10 k surrogates (which is more than you would typically need) and all your original subnetworks have the same size, this is only as computationally expensive as evaluating your original 10 k subnetworks (generating the surrogates may be more expensive though if you have to take into account a-priori knowledge).

^{‡ for details of the statistics of surrogates, see for example section 3.3 of Schreiber’s and Schmitz’ review paper on surrogates for time series (Arxiv)}