computeSmallWorldness {cancerGI} | R Documentation |
This function computes the smallworldness of a graph.
computeSmallWorldness(g, n, m, nrep = 1000)
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}. |
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}.
A scalar of smallworldness.
Audrey Q. Fu
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
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)