computeSmallWorldness {cancerGI}

Compute smallworldness of a graph

Description

This function computes the smallworldness of a graph.

Usage

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

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}.

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}.

Value

A scalar of smallworldness.

Author(s)

Audrey Q. Fu

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)