Network Models: Random Graphs



In [ ]:

    
import numpy as np
import matplotlib.pyplot as plt
# plt.xkcd()
import networkx as nx
%matplotlib inline

Clustering coefficient

During the lecture we have understood, that the clustering coefficient of a random graph is equal to the probability $p$: $$\text{Clustering coefficient} = \frac{\langle k \rangle}{n} = p $$

In this task you have to check it on generated data. Please, generate $100$ Random Graphs with $n = 1000$ and $p = 0.002$ (for saving computational time) and plot the box-plot of your computations.



In [ ]:

    
import networkx as nx
N = 1000 ; prob = 0.002
graphs = [ nx.gnp_random_graph(n = N, p = prob ) for i in range( 100 ) ]



In [ ]:

    
ccoef = [ nx.transitivity(G) for G in graphs ]



In [ ]:

    
plt.plot( ccoef, "x" )
mean_cc = np.mean( ccoef )
plt.plot( np.arange( len(ccoef) ), np.repeat( mean_cc, len( ccoef ) )   )

Size of small components

In this task you are asked to calculate the average size of small components (small component = not a giant one) with regard to average degree of the network. To see the effect clearly, plot average size around $\langle k \rangle = 1$.



In [ ]:

    
# lcc = []
# for G in graphs :
#     deg = G.degree( )
# ## Find all nodes with degree one
#     nodes = [ v for v, d in deg.itmes() if d == 1 ]
#     sc = [ len( nx.node_connected_components( G, v ) for v in nodes ]
#     for cc in  :
#         sc.add( cc )
n = 1000
prob = np.arange( .1/n, 3.0/n, .1/n )
sz = []
for p in prob :
    lcc = []
    for i in xrange( 50 ) :
        G = nx.gnp_random_graph( n, p )
        cc = sorted( nx.connected_components( G ), key = len, reverse = True )
        lcc.extend( [ len( c ) for c in cc[1:] ] )
    sz.append( np.mean( lcc ) )



In [ ]:

    
plt.plot(prob*n, sz, "-r")



In [ ]: