We can classify graphs into several types depending on the use case or the context. Let's begin by taking a look at the following types.

Undirected graph

This is a simple graph in which the edges don't have a directed nature. In other words, E(u,v) = E(v,u); the links don't have a sense of direction and are considered the same when moved from node u to node v or from node v to node u. A social network of friends is an excellent example of an undirected graph in which nodes represent individuals, and the edges represent their friendship.

Press + to interact
An undirected graph
An undirected graph

Directed graph

A directed graph (or a digraph) is a graph in which the edges are ordered, and the flow of direction is well defined. In such a case, E(u,v) ≠ E(v,u).

In the example below, node A is called a head, and node B is called a tail. This nomenclature specifies the direction of the connection between the two nodes. Also, the presence of this sense of direction makes it necessary to add more details to the degree property of a node. Here, we introduce indegree and outdegree to mention the number of inward and outward connections to a node. For example, node A has two outdegrees and zero indegrees, whereas node B has one outdegree and one indegree.

A simple instance of a directed graph would be a network of Twitter followers in which the nodes are individual accounts and the edges are the follows. A person could follow Elon Musk, but Musk might not follow them back, making the connection one way. This adds a property to the edge, which is the direction of the relationship.

Press + to interact
A directed graph
A directed graph

Multigraph

This is a graph type that allows multiple edges or connections between the nodes. Imagine a transport graph with a few cities like Paris and London that act as nodes. The different possible travel routes between the two cities are the edges. This represents an instance of a multigraph, which can be directed or undirected.

Press + to interact
A multigraph
A multigraph

Single-relational graph

This is a graph in which the nodes and edges represent one type of property—for instance, the property of friendship in a social network graph.

Multi-relational graph

Here, we allow the nodes and edges to have multiple properties and coexist in the graph. A simple example would be a social network that represents different types of friends, like school and university friends. A knowledge graph, which we'll discuss in more detail later, is an excellent example of a multi-relational graph, and they are very popular nowadays.

Bipartite graph

As the name suggests, the nodes in the graph are divided into two groups. Check out the visualization of an example below:

Press + to interact
Bipartite graph
Bipartite graph

The two groups are shown in different colors. The groups can have any property, like football players, clubs, and so on.

Directed acyclic graphs

Also denoted as DAGs, the directed acyclic graphs have no directed cycles since the directed edges never form a closed loop. All tree-based graphs are DAGs.

Press + to interact
Directed acyclic graph
Directed acyclic graph

Weighted graph

In this type of graph, we use a function that assigns a weight to either a node or an edge. Subsequently, graphs like these are called node-weighted graphs or edge-weighted graphs.

Press + to interact
An edge-weighted directed graph
An edge-weighted directed graph

Note: A given graph can be a mixture of multiple types mentioned above. We could build a graph that’s edge-weighted, directed, and multi-relational all at the same time.

Graph visualization

Let's see a code that makes a directed graph (or a DiGraph) using NetworkX.

Press + to interact
import networkx as nx
import matplotlib.pyplot as plt
# create an instance of graph
G = nx.DiGraph()
# add nodes from a list
G.add_nodes_from([1, 2, 3, 4])
# add edges from a list
G.add_edges_from([(1, 2), (1, 3), (1, 4)])
# visualize graph
plt.figure()
nx.draw(G, with_labels=True, node_size=1000, font_size=30, arrowsize=30)

Let’s have a look at the code explanation below:

  • Line 5: We use an nx.DiGraph() instance to generate a directed graph.

  • Lines 8–11: Instead of adding nodes one by one, we can use the add_nodes_from() and add_edges_from() methods to input a list directly.

There are methods in the NetworkX library that can be used to check if a graph is directed or weighted.

Let's run the following code to check if the graph is directed:

Press + to interact
import networkx as nx
G = nx.erdos_renyi_graph(100, 0.15)
print("The graph is directed: ",nx.is_directed(G))

Let's run the following code to check if the graph is weighted.

Press + to interact
import networkx as nx
G = nx.erdos_renyi_graph(100, 0.15)
print("The graph is weighted: ",nx.is_weighted(G))