cancerGI (version 1.0.0)

computeSmallWorldness: Compute smallworldness of a graph

Description

This function computes the smallworldness of a graph.

Usage

computeSmallWorldness(g, n, m, nrep = 1000)

Value

A scalar of smallworldness.

Arguments

g

A graph object.

n

Number of nodes of g.

m

Number of edges of g.

nrep

Number of random graphs to generate for estimating \(C_{rand}\) and \(L_{rand}\).

Author

Audrey Q. Fu

Details

For a graph \(g\) with \(n\) nodes and \(m\) edges, the smallworldness \(S\) is defined as in Humphries and Gurney (2008):

\(S = (C_g / C_{rand}) / (L_g / L_{rand})\),

where \(C_g\) and \(C_{rand}\) are the clustering coefficient of \(g\) and that of a random graph with the same number of nodes and edges as \(g\), respectively. Also, \(L_g\) and \(L_{rand}\) are the mean shortest path length of \(g\) and that of the same random graph, respectively.

Here, in order to estimate \(C_{rand}\) and \(L_{rand}\), this function generates a large number of random graphs with \(n\) nodes and \(m\) edges under the Erdos-Renyi model (Erdos and Renyi, 1959), such that each edge is created with the same probability as the nodes in \(g\). This function then computes \(C\) and \(L\) for each random graph, and takes the average as the estimate for \(C_{rand}\) and \(L_{rand}\).

References

Humphries, M. D. and Gurney, K. Network 'small-world-ness': a quantitative method for determining canonical network equivalence. PLoS ONE 3, e0002051 (2008).

Erdos, P. and Renyi, A. On random graphs. Publ. Math. 6, 290-297 (1959).

Wang, X., Fu, A. Q., McNerney, M. and White, K. P. (2014). Widespread genetic epistasis among breast cancer genes. Nature Communications. 5 4828. doi: 10.1038/ncomms5828

Examples

library (igraph)
# compute smallworldness for the design graph
data (tested_pairs)
# build the graph object
g <- graph.edgelist (as.matrix (tested_pairs), directed=FALSE)
summary (g)  # 67 nodes and 1508 edges
# compute smallworldness
computeSmallWorldness (g, n=67, m=1508)