<jupyter_start><jupyter_text>Part 3: Watts-Strogatz NetworksIn this part *Watts-Strogatz Networks* will be investigated. Watts-Strogatz Networks is an extension to the random network model that takes care of the two following properties seen in real networks[1, chap 3]:1) The **Small World Property** that states the average distance between any two nodes should depend logaritmically on $N$, where $N$ is the total number of nodes in the network. This can be related to the *six degrees of seperation* where just a few connections between persons from Denmark to the United states means that many Danes only requires a few links to get to most people in the United States. 2) **High Clustering** that states the clustering coefficient of real networks is much greater than what is seen in random networks of the same size. This can be related to the fact that e.g. in a real social network there is a greater probability than random that the friends of a given person also being friends (which is what the clustering coefficient calculates).To make a Watts-Strogatz Network the number of nodes an edges have to be defined. As with a random netowrk it takes the parameters $N$ for the total number of nodes while $k$ indicates the degree for each node. As the extension a parameter $p\in[0;1]$ also has to be set. Setting $p=0$ leads to a regular network where the nodes are connected to their $k$ nearest neighbors. This is illustrated below with a simple example where $N=16$ and $k=2$.<jupyter_code>plt.figure(figsize = (14,6))
nx.draw(
    nx.watts_strogatz_graph(16, 2, 0), 
    node_size = 300, 
    node_color = "#A0CBE2", 
    edgecolors = "k")
plt.title("Watts-Strogatz graph with n=16, k=2 and p=0", fontsize = 18)
plt.show()<jupyter_output><empty_output><jupyter_text>What $p$ actually indicates is the probability of *rewiring* a given edge to a random node. This means as the probability $p$ rises, the network approaches a random network which is the case when $p=1$. The small-world phenomena is seen as $0<p<1$ as some nodes will rewire and not only be connected to the neighbours. This is what is investigated in the following exercises below: **Use `nx.watts_strogatz_graph` to generate 3 graphs with 500 nodes each, average degree = 4, and rewiring probablity $p = 0, 0.1, \textrm{and } 1$. Calculate the average shortest path length $\langle d \rangle$ for each one. Describe what happens to the network when $p = 1$.** In the code cell below the task is carreid out with `network` where three graphs are created and the average shortest path length for each of three graphs are calculated. Afterwards the three graphs are plotted and shown with their average shortest path length.<jupyter_code># Initilize list for graphs
WSgraphs = []

# Set parameters
n = 500
k = 4
p_list = [0,0.1,1]

# Create graphs
for p in p_list:
    WSgraphs.append(nx.watts_strogatz_graph(n, k, p))

# Calculate average shortest path
avg_shortest = [nx.average_shortest_path_length(graph) for graph in WSgraphs]

fig, axes = plt.subplots(nrows=3, ncols=1, figsize = (16,16))
ax = axes.flatten()

for i,graph in enumerate(WSgraphs):
    nx.draw(graph, pos = nx.circular_layout(graph), node_size = 50, node_color = "#A0CBE2", edgecolors = "k", linewidths = 0.1, ax=ax[i])
    ax[i].set_title(f"Network with p={p_list[i]} that gives an average shortest path length of {avg_shortest[i]:.2f}", fontsize = 18)
    #ax[i].set_axis_off()

plt.show()<jupyter_output><empty_output><jupyter_text>By starting from the top:* $p=0$: What is seen here is very similar to what was seen in the example further up. As $k = 4$ it means that each node is connected to its two neighbours - this can though be a bit hard to see as $N = 500$. One can though verify that no links goes "across" the graph. An average shortest path length of 62.88 is obtained.* $p=0.1$: Now it becomes very clear what the Watts-Strogatz model actually does. A few links (as p still is quite low) are now connecting nodes that are not close neighbours. Even though $p$ only is 0.1 the average shortest path length has dropped to 7.72. This is due to the fact that by using some of these *cross links* the path lenghts can drop significantly.* $p=1$: A random network is now obtained which can be seen due to the vast number of links connecting nodes that are not close neighbours. This leads to a futher drop in the average shortest path length to only 4.74.  **Let's understand the behavior of the WS model as we increase _p_ in more detail.. Generate 50 networks with $N = 500$, $\langle k \rangle = 4$, for each of $p = \{0, 0.01, 0.03, 0.05, 0.1, 0.2\}$. Calculate the average of $\langle d \rangle$ as well as the standard deviation over the 50 networks, to create a plot that shows how the path length decreases very quickly with only a little fraction of re-wiring. Use the standard deviation to add errorbars to the plot.** The same $n$ and $k$ as above is used. The new p-list is defined and as well as the number of networks per $p$. In order to calculate all average shortest path lengths a list comprehension is used which afterwards is converted to a 2d-numpy array. Using the array the mean and standard deviation for each $p$ can be calculated.<jupyter_code># New p-list
p_list = [0,0.01,0.03,0.05,0.1,0.2]

# Number of repetitions
N = 50

# Store all results in a 2d numpy array
WSgraphs_avg_shortest = np.array([nx.average_shortest_path_length(nx.watts_strogatz_graph(n, k, p)) 
                                  for p in p_list for j in range(N)]).reshape(-1,N)

# Calculate mean and standard deviation
mean_list = np.mean(WSgraphs_avg_shortest, axis = 1)
std_list = np.std(WSgraphs_avg_shortest, axis = 1)<jupyter_output><empty_output><jupyter_text>Using the results obtained above this can be plotted as shown below:<jupyter_code>plt.figure(figsize = (16,8))
plt.errorbar(x = p_list, y = mean_list, yerr=std_list, lw = 2, fmt = "-o", ecolor = "r", capsize = 3, color = "k")
plt.title(r"Average shortest path length as a function of p. Error bars indicates 1$\sigma$", fontsize = 18)
plt.xlabel("p", fontsize = 18)
plt.ylabel(f"Avg.(<d>) across {N} repetitions", fontsize = 18)
plt.xticks(fontsize = 14)
plt.yticks(fontsize = 14)
plt.ylim((0,70))
plt.show()<jupyter_output><empty_output><jupyter_text>From the plot it can clearly be seen how drastic the average shortest path lenght drops - it looks very exponential. More over it is also interesting to notice the variation in standard deviation as seen from the error bars. The exact figures are printed below as a fdict:<jupyter_code>print("Standard deviation as a function of p:")
dict(zip(p_list, std_list))<jupyter_output>Standard deviation as a function of p:<jupyter_text>Firstly it is noted that for $p=0$ a standard deviation around the machine epsilon is obtained. This is though not very unsuprising as the graph is deterministic when $p=0$. The mean value of just around $500/8=62.5$ makes perfect sense; there is a distance of 1 between two nodes that are not directly neighbours in the circle. The means it takes $n/(2\cdot2)$ steps to reach the furthest point in the graph. The second "2" comes from the fact it is a circle and there is only $n/2$ to the furthest point. This is though to the furthest away node. On average only a fourth of the circle has to be travesed and remebering that $k=4$ leads to jump of two the $500/8=62.5$ is obtained. As there still is a distance of 1 to the direct neighbouts the actual figure is just above the 62.5.Settign $p=0.01$ the standard deviation grows quite large. This is though also not unsurprising as setting $p=0.01$ means that the expected number of edges that is rewired is $p\cdot n\cdot k/2 = 10$. This low number introduces massive uncertanity. If they end up being rewired to nodes still very close the average shortest path lengths still ends up being quite far. On the opposite if a few of these *cross* the whole graph the average shortest path length can take a large drop. Usign this reasoning the lower standard deviation for larger $p$'s can be deducted. As more edges are rewired the probability that getting the *key edges* that traverse the network increasing brings the uncertanty down. For $p=0.2$ it is seen that the standard deviation drops to around $0.1$ with a mean values of aroudn 6.  Part 4. The Barabasi-Albert ModelA different type of graph model will now be investigated - more specifically the Barabasi-Albert Model. What makes this model different is the fact that all nodes does not exist to start of with. Instead the nodes are added iteratively. In this part a special version of the Barabasi-Albert model will be used, where the graphs are generated as follows [1, chap5]:1) Start of with a graph consisting of two nodes that are both connected.2) Add a new node and connect it to only one of the existing nodes. The probability of the new node connecting to node $i$ is given as $k_i/\sum_j k_j$. Or to explain it in English; the greater the degree of a given node is the greater the probability is that a new node will be connected to that given node.3) Repeat 2) until a desired total number of nodes is reached.A function, `create_BA_graph`, has been implemented below which follows the algorithm described above:<jupyter_code># Number of total nodes
def create_BA_graph(total_nodes):
    # Init graph
    G = nx.Graph()
    G.add_edge(0, 1)
    
    # Add nodes and edges
    nodes_to_add = np.arange(2, total_nodes)
    for node in nodes_to_add:
        connect_to = np.random.choice(a = [k for k,v in G.degree], 
                                      p = [v for k,v in G.degree]/np.sum([v for k,v in G.degree]))
    
        G.add_edge(node, connect_to)
    
    return G<jupyter_output><empty_output><jupyter_text>**Create a 100 node BA network using a BA model that you've coded on your own (so don't use the built-in NetworkX function, but the one you created during week 3). And plot it using NetworkX.** To do this the function above is used and the resulting graph can easily be plotted using networkX as seen below:<jupyter_code># Create BA network with 100 nodes
G_BA100 = create_BA_graph(100)

# Draw it
plt.figure(figsize = (14,5))
nx.draw(
    G_BA100, 
    node_size = 100, 
    node_color = "#A0CBE2", 
    edgecolors = "k")
plt.title("Barabasi-Albert graph with 100 nodes", fontsize = 18)
plt.show()<jupyter_output><empty_output><jupyter_text>From the plot it becomes clear that this particular graph generating method leads to a *forest*, which is an undirected graph in which any two vertices are connected by at most one path. This makes perfect sense as each new node only connects to a single node and as such cycles can never appear. Another property is that there are quite a few *hubs* and thus also many nodes with degree 1. As the number of edges is constant at $n-1$, where $n$ is the total number of nodes, it is clear having hubs must also lead to nodes with degree 1. Having hubs is also expected as the probability of new nodes connecting to hubs are larger given the algorithm. This will lead to a few nodes having very high degree while many nodes will have degree 1. This is investigated below: **Now create a 5000 node network. What's the maximum and minimum degree? Now, bin the degree distribution, for example using `numpy.histogram`. Plot the distribution. Plot it with both linear and log-log axes.** Using the `create_BA_graph` function as before a BA model with 5000 nodes is created. A random seed is set for reproducability.<jupyter_code># Use seed for reproducability
np.random.seed(42)

# Create BAgraph with 5000 nodes
G_BA5000 = create_BA_graph(5000)<jupyter_output><empty_output><jupyter_text>In order to calculate the minimum and maximum degree the inbuilt method `.degree` in networkX is used:<jupyter_code># Calculate minimum and maximum degree and print results
minD = np.min(np.min([v for k,v in G_BA5000.degree]))
maxD = np.max(np.max([v for k,v in G_BA5000.degree]))
print(f"The minimum degree is {minD} and the maximum degree is {maxD}.")<jupyter_output>The minimum degree is 1 and the maximum degree is 191.<jupyter_text>To obtain a minimum degree of 1 is expected as discussed above in the example with 100 nodes. It wil actually always be 1 as the final node added only will have one connection. It is though also seen that there is a very large hub with degree 191 - this is a result of the way the graph is created and it will be even more clear below. Here, the distribution is binned with the same method as in part 1. The frequency of nodes with a given degree is then showed. To the left with linear axis and to the right with log axis.<jupyter_code># Bin the distribution
v = np.arange(minD, maxD+2)
counts = np.histogram([v for k,v in G_BA5000.degree], bins = v-0.5)[0]

fig, (ax1, ax2) = plt.subplots(nrows=1, ncols=2, figsize = (16,6))

#Nonlog
ax1.scatter(x = v[:-1], y = counts)
ax1.set_title("Frequency of nodes with given degree")
ax1.set_xlabel("k", fontsize = 18)
ax1.set_ylabel("Count", fontsize = 18)

#log
ax2.scatter(x = v[:-1], y = counts)
ax2.set_title("Frequency of nodes with given degree (log-log plot)")
ax2.set_xlabel("k", fontsize = 18)
ax2.set_ylabel("Count", fontsize = 18)
ax2.set_xscale('log')
ax2.set_yscale('log')
ax2.set_ylim(bottom=0.7, top=10**4)

plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07632211538461539, 'fraction_numerical': 0.023587740384615384, 'mean_word_length': 4.340152426795026, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '73269', 'license': 'RSA-MD', 'n_tokens_mistral': 4145, 'n_tokens_neox': 3829, 'n_words': 1959, 'path': 'notebooks/.ipynb_checkpoints/Assignment1_Ex34-checkpoint.ipynb', 'repo_name': 'MikkelGroenning/02805_social_graphs', 'size': '13312'}