3
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lrnzcig Oct 27 '15 at 21:10
3
$\begingroup$

I think what you're looking for is the clustering coefficient? https://en.wikipedia.org/wiki/Clustering_coefficient.

Sorry this should probably be a comment but my reputation's not high enough for that yet :-)

$\endgroup$
  • 2
    $\begingroup$ That's helpful Andrey. Though I suspect the next question is harder: how do I determine the distribution for the clustering coefficient of graphs generated in the manner described above? If I have that, then I could compare the clustering coefficient of the graph in question with the distribution and I could see how "rich" the graph in question is. $\endgroup$ – John Berryman Oct 26 '15 at 19:03
1
$\begingroup$

An information theoretic metric such as entropy would also give you an estimate of nonrandom "clumpiness." Then, for a more formal answer, see this paper on Quantifying randomness in real networks posted here... http://www.nature.com/ncomms/2015/151020/ncomms9627/full/ncomms9627.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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