How to test whether the majority of vertices belong to one giant component?

Question

I have a sample of 200 independent networks and I want to test the hypothesis that majority of vertices belong to one giant component. I wonder what is the appropriate approach to do that.

More formally, suppose we have two variables, $A$ and $B$, where $A$ denotes number of vertices belonging to a giant component in a network $i$ and $B$ denotes number of vertices not belonging to giant component in network $i$.

The task is to test the hypothesis $\mu_A > \mu_B$. Because $A$ and $B$ are clearly dependent here, I doubt that classical statistical tests (e.g., Z-test) are appropriate here.

Any suggestion would be greatly appreciated.

Answer 1

Depending on where your data comes from, you could try either monte carlo simulation or bootstrapping to get a confidence interval.

If you have random data which generates this network (e.g., if your network is a correlation matrix, or if it is a similarity matrix, or anything else that you can simulate), you could try randomly generating the data which is used to make the network. Do this 10,000 times and see how many have a larger giant component than the one you observed.

If you do not have underlying data, but just have the network then you might try a different approach. If you believe structural equivalence is more important than geodesic distance in terms of clustering the nodes, then it makes sense to bootstrap the vertex labels (i.e., sample the vertex labels with replacement and if in the original network there is an edge from $i \to j$, then if you draw vertices $i$ and $j$, then connect them in the bootstrap sample as $i \to j$. Do this 10,000 times and see how many bootstrapped networks have a larger giant component.

If you don't believe structural equivalence holds for your graph, but you believe you know the distribution that comes from, then you can sample graphs from that distribution. If I saw this in a paper though, I wouldn't believe it, because there are no good graph distribution models (which is why there are so many different ones that have been proposed). Even when the graph does come from a distribution for some theoretical reason, estimating the graph parameters (as in an exponential random graph model) has been shown to be bad even with very few parameters (see e.g., the Chatterjee & Diaconis 2011 paper on ERGMs). In the unlikely event that you have a good model to simulate from, you could either try to do the math to find the theoretical distribution of the size of the largest component... or just do a simple monte carlo simulation again with the 10,000 samples.

...I'm new to stack exchange, and I just saw this was asked about a year ago. I hope this is still helpful to someone though.