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

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?

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?

• What do you mean by "binarize"? I would probably use this to mean that all edges must have weight 0 or 1, as opposed to continuous-valued edge weights. But it seems like that's not what you mean. Aug 13, 2017 at 23:55
• Reading this again, maybe that is exactly what you mean. One way to avoid choosing a threshold would be to run the analysis across multiple thresholds. For example, if the range of weight values is (0,1), you could run the analysis at each element of {0.1, 0.2, ..., 0.9}. Aug 13, 2017 at 23:59
• @DanHicks Yes, by binarizing I meant edges having 0 or 1 value. Question is updated with more information on this
– NULL
Aug 14, 2017 at 12:15
• @DanHicks Multiple thresholding is a good idea, but wouldn't that increase the number of test I have to correct for?
– NULL
Aug 14, 2017 at 12:17

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)

• The idea of using surrogate networks is very interesting. But, there is a linkage problem that bootstrapping could harm. Take a look at the updated question with scientific context added.
– NULL
Aug 14, 2017 at 12:19
• or maybe not, as you mentioned these surrogates would be subnetworks consisting of nn random nodes, where nn is the number of nodes of the subnetwork you want to investigateSo it is using the current structure of the network without permuting it?
– NULL
Aug 14, 2017 at 12:20
• So it is using the current structure of the network without permuting it? – Right. You are generating subnetwork surrogates, not network surrogates. Also see my edit. Aug 14, 2017 at 19:53
• Cool, one thing though, even with bootstrapping, we still need to perform a test, and the problem with binarizing, etc. still exist, what's your recommendation about that?
– NULL
Aug 16, 2017 at 13:04
• Do you mean keeping the weights and get an estimation of null distribution by bootstrapping. What measure to be used? Like median weight of sub-network surrogate?
– NULL
Aug 16, 2017 at 13:05