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

Requirement already satisfied: networkx==3.4.2 in /Users/patrickdirks/.pyenv/versions/3.11.14/envs/jup2/lib/python3.11/site-packages (3.4.2)

[notice] A new release of pip is available: 24.0 -> 25.3
[notice] To update, run: python -m pip install --upgrade pip

%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()

 # e.g. :
    # 'as1', 'as2'
edge = (
    # begin insert code
    # e.g. one of the following edges increases the core
    'as85', 'as70'
    # 'as35', 'as70'
    # 'as63', 'as70'
    # 'as99', 'as35'
    # other solution are also possible
    # end insert code
)

unigraph2.add_edge(
    edge[0], edge[1]
)

# plot
plotNetwork(perform_kcore(unigraph2))

All nodes of the core have at least degree 3.

plotNetwork(G)

Tutorial 3 - Autonomous Systems & Routing Tables

Problem 1 Autonomous Systems (9.0 credit)