Introduction to NetworkX

F. Mráz

NetworkX is a Python package for modeling, analyzing, and visializing networks

several types of networks
several algorithms for network analysis
read/write networks in many formats

Documentation: https://networkx.github.io/documentation/stable/

At first, we must import the module networkx

!pip install networkx import networkx as nx

Creating Simple Graphs

# create an undirected graph (network) G = nx.Graph()

The graph can have an arbitrary additional information.

G.name = "The first simple graph" G

G.name

Nodes

Nodes in graphs manipulated with networkx can be arbitrary objects that are hashable. Most commnon are numbers and strings.

# adding one node at a time G.add_node(1) G.add_node(2) # adding several nodes at once G.add_nodes_from([3,4,5,6]) G.nodes

The argument X in nx.add_nodes_from(X) can be any iterable container.

Even a graph can be a node!

Edges

# ading edeges one at a time G.add_edge(1,2) e = (2,3) G.add_edge(*e) # unpack the tuple e # adding several edges at once G.add_edges_from([(3,4),(4,5),(5,6),(6,1)]) G.edges

The argument E in nx.add_nodes_from(E) can be any iterable container of edge-tuples. An edge-tuple can be

a 2-tuple - (node$_1$ ,node$_2$ ), or
a 3-tuple - (node$_1$ ,node$_2$ , dc), where dc is a dictionary of edge attributes.

G.add_edge(1,2,weight=2.1) G.add_edges_from([(2,3,{'weight':1.0}), (3,4,{'weight': 3.9}) ]) G.edges

Notes

Adding existing nodes is no error.
Adding existing edges is no error.
Even a graph can be a node!
Any edge and node can have an arbitrary number of atributes.

G.nodes[1]['name'] = "A" G.nodes[2]['name'] = "B" G.add_node(3,name = "C") G.nodes

list(G.nodes)

G.nodes[1]

G.nodes.data()

Removing Nodes and Edges

G.remove_edge(1,6) G.remove_edges_from([(4,5),(5,6)]) G.remove_node(4) G.remove_nodes_from([5,6]) print(list(G.nodes)) print(list(G.edges))

Accessing Nodes and Edges

G.clear() # clear everything from G G.add_edges_from([(1,2,{'weight':1.0}), (2,3,{'weight':2.0}), (1,3,{'weight':1.5}), (3,4,{'weight':2.0})]) print('Nodes:',list(G.nodes)) print('Edges:',list(G.edges))

G.edges

G[1] # this is a view on the neighbors of node 1

G.adj

G.adj[1]

G[1][2]

G.edges[1,2]

G.edges[1,2]['color'] = "blue" G[2][3]['color'] = "red" G[2]

list(G.adjacency())

for (u,v,w) in G.edges.data('weight'): print('{}, {}, {}'.format(u,v,w))

Atributes of Graphs, Nodes and Edges

Each grah, node and edge can have attributes that are stored in a associated attribute dictionary. Attributes are empty by default.

Graph Attributes

They can be added when creating a new graph

G = nx.Graph(time = '1pm') G.graph

changed or added later

G.graph['time'] = '2pm' print(G.graph) G.graph['event'] = 'tournament' G.graph

Node attributes

G.add_node(1, name='Ethan') G.add_nodes_from([3,4], team='Bulls') G.nodes[1]

G.nodes[1]['court'] = 4 G.nodes.data()

Warning: Adding nodes to G.nodes does not add them to the graph. It is necessary to use add_node() or add_nodes_from(). Similarly for edges!

Edge Attributes

G.add_edge(1, 2, round=1 ) G.add_edges_from([(3, 4), (4, 5)], round=2) G.add_edges_from([(1, 2, {'round': 3}), (2, 3, {'time': '3pm'})]) G[1][2]['time'] = '2:30pm' G.edges[3, 4]['time'] = '4pm' list(G.adjacency())

Edge Attributes (cont)

Attribute weight is special, as it is used by several algorithms implemented in networkx. Therefore the attribute weight must be numeric.

G[1][3]['weight'] = 2.3

Oops! What is the error?

Once again with the weight attribute

G.add_edge(1,2,weight=3.2) G.add_weighted_edges_from([(2,3,1.2), (3,1,0.5)]) print(G.adj[2]) G[1][2]['weight'] = 2 print(G.adj[2])

Directed Graphs

Directed graph are represented by the class DiGraph with some specific properties, like DiGraph.out_edges(), Digraph.in_degree(), DiGraph.out_degree(), DiGraph.predecessors(), DiGraph.successors(). Actually, the directed versions of neighbors() is equivalent to successors() while degree reports the sum of in_degree and out_degree.

DG = nx.DiGraph() DG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)]) DG.out_degree(1, weight='weight') DG.degree(1, weight='weight') node = 1 print('Node {} \n\thas successors {}\n\t predecessors {}'.format( node, list(DG.successors(node)), list(DG.predecessors(node))) ) print('Neighbors of node {} are {}'.format( node, list(DG.neighbors(node))) )

Drawing Graphs

import matplotlib.pyplot as plt

G = nx.petersen_graph() plt.subplot(121) #nx.draw(G, with_labels=True, font_weight='bold') nx.draw(G) plt.subplot(122) nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold')

%matplotlib inline G = nx.petersen_graph() plt.subplot(121) #nx.draw(G, with_labels=True, font_weight='bold') nx.draw(G) plt.subplot(122) nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold', node_color="#00AAAA")

Excercises

1. Construct a Simple Graph

Implement function gener_house_graph() that returns an undirected graph representing the following drawing

Implement the following functions, assume that graph is undirected if not said otherwise:

def compute_diameter(G): # returns the diameter of graph G pass def compute_degrees(G): # returns list of degrees of nodes in G pass def avg_degree(G): # return the average degree of nodes in G pass def degree_histogram(G): # plot histogram of degrees of nodes in graph G pass

A center of a graph is a node where the maximum distance (number of edges) traversed to any other node is a minimum, compared to any other node. Essentially, the center of a graph is the most centrally located node. Note that there may be more than one node that qualifies as the center of the graph.

def centers(G): # return the list of all centers of graph G pass def max_diameter_graph(Nodes): # return a graph with the set of nodes Nodes and maximal possible diameter pass def min_diameter_graph(Nodes): # return a graph with the set of nodes Nodes and minimal diameter pass

def binomial_graph(N,prob): # generate graph with N nodes 1,...,N where the probability that a pair # of nodes is connected by an edge is prob pass def describe_graph(G): # print description of graph G. The description should list # as many properties as possible. E.g., the number of nodes and edges, # average degree, standard deviation from the average, number and names of different # attributes of nodes, of edges, etc. pass

G = nx.karate_club