<jupyter_start><jupyter_text>Introduction to Data Science and ProgrammingClass 21: Introduction to network scienceIT University of Copenhagen, Fall 2019    Instructor: <NAME>  SourceThis notebook was adapted from:* <NAME> / Data4Sci: https://github.com/DataForScience/Networks<jupyter_code>from collections import Counter
from pprint import pprint

import numpy as np
import matplotlib.pyplot as plt<jupyter_output><empty_output><jupyter_text>Edge List Let us start by defining a list of edges. This will give us our first "dataset" to work with<jupyter_code>edge_list = [
    ('A', 'B'),
    ('A', 'C'),
    ('A', 'E'),
    ('B', 'C'),
    ('C', 'D'),
    ('C', 'E'),
    ('D', 'E')]<jupyter_output><empty_output><jupyter_text>This is a particularly useful representation as many datasets are distributed in this (or a closely related) format. From this list, we can easily measure the number of edges that constitute our network. It's main limitations are that it has no way to explictly take into account disconnected nodes (it only accounts for nodes that are part of edges) and no indication on whether it is directed or not.<jupyter_code>number_edges = len(edge_list)
print(number_edges)<jupyter_output>7<jupyter_text>To get the number of node is a bit trickier. We must go edge by edge and keep track of all new nodes. For efficiency, we use a set to automatically remove duplicates<jupyter_code>nodes = set()

for edge in edge_list:
    nodes.update(edge)
    
number_nodes = len(nodes)
print(number_nodes)<jupyter_output>5<jupyter_text>Now we know that we have 5 nodes and 7 edges in our network. The node ids are:<jupyter_code>nodes<jupyter_output><empty_output><jupyter_text>Adjacency List A closely related data structure to the edge list is the adjacency list. In this formulation, we use a dictionary to map each node to its set of neighbors<jupyter_code>adj_list = {}

for node_i, node_j in edge_list:
    if node_i not in adj_list:
        adj_list[node_i] = set()
    
    adj_list[node_i].add(node_j)<jupyter_output><empty_output><jupyter_text>Our adjaceny list is then:<jupyter_code>pprint(adj_list)<jupyter_output>{'A': {'E', 'C', 'B'}, 'B': {'C'}, 'C': {'E', 'D'}, 'D': {'E'}}<jupyter_text>In this approach we inherently assumed that our network is directed (or, equivalently, that both edge directions are present in the data). To generate an undirected version we must make a simple modification to our code to manually add the opposite direction edge<jupyter_code>adj_list = {}

for node_i, node_j in edge_list:
    if node_i not in adj_list:
        adj_list[node_i] = set() # 'set' is used to prevent accidental multiple edges
    
    adj_list[node_i].add(node_j)
    
    # Manually add the opposite direction edge
    if node_j not in adj_list:
        adj_list[node_j] = set()
    
    adj_list[node_j].add(node_i)<jupyter_output><empty_output><jupyter_text>The undirected adjacency list represenation is then:<jupyter_code>pprint(adj_list)<jupyter_output>{'A': {'E', 'C', 'B'},
 'B': {'A', 'C'},
 'C': {'A', 'E', 'B', 'D'},
 'D': {'E', 'C'},
 'E': {'A', 'C', 'D'}}<jupyter_text>Adjacency Matrix We now move on to generating an Adjacency Matrix view of the network. For this we must have two things: - the number of nodes in the network- A mapping between the original node ids and a sequential numerical IDWe start by building out the numerical ID mapping. As we do, we get the number of nodes for free<jupyter_code>node_id = {}
node_count = 0

for node_i, node_j in edge_list:
    if node_i not in node_id:
        node_id[node_i] = node_count
        node_count += 1
    
    # Make sure we have an id for both nodes
    # This is necessary, irregardless of whether the network is directed or undirected
    if node_j not in node_id:
        node_id[node_j] = node_count
        node_count += 1<jupyter_output><empty_output><jupyter_text>We can check that each of the original node ids is correctly mapped to a sequential number<jupyter_code>node_id<jupyter_output><empty_output><jupyter_text>Finally, we are ready to build our adjacency matrix. We start by declaring the data structurewe will use<jupyter_code>adj_matrix = np.zeros((node_count, node_count), dtype='int')<jupyter_output><empty_output><jupyter_text>And we can now populate the matrix entries. For generality, we'll include a flag to control wether or not the graph is directed. As we don't have any weights associated with our edges, we assign to each of them a value of 1.<jupyter_code>is_directed = False

for node_i, node_j in edge_list:    
    # Get the correct node ids
    node_i = node_id[node_i]
    node_j = node_id[node_j]
    
    adj_matrix[node_i, node_j] = 1 # Unweighted network

    if not is_directed:
        adj_matrix[node_j, node_i] = 1 # Undirected networks<jupyter_output><empty_output><jupyter_text>Our Adjacency Matrix is then:<jupyter_code>adj_matrix<jupyter_output><empty_output><jupyter_text>As we can see, the Adjacency matrix representation is very wasteful, using 25 values to store a 7 (14) edge network plus 5 dictionary entries for the id mappings.  Adjacency Dict The final graph representation we will explore is the Adjacency Dict. This is a generalization of the Adjacency List covered above that is a bit more flexible and is able to accuratly account for diconnected nodes, weights, etc. For this we will need two datastructures, one to store node information and one for edges. For the sake of flexbility, we will use dicts for both.<jupyter_code>nodes = {}
edges = {}
is_directed = False<jupyter_output><empty_output><jupyter_text>And we can now populate them from our original edge_list<jupyter_code>for node_i, node_j in edge_list:
    if node_i not in nodes:
        nodes[node_i] = {}
        edges[node_i] = {}
        
    if node_j not in nodes:
        nodes[node_j] = {}
        
        if not is_directed:
            edges[node_j] = {}
    
    edges[node_i][node_j] = {}
    
    if not is_directed:
        edges[node_j][node_i] = {}<jupyter_output><empty_output><jupyter_text>Our set of nodes is:<jupyter_code>nodes<jupyter_output><empty_output><jupyter_text>Where we chose to use dictinaries to allow for the storage of node attributes. Further, our edges are now:<jupyter_code>edges<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup