Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!
Get Started for Free

calcSumProb

Calculate the probability that a subgraph has an unusual number of edges.


Description

For any graph a set of nodes can be used to obtain an induced subgraph (see 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 the hypergeometric.

Usage

calcSumProb(sg, g)

Arguments

sg

subgraph made from the original graph

g

original graph object from which the subgraph was made

Details

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 g) 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 dense.

Value

The probability of having greater than or equal to the subgraph's number of edges is returned.

Author(s)

Elizabeth Whalen

See Also

Examples

set.seed(123)
  V <- letters[14:22]
  g1 <- randomEGraph(V, .2)

  sg1 <- subGraph(letters[c(15,17,20,21,22)], g1)
  calcSumProb(sg1, g1)

graph

graph: A package to handle graph data structures

v1.68.0
Artistic-2.0
Authors
R. Gentleman, Elizabeth Whalen, W. Huber, S. Falcon
Initial release

We don't support your browser anymore

Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.