# Statistical Test for “clumpiness” of graph

My data set is a list of items and for each item a list of all other items that this item has cooccurred with. Effectively this is an adjacency matrix for a non-directed graph. I'm looking for some sort of test to determine if the clustering in the graph is statistically significant or if whatever "clumpiness" I see is a product of chance.

I think a null hypothesis here is that the graph was randomly generated using the following the process: a user views items randomly but selects the item based upon the "popularity" of the product (e.g. the probability of viewing an item is not uniformly distributed). The alternative hypothesis would be that the user selects items to view based somewhat upon their particular interests thus leading to more clumpy adjacency matrix of co-occurrent items.

Now I think I just need a good statistic to measure this notion of "clumpiness". Then I can state my hypothesis test as "What portion of random graphs are more 'clumpy' than the graph I'm testing?" And if that number is low then it's likely that this graph has useful clustering. (I guess the next question is how low should this value be before I can actually draw useful information from this graph?)

So in summary: Is there a statistical test to determine whether a given undirected graph is "clumpier" than it would be just by pure chance?

(see this related question)

• I would not know how to do it with a statistical test with a null hypothesis and so on. But you could model the graph as a combination of views based on popularity and views based on particular interests (would those be purely at random?) Then use some coefficients for each of the two, fit your model to your real dataset, find the value of the 2 coefficients for your dataset, and take conclusions. I hope it makes sense. – lrnzcig Oct 27 '15 at 21:10