I am trying to determine if my directed Graph G is a “small world”. The graph is created from my dataset which consists of 500 nodes, but only 60 nodes have edges (total of 150 edges).I believe to do so I need to compare the clustering coefficient and the average path length to a random graph R with the same amount of nodes and edges.
Q1: Gephi has an embedded "generate Random Graph" capability - what is the algorithm it uses?
Q2: should I just generate a graph R with 60 nodes and 150 edges, or with 500 nodes and 150 edges?
Q3: I found small differences between definitions of small-worldness test. The one I am using is taken from Humphries, M. D. and K. Gurney (2008). "Network ‘small-world-ness’: a quantitative method for determining canonical network equivalence." PloS one 3(4): e0002051. "The network G is said to be a small-world network if Lg≥Lr and Cg≫Cr" (L is average path length and C is global clustering coefficient). any insights on this definition?
Thanks in advance for any help!
This paper gives a better insight on empirically testing whether a graph is small world. Indeed you have to create a random graph to test your graph.
Q1: As one can see from the code the Gnp, Gnm generators are based on Batagelj, Brandes, Efficient Generation of Large Random Networks, Sunbelt Conf. on Social Networks, 2004, available here.
Q2: The way CC is defined takes into account the number of triangles and connected triples. This notion discards automatically all the isolated nodes (unless you computer the average clustering coefficient by averaging over the number of nodes. This is not what you want though.
The bottom line is that it shouldn't make any difference which graph to choose in your case
Q3: Check the paper in the introduction of my answer for a more intuitive definition and check