<jupyter_start><jupyter_text>Assignment 07 Social Network Analysis  CSCI S-96> Instructions: For this assignment you will complete the exercises shown. All exercises involve creating and executing some Python code. Additionally, most exercises have questions for you to answer. You can answer questions by creating a Markdown cell and writing your answer. If you are not familiar with Markdown, you can find a brief tutorial here.  IntroductionIn this assignment you will gain some experience with several algorithms used for the analysis of social networks. There are two running examples. The first dataset is a simple purely synthetic network. The second dataset is a widely used example of a small real-world social network.  Anthropologist <NAME> observed the social interactions between members of a small real-world [karate club](https://en.wikipedia.org/wiki/Zachary%27s_karate_club) over a two year period. Toward the end of the study period a conflict arose which caused the club to split into 2. Some club members stayed connect to a group centered on a founder, Mr Hi. Other members started a new club. Zachary published his results in [1977](https://www.jstor.org/stable/3629752).<jupyter_code>## Install NetworkX if it is not already present.  
#!pip install networkx

## You may need to install PyGraphViz. This instilation will fail on Windows. 
#!pip install pygraphviz<jupyter_output><empty_output><jupyter_text>Execute the code in the cell below to import the packages you will need for this assignment.<jupyter_code>import numpy as np
from scipy.sparse.linalg import eigs
import networkx as nx
import itertools
from networkx.algorithms.community.centrality import girvan_newman
from networkx.algorithms.community import modularity, greedy_modularity_communities
from networkx.linalg.laplacianmatrix import laplacian_matrix
import matplotlib.pyplot as plt

%matplotlib inline<jupyter_output><empty_output><jupyter_text>Data SamplesIn this assignment you will work with two datasets. The first is a simple synthetic network. The second is the karate club dataset. To create and plot the first dataset execute the code in the cell below. Notice the two clear communities.<jupyter_code>edge_list = [(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(2,6),(3,5),(4,5),(5,10),(6,7),(6,9),(6,10),(7,8),(7,9),(7,10),(8,9),(8,10)]
simple_graph = nx.Graph()
simple_graph.add_nodes_from([1,2,3,4,5,6,7,8,9,10])
simple_graph.add_edges_from(edge_list)

nx.draw(simple_graph, with_labels=True, alpha=0.5, node_size=800)<jupyter_output><empty_output><jupyter_text>To import and plot the karate club dataset execute the code in the cell below. The structure of this social network is fairly complex. However, you can see that some nodes clearly have some amount of centrality.<jupyter_code>K_club = nx.karate_club_graph()
nx.draw(K_club, with_labels=True, alpha=0.5, node_size=800)<jupyter_output><empty_output><jupyter_text>Measures of CentralityYou will now compute and assess measures of centrality for both graphs.    Closeness CentralityCloseness centrality is a simple centrality metric. Nodes with a small average inverse distance to the other nodes in the network are considered to have higher centrality.  Execute the code in the cell below to compute and display the closeness centrality of the simple graph. This code uses the [networkx.algorithms.centrality.closeness_centrality](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.closeness_centrality.html?highlight=closeness%20centrality) function.<jupyter_code>simple_closeness_centrality = nx.closeness_centrality(simple_graph)
simple_closeness_centrality<jupyter_output><empty_output><jupyter_text>A graphical display of centrality metrics on a graph is often very useful in terms of interpreting the results. Execute the code in the cell below to display the closeness centrality of the simple graph.<jupyter_code>def plot_centrality(G, node_centrality=None, edge_centrality=None, size=1.0, width=2.0): 
    fig,ax = plt.subplots(figsize=(12,10))
    ## Set the node sizes to display if provided
    if node_centrality==None:
        node_size=size
    else: 
        node_size = [size*node_centrality[key] for key in node_centrality.keys()]
    ## Set the edge width to display if provided 
    if edge_centrality==None:
        edge_width=width
    else:
        edge_width = [width*edge_centrality[u,v] for u,v in edge_centrality.keys()]
    ## Display the graph
    nx.draw(G, with_labels=True, alpha=0.5, node_size=node_size, width=edge_width, ax=ax)  

plot_centrality(simple_graph, simple_closeness_centrality, size=3000, width=2)<jupyter_output><empty_output><jupyter_text>There range of the closeness centrality values is limited. None the less, the results look reasonable since the nodes with the highest closeness centrality are concentrated around the middle of the graph, and more peripheral nodes have low closeness centrality.  > **Exercise 07-1:** You will now compute and display the closeness centrality of the karate club graph by the following steps:   > 1. Compute the closeness centrality of the graph using the [networkx.algorithms.centrality.closeness_centrality](https://networkx.org/documentation/stable/search.html?q=closeness) function.  > 2. Plot the closeness centrality of the graph using the `plot_centrality` function.  > 3. Print the centrality of the graph nodes.<jupyter_code>## Put your code below<jupyter_output><empty_output><jupyter_text>> Examine both the numerical values of closeness centrality and the plot. What statement can you make about how well the closeness centrality represents the connectedness of the network?     > **End of exercise.**  K-CoresK-cores are a metric of connection density at the densest part of a community, the core. A node, $n_i$, is in the k-core if at least $k$ edges can be removed without breaking the component containing the node into parts. At the minimum, a k-core node must have at least $degree(n_i) = k_i > k$.The [networkx.algorithms.core.k_core](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.core.k_core.htmlnetworkx.algorithms.core.k_core) function iterates over values of k. The function starts from $k=1$ and terminates at the value of $k$ where all nodes are in disconnected components. To see how the core components evolved for the simple example graph execute the code in the cell below.<jupyter_code>nx.k_components(simple_graph)<jupyter_output><empty_output><jupyter_text>The key of the displayed dictionary is the value of k. The values are the components for that value of k. At $k=3$ there are 2 disconnected components. For $k > 3$ the components become disconnected.  To visualize the cores at the different values of k execute the code in the cell below.<jupyter_code>def plot_k_components(G, K_comps):
    for c in range(len(K_comps)): #[4,3,2,1]:
        node_colors = ['blue']*len(G.nodes)
        for node in K_comps[c+1][0]: 
            node_colors[node-1] = 'red'
        nx.draw(G, node_color=node_colors, with_labels=True)
        plt.title('Component number = ' + str(c+1))
        plt.show()
        
K_comps = nx.k_components(simple_graph)
plot_k_components(simple_graph, K_comps)<jupyter_output><empty_output><jupyter_text>Notice that for $k=3$ the simple graph is divided into two components. Given the structure of the communities, the selection of k-core nodes is a bit arbitrary. At termination, the algorithm must label nodes as core or not, and in this case, there is no particularly good division of the nodes.      > **Exercise 07-2:** To visualize the k-cores of the karate club graph crease and execute the code in the cell below to display these cores for different values of k. Hint: It will help your interpretation to examine print the degree of the nodes in this graph, which is the [degree](https://networkx.org/documentation/stable/reference/classes/generated/networkx.Graph.degree.html?highlight=degreenetworkx.Graph.degree) attribute of the graph object.<jupyter_code>print(K_club.degree)

## Put your code below<jupyter_output><empty_output><jupyter_text>> Examine these plots. How do the members of the core nodes change with increasing k? How does membership in the k-core align with connectivity of the graph?        > **End of exercise.**  Triangle Centrality and Clustering  The density of triangles, or triad relationships, in a social network is a measure of the centrality of the nodes. Triangle density is computed using the [networkx.algorithms.cluster.triangles](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cluster.triangles.html?highlight=trianglenetworkx.algorithms.cluster.triangles) function. To see the triangle density of the simple graph example execute the code in the cell below.<jupyter_code>## Compute triangle density  
triangles = nx.triangles(simple_graph)
plot_centrality(simple_graph, triangles, size=500, width=2)
triangles<jupyter_output><empty_output><jupyter_text>In the above plot you can see that two nodes have higher triangle density that the others. These nodes are vertices of 4 triangles, indicating centrality of these nodes.Triangle centrality is a biased measure since nodes with higher degree are more likely to be vertices of a triad in a random graph. The clustering coefficient adjusts the triangle density of the nodes by the degree, which is done by the [networkx.algorithms.cluster.clustering](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.cluster.clustering.html?highlight=clusteringnetworkx.algorithms.cluster.clustering) function. Execute the code to display the correlation coefficients for the simple graph.<jupyter_code>clustering = nx.clustering(simple_graph)
plot_centrality(simple_graph, clustering, size=2000, width=2)
clustering<jupyter_output><empty_output><jupyter_text>There are several nodes with high clustering coefficients. Because of the small graph with significant symmetry several nodes have high clustering coefficients.    > **Exercise 07-3:** Compute and display the triangle density for the karate club graph. Display the dictionary of triangle density and the plot.<jupyter_code>## Compute triangle density  
K_triangles = nx.triangles(K_club)
plot_centrality(K_club, K_triangles, size=200, width=2)
K_triangles<jupyter_output><empty_output><jupyter_text>> Examine the triangle density of this graph. How do the nodes with high triangle density compare to the $k=$ core components found in Exercise 07-2?       > **End of exercise.**     > **Exercise 07-4:** In the cell below create and execute the code to display the clustering coefficients of the karate club graph as a dictionary and a plot.<jupyter_code>## Put your code below<jupyter_output><empty_output><jupyter_text>> Examine the results noticing how the clustering coefficient is down-weighted by the degree of the node. What pattern can you observe for the nodes with the highest and lowest clustering coefficients?    > **End of exercise**  Betweenness Betweenness is a measure of the number of shortest paths through a node or edge. Nodes and edges with high betweenness tend to be at the edges of communities within a graph. The node and edge betweenness often follow similar patterns, these different metrics can sometimes highlight different aspects of community structure.   We use betweenness in two ways here. First to highlight community structure in the graph. The nodes and edges connecting communities tend to have the highest betweenness since there are relatively fewer paths between densely connected communities. Next, we will use the concept of betweenness to remove edges from graphs and partition them by communities.       Betweenness Centrality  We can use the concept of either edge or node betweenness as a measure of centrality. Nodes and edges with high betweenness can define the edges of communities. The code in the cells below computes the edge betweenness with the [networkx.algorithms.centrality.edge_betweenness_centrality](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.edge_betweenness_centrality.html?highlight=betweennessnetworkx.algorithms.centrality.edge_betweenness_centrality) function and the node betweenness with the [networkx.algorithms.centrality.betweenness_centrality](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.centrality.betweenness_centrality.html?highlight=betweennessnetworkx.algorithms.centrality.betweenness_centrality). Execute this code and examine the results.<jupyter_code>edge_betweenness=nx.edge_betweenness_centrality(simple_graph)
edge_betweenness
node_betweenness = nx.betweenness_centrality(simple_graph)
node_betweenness<jupyter_output><empty_output><jupyter_text>Next, execute the code in the cell below to display a plot of the simple graph with node size showing betweenness centrality and edge width showing edge centrality.<jupyter_code>plot_centrality(simple_graph, node_betweenness, edge_betweenness, size=10000, width=30)<jupyter_output><empty_output><jupyter_text>Notice the following aspects of the node and edge betweenness for this graph. The nodes with the highest betweenness are the ones with end points for edges between the communities. Correspondingly, the edges between the communities have the highest betweenness.  > **Exercise 07-5:** Starting with the karate club graph create and execute code in the cell below do the following:   > 1. Compute the edge betweenness. > 2. Compute and print the node betweenness centrality. > 3. Plot the graph showing edge betweenness and betweenness centrality.<jupyter_code>## Put your code below<jupyter_output><empty_output><jupyter_text>> Examine this plot and answer the following questions: > 1. Compare the node betweenness centrality to the nodes in the $k=4$ k-core. Do nodes with high betweenness centrality appear to be largely the same ones in the k-core?   > 2. Certain edges have relatively high betweenness. Can you see a correspondence between these edges and a possible division of the graph into communities?  > **End of exercise.**   Graph Partitioning with Betweenness Having explored the betweenness of the two running example graphs, we will now turn our attention to using betweenness to partition these graphs. Since the goal is to partition the graphs by removing edges, we will use edge betweenness. The Girvan Newman algorithm is a well known method for partitioning graphs into communities using edge betweenness. The algorithm partitions the graph by recursively removing edges with the highest betweenness. Execute the code which uses [networkx.algorithms.community.centrality.girvan_newman](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.centrality.girvan_newman.html?highlight=girvan%20newmannetworkx.algorithms.community.centrality.girvan_newman) the function, and examine the results.<jupyter_code>betweenness_decomp = girvan_newman(simple_graph)
betweenness_decomp = tuple(sorted(c) for c in next(betweenness_decomp))
betweenness_decomp<jupyter_output><empty_output><jupyter_text>The Givan Newman algorithm has partitioned the graph into two subsets. These subsets correspond to the communities.    Execute the code in the cell below to see the graph partitioned by these communities.<jupyter_code>col = ['red','blue']
node_colors = ['None']*len(simple_graph.nodes)
for i,list in enumerate(betweenness_decomp): 
    for val in betweenness_decomp[i]:
        node_colors[val-1] = col[i] 
 
nx.draw(simple_graph, with_labels=True, alpha=0.5, node_color=node_colors)<jupyter_output><empty_output><jupyter_text>This above labels of the communities is as expected.   We can take a direct approach to partitioning a graph using edge betweenness. The code in the cell below does just this using a greedy algorithm with the following steps:  1. The function `remove_edges` prunes the k edges with the highest edge betweenness. In the for loop the betweenness of the current graph is computed. It is important to update the edge betweenness values each time an edge is removed, since the graph changes at each step.     2. The edge to removed is determined by the `find_max_edge` function. This function searches the edges in the graph and returns the key (endpoint pair of nodes) with the maximum betweenness.  Execute this code and examine the result.<jupyter_code>def find_max_edge(temp_betweenness):
    max_key = None
    max_betweenness = 0.0
    for edge in temp_betweenness.keys():
        if temp_betweenness[edge] > max_betweenness: 
            max_betweenness = temp_betweenness[edge]
            max_key = edge 
    ## Remove edge from dictionary  
    temp_betweenness.pop(max_key)
    return max_key        

def remove_edges(graph, k=2):
    '''Remove k edges from the graph'''
    temp_graph = graph.copy()
    for _ in range(k):
        temp_betweenness = nx.edge_betweenness_centrality(temp_graph)
        max_key = find_max_edge(temp_betweenness)
        temp_graph.remove_edge(max_key[0],max_key[1])
    return temp_graph    

partitioned_graph = remove_edges(simple_graph, k=2)

nx.draw(partitioned_graph, with_labels=True, alpha=0.5, node_size=500)<jupyter_output><empty_output><jupyter_text>The partition of the simple graph into the two communities is exactly as expected. You will apply the betweenness-based graph partitioning to the karate club graph. But first, it will be useful to see the actual partitioning of the club members that resulted from the club splitting in a dispute. The club split into two communities, one centered around a key figure, Mr Hi, and the other around an officer of the club. To see this partition, execute the code in the cell below.<jupyter_code>club_color = {
    'Mr. Hi': 'orange',
    'Officer': 'lightblue',
}
node_colors = [club_color[K_club._node[n]['club']] for n in K_club._node]
nx.draw(K_club, node_color=node_colors, with_labels=True)<jupyter_output><empty_output><jupyter_text>Examine this result, keeping in mind that Mr Hi is represented by node 0 and the officer by node 33. > **Exercise 07-6:** To understand how the karate club graph can be partitioned using edge betweenness create and execute code in the cell below. At the use a for loop to remove between 9 and 14 edges from the graph. For each iteration of the for loop do the following:  > 1. Compute a partitioned graph for each number of edges to remove using the `remove_edges` function. > 2. Print the number of edges removed as a label of the resulting graph. > 3. Display the plot of the partitioned graph, using the show method to ensure each plot is displayed individually.<jupyter_code>for k in range(9,15): 
    ## Put your code below
    
    print('Remove ' + str(k) + ' edges')
    nx.draw(club_partitioned_graph, with_labels=True, alpha=0.5, node_size=500, node_color=node_colors)  
    plt.show()<jupyter_output><empty_output><jupyter_text>> Examine these results and answer the following questions:  > 1. How many edges must be removed to create a graph with two components, each representing a community?    > 2. Are the members of these two communities found with the graph partitioned reasonably aligned with the actual split of the karate club?  > 3. How many edges must be removed before the graph partition starts to produce isolated singletons? > **End of exercise.**  Modularity and Graph Partitioning   Modularity of a graph measures the concentration of edges to certain nodes compared the number expected for a random graph. Since we expect communities to have a high concentration of edges, modularity can be used as a community detection metric.    There are many proposals for algorithms one can use to partition a graph. In these exercises will we look at only one, greedy partitioning. The algorithm is conceptually simple. The algorithm starts with a random allocation of nodes to two equal partitions of the graph. Nodes chosen at random one at a time. The community assignment of the chosen node is changed to the other community. If the modularity of the graph improves the new assignment is retained. Otherwise the node retains its current assignment. To see this algorithm applied to the simple example graph execute the code in the cell below, which uses the [networkx.algorithms.community.modularity_max.greedy_modularity_communities](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.community.modularity_max.greedy_modularity_communities.html?highlight=greedy%20modularitynetworkx.algorithms.community.modularity_max.greedy_modularity_communities) function.<jupyter_code>modular_communities = greedy_modularity_communities(simple_graph)
print(modular_communities)

## Need to convert this list of frozen sets to a simple flat list. 
## This is a bit tricky. First create a list of lists and then flatten to a single list. 
node_colors = [[col[i]]*len(set(x)) for i,x in enumerate(modular_communities)]
node_colors = [item for sublist in node_colors for item in sublist]

## Finally draw the graph with the colors showing the communities 
nx.draw(simple_graph, node_color=node_colors)<jupyter_output><empty_output><jupyter_text>The greedy modularity algorithm has found the expected two communities.   > **Exercise 07-7:** Complete the code in the cell below to apply the greedy modularity algorithm to the partition of the karate club graph. Assign the partitioned graph to a variable named `club_modular_communities`. Print the `club_modular_communities`. Execute the code and examine the results.<jupyter_code>## Color dictionary for dispalying the graph
col = {0:'red',1:'gray',2:'blue'}

## Put your code below

print(club_modular_communities)

## Need to convert this list of frozen sets to a simple flat list. 
## This is a bit tricky. First create a list of lists and then flatten to a single list. 
node_colors = [[col[i]]*len(set(x)) for i,x in enumerate(club_modular_communities)]
node_colors = [item for sublist in node_colors for item in sublist]

## Finally draw the graph with the colors showing the communities 
nx.draw(K_club, node_color=node_colors)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06601357120388263, 'fraction_numerical': 0.009257178807351817, 'mean_word_length': 5.41880588404961, 'pattern_counts': {'":': 0, '<': 98, '<?xml version=': 0, '>': 135, 'https://': 12, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '24', 'dir': 'jupyter-structured-clean-dedup', 'id': '546290', 'license': 'MIT', 'n_tokens_mistral': 6223, 'n_tokens_neox': 5970, 'n_words': 2526, 'path': 'notebooks/07_SocialNetworkAnalysis.ipynb', 'repo_name': 'kacpersh/CSCI-E-96', 'size': '22260'}