# only needs to be executed once
!pip3 install networkx==3.4.2

Collecting networkx==3.4.2

  Downloading networkx-3.4.2-py3-none-any.whl.metadata (6.3 kB)
Downloading networkx-3.4.2-py3-none-any.whl (1.7 MB)

   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 0.0/1.7 MB ? eta -:--:--

   ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 1.7/1.7 MB 38.8 MB/s eta 0:00:00

Installing collected packages: networkx

Successfully installed networkx-3.4.2

%matplotlib inline

import networkx as nx
import matplotlib.pyplot as plt


edges = [
         # (src, dst, weight)
         ('as27', 'as15', 1),
         ('as92', 'as70', 1),
         ('as85', 'as60', 1),
         ('as85', 'as63', 1),
         ('as35', 'as63', 1),
         ('as70', 'as60', 1),
         ('as60', 'as70', 1),
         ('as63', 'as60', 1),
         ('as60', 'as63', 1),
         ('as92', 'as70', 1),
         ('as15', 'as70', 1),
         ('as70', 'as15', 1),
         ('as70', 'as20', 1),
         ('as60', 'as20', 1),
         ('as20', 'as99', 1),
         ('as99', 'as20', 1),
         ('as60', 'as99', 1),
         ('as63', 'as99', 1),
         ('as85', 'as35', 1),
         ('as35', 'as85', 1)
        ]


ases = {
    # 'name':(posX, posY)
    'as27':(0,0),
    'as92':(20,0),
    'as85':(40,0),
    'as35':(60,0),
    'as15':(-10,20),
    'as70':(10,20),
    'as60':(30,20),
    'as63':(50,20),
    'as20':(20,40),
    'as99':(40,40)
}

def plotNetwork(graph):
    # set plot size
    plt.figure(3,figsize=(14,8))

    # draw graph  
    nodz = {k:ases[k] for k in ases if k in graph.nodes()}
    nx.draw_networkx_nodes(graph, pos=nodz, nodelist=nodz.keys(), node_color = 'lightblue', node_size=1500)
    nx.draw_networkx_edges(graph, pos=nodz, nodelist = [], edgelist = graph.edges(), node_size=1500)
    nx.draw_networkx_labels(graph, pos=nodz)
    
    # remove axis and plot
    plt.axis('off')
    plt.show()

# create graph
G = nx.DiGraph()
G.add_weighted_edges_from(edges)
    
# draw network
plotNetwork(G)

def remove_nodes_of_degree(unigraph, degree):
    # begin insert code  
    nodelist = unigraph.nodes()
    node_deleted = False
    
    # remove nodes of 'degree'
    for node in list(nodelist):
        if unigraph.degree(node) <= degree:
            unigraph.remove_node(node)
            
            # uncomment following lines to see intermediate steps
            #print('Removing node %s' % node)
            #plotNetwork(unigraph)
            
            node_deleted = True
            
    # recursive call in case of node deletion
    if node_deleted:
        return remove_nodes_of_degree(unigraph, degree)

    # end insert code
    return unigraph

# convert to unidirectional graph to simplify kcore
unigraph = G.to_undirected().copy()

one_degree_graph = remove_nodes_of_degree(unigraph, 1)

# plot
print("Resulting graph:")
plotNetwork(one_degree_graph)

Resulting graph:

def perform_kcore(graph):
    # begin insert code

    degree = 0
    while graph.nodes():
        graph_tmp = graph.copy() # copy original graph in case of all nodes being removed
        graph = remove_nodes_of_degree(graph, degree)
        
        if graph.nodes():            
            # print("Network without nodes of degree %s:" % degree)
            # plotNetwork(graph)
            pass
        else:
            # print("The network drawn above is the core of the network, the nodes have a degree of %s" % degree)
            print('All nodes of the core have at least degree {}.'.format(degree))
            return graph_tmp  
        degree = degree + 1  
              
    # end insert code
    return graph
    
# convert to unidirectional graph to simplify kcore
unigraph2 = G.to_undirected().copy()

# plot
plotNetwork(perform_kcore(unigraph2))

All nodes of the core have at least degree 2.

# convert to unidirectional graph to simplify kcore
unigraph2 = G.to_undirected().copy()

unigraph2.add_edge(
    # e.g. :
    # 'as1', 'as2'
# begin insert code
    # e.g. one of the following edges increases the core
     'as85', 'as70'
    # 'as35', 'as70'
    # 'as63', 'as70'
    # 'as99', 'as35'
    
# end insert code
)

# plot
plotNetwork(perform_kcore(unigraph2))

All nodes of the core have at least degree 3.

plotNetwork(G)

Tutorial 2 - Autonomous Systems

Problem 1 Autonomous Systems (10.0 credit)