Graphs and networkx

Objectives¶

By the end of this lesson, students will be able to:

Use methods from networkx to create and manipulate graphs

Networks¶

In Homework 4 - Networks, you’ll work with graphs in the networkx Python library to represent a social media friend recommendation algorithm, such as Facebook. This section will introduce you to some of the underlying ideas we will need to understand how graphs work, their uses in data science, and the implementation of this recommendation algorithm.

Graphs¶

A graph is a data structure that represents relationships between entities. It consists of:

Nodes (also called vertices): The entities themselves
Edges: Connections between nodes

The degree of a node is the number of edges connected to it.

Graphs are everywhere in computing and data science: transportation systems, web pages linked by URLs, citation neteworks, course prerequisites, food webs, and much more. There are a few main types of graphs:

Undirected graphs: Edges have no direction. If A connects to B, then B connects to A. Example: Facebook friendships (symmetric relationships).
Directed graphs (digraphs): Edges have direction. An edge from A to B doesn’t necessarily mean there’s an edge from B to A. Example: Twitter follows (asymmetric relationships).
Weighted graphs: Edges have associated weights or costs. Example: Road networks where weights represent traffic congestion.

Note that either an undirected or directed graph can have weighted or unweighted edges. A helpful way to think about this is that a graph can be either undirected or directed, and either weighted or unweighted.

The `networkx` Library¶

networkx is a fairly powerful Python library for creating and analyzing graphs. You can find a full tutorial for how to get started in the Homework 2 spec, or by following the link here. The convention is to import the networkx library as nx, and most of the work that we will do with graphs uses the nx.Graph() object. This initializes an empty graph so that we can add edges and/or nodes.

import networkx as nx
import matplotlib.pyplot as plt  # Needed to make the graphs appear

# Create an undirected graph
avengerz = nx.Graph()

# Add individual nodes
avengerz.add_node("Ava")
avengerz.add_node("Bob")

# Or add multiple nodes at once using a list
avengerz.add_nodes_from(["Yelena", "John", "Bucky", "Alexei"])

# Add individual edges
avengerz.add_edge("Alexei", "Yelena")

# Or several at once, using a list of two-element tuples
avengerz.add_edges_from([("Bob", "Yelena"),
                        ("John", "Ava"),
                        ("Bucky", "John"),
                        ("John", "Yelena")])

# Visualize the graph
nx.draw_networkx(avengerz)

# Save figure
plt.savefig('avengerz_graph.png')

It is also possible to initialize nodes in a Graph only by using the add_edge or add_edges_from functions:

friends = nx.Graph()

abc = [("Enjolras", "Combeferre"),
       ("Combeferre", "Prouvaire"),
       ("Prouvaire", "Feuilly"),
       ("Feuilly", "Courfeyrac"),
       ("Courfeyrac", "Bahorel"),
       ("Bahorel", "Bossuet"),
       ("Bossuet", "Joly"),
       ("Joly", "Grantaire")]

friends.add_edges_from(abc)
nx.draw_networkx(friends)
plt.savefig("friends_graph.png")

For a directed graph, we use DiGraph instead. Also, note that a node can have any type! You can even create nodes with additional attributes by defining them in the form (node, dict) where the dict is a dictionary of the node’s attributes.

# Create a directed graph
rj = nx.DiGraph()

rj.add_nodes_from([("Romeo", {"House": "Montague"}),
                   ("Juliet", {"House": "Capulet"}),
                   ("Mercutio", {"House": "Prince"})])

rj.add_edge("Romeo", "Juliet")
nx.draw_networkx(rj)
plt.savefig("rj_graph.png")

Here are some functions you may find helpful for both Graphs and DiGraphs:

graph.number_of_nodes() returns the number of nodes in the graph
graph.number_of_edges() returns the number of edges in the graph
graph.nodes() returns a set-like object containing all the nodes in the graph
graph.edges() returns a set-like object containing all the edges in the graph
graph.degree[n] returns the number of edges that n has
graph.neighbors(n) returns the “neighbor” nodes of n, or any node that is connected to n by an edge

Food for thought: When would you want to directed or undirected graphs?

Set Operations¶

When working with graphs and social networks, we frequently need to compare groups of nodes. Python’s set operations are perfect for this! Sets allow us to efficiently find commonalities and differences between collections.

Intersection (&) lets us find the elements that appear in both sets
Union (|) lets us find the elements that appear in either or both sets
Difference (-) lets us find the elements that appear in the first set but not the second (order matters!)

s1 = {1, 2, 3, 4, 5}
s2 = {3, 4, 5, 6, 7}

print(s1 & s2)
print(s1 | s2)
print(s1 - s2)

{3, 4, 5}
{1, 2, 3, 4, 5, 6, 7}
{1, 2}

⏸️ Pause and 🧠 Think¶

Take a moment to review the following concepts and reflect on your own understanding. A good temperature check for your understanding is asking yourself whether you might be able to explain these concepts to a friend outside of this class.

Here’s what we covered in this lesson:

Graphs
- Undirected graphs
- Directed graphs
- networkx
Set operations

Practice Problems¶

Let’s work together on writing the class in labcourse.py, which is a subclass of the Course class in course.py.

LabCourse¶

Recall the Course class, which represents a course object that has a course code, credit hours, an instructor, and a list of prerequisites:

class Course:
    def __init__(self, code: str, credit_hours: int, 
                 instructor: str, prereqs: list[str]) -> None:
        self._code: str = code
        self._credit_hours: int = credit_hours
        self._instructor: str = instructor
        self._prereqs: list[str] = prereqs

    def get_name(self) -> str:
        return self._code

    def get_prereqs(self) -> list[str]:
        return self._prereqs

    def get_credit_hours(self) -> int:
        return self._credit_hours

    def check_instructor(self, other: "Course") -> bool:
        return self._instructor == other._instructor

Task: Update the Course class to include a __str__ method which returns a string representation of the course in the format: "COURSE (X credits)" where COURSE is the name of the course, and X is the number of credit hours in the course.

Task: Define a new class LabCourse that inherits from the Course class and adds the following attributes:

A field lab_days, which is a list of strings representing the days that the labs meet, e.g., ["Tuesday", "Thursday"]
A field lab_materials which is a boolean representing whether the lab requires extra materials, e.g., False
A method get_lab_days that returns the list of strings representing the days that the labs meet
A method needs_materials which returns whether the lab requires extra materials
A method __str__ that overrides the existing __str__ function to return a string representation of a lab course in the format: "COURSE (X credits) - Lab: DAYS", where COURSE is the name of the course, X is the number of credit horus, and DAYS is the list of days that the lab meets.

Here’s an example of the usage:

cse164 = LabCourse("CSE 164", 4, "Suh Young Choi", ["CSE 163"], 
                   ["Tuesday", "Wednesday"], True)

print(cse164.get_name())          # CSE 164
print(cse164.get_credit_hours())  # 4
print(cse164.get_lab_days())      # ['Tuesday', 'Wednesday']
print(cse164.needs_materials())  # True
print(cse164)  # CSE 164 (4 credits) - Lab: Tuesday, Wednesday