For any graph a set of nodes can be used to obtain an induced subgraph
subGraph). An interesting question is whether that
subgraph has an unusually large number of edges. This function
computes the probability that a random subgraph with the same
number of nodes has more edges than the number observed in the
presented subgraph. The appropriate probability distribution is
subgraph made from the original graph
original graph object from which the subgraph was made
The computation is based on the following argument. In the original
graph there are n nodes and hence N=n*(n-1)/2 edges in the
complete graph. If we consider these N nodes to be of two types,
corresponding to those that are either in our graph,
g, or not in
it. Then we think of the subgraph which has say m nodes and
M=m*(m-1)/2 possible edges as representing M draws from an
urn containing N balls of which some are white (those in
and some are black. We count the number of edges in the subgraph and use
a Hypergeomtric distribution to ask whether our subgraph is particularly
The probability of having greater than or equal to the subgraph's number of edges is returned.
1 2 3 4 5 6
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.