1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Based on the wikipedia definition of a giant component, it merely need be connected a majority of the nodes in the network. Is this the precise interpretation that you are considering, i.e. that the giant component is connected to >.5 of N where N is the number of nodes in the network? $\endgroup$
    – mpacer
    Jun 16, 2011 at 18:23
  • $\begingroup$ @ThisIstheId Yes, using threshold value I can derive if particular network contains giant component or not. This way I obtain 200 binary values (i.e., 1 = network has giant component and 0 = network hasn't giant component). But what's next step? $\endgroup$
    – Andrej
    Jun 16, 2011 at 18:59

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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