What is a Graph?

Understand the basic definition of a graph.

We'll cover the following

Data structures

We use different types of data structures in our daily life. Recording test scores from school science experiments and keeping track of the number of steps taken on our smartwatch are a couple of instances in which storing data is necessary. We use numbers, strings, or a combination of both to build a database and use it later for analysis. Using a linear data structure, like an array or a simple list, is enough to handle the tasks in these examples.

Imagine a real-life situation in which we need to record and document a person’s social network with all the family, friends, and acquaintances from their entire life. This task is more complex than the one discussed before. It can get especially complex when dealing with relationships between an entity and multiple entities and the interrelationships between them.

Representing information like this using simple data structures is not intuitive and is usually challenging to understand. That is where nonlinear data structures such as graphs come into play. They make it easier to capture intricate details related to real-world, complex systems. Not just that, but we can easily collect, organize, build, and analyze information using graph data structures.

In the biological domain, we can apply graph structures to represent protein-protein interactions in which the nodes represent proteins and the edges represent the interactions between them. Similarly, we can apply the same idea to the representation of atoms and molecules as graph data. Telecommunications, geosciences, inventory management, and movie recommendation systems are some of the few areas where graph data structures are essential.

Graph

Let's look below at the formal definition of a graph:

Note: A graph is represented as G(V,E)G(V, E) where VV belongs to a set of vertices/nodes and EE belongs to a set of edges/links so that u∈Vu ∈ V, v∈Vv ∈ V, and (u,v)∈E(u,v) ∈ E.

Simply put, we have a set of nodes and a set of edges. Edges store the relationships between two nodes. For example, let four nodes be named as {a,b,c,d}, and their edges written as {ab, ac, bc, bd}. If we draw this example graph, it will look like the following:

Press + to interact
Example of a graph
Example of a graph

Properties

Some basic properties of graphs include:

  • Order: The total number of nodes in a graph.

  • Size: The total number of edges.

  • Degree of a node: The number of edges connected to the node.

  • Neighbors of a node: All the other nodes adjacent to the given node.

Graph visualization

We finished the basics of graph theory, so let's jump into the coding part. We provide code snippets to run and observe the output depending on the lesson.

For coding, we'll be using Python programming language and libraries such as NetworkX.

Look at the following code and click "Run" to execute. You'll see a visualization of the graph as output.

Press + to interact
import networkx as nx
import matplotlib.pyplot as plt
# create an instance of graph
G = nx.Graph()
# add nodes 
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
# add edges
G.add_edge(1, 2)
G.add_edge(1, 3)
G.add_edge(1,4)
# visualize graph
plt.figure()
nx.draw(G, with_labels=True, node_size=1000, font_size=30)

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

  • Line 5: We created an instance of graph G using the method nx.Graph().

  • Line 7–16: We added nodes and edges to the graph using the add_n​ode() and add_e​dge() methods.

This is a simple way to create graphs using the NetworkX Python library.

We can create random graphs using NetworkX too. For visualization purposes, consider the following random graph:

Press + to interact
import networkx as nx
import matplotlib.pyplot as plt
# random graph
G = nx.erdos_renyi_graph(100, 0.15)
# visualize graph
fig, ax = plt.subplots(figsize=(3, 2),dpi=300)
fig.patch.set_linewidth(1)
fig.patch.set_edgecolor('black')
nx.draw(G, with_labels=True, node_size=25,width=0.2, font_size=3)

The widgets below contain commands that can be used to retrieve the following properties:

  • The number of nodes

Press + to interact
import networkx as nx
G = nx.erdos_renyi_graph(100, 0.15)
number_of_nodes = nx.number_of_nodes(G)
print("Total number of nodes: ",number_of_nodes)

  • The number of edges

Press + to interact
import networkx as nx
G = nx.erdos_renyi_graph(100, 0.15)
number_of_edges = nx.number_of_edges(G)
print("Total number of edges: ",number_of_edges)

  • The degree of node 42

Press + to interact
import networkx as nx
G = nx.erdos_renyi_graph(100, 0.15)
degree = dict(nx.degree(G))
print("Type of variable: ",type(degree))
print("Degree of node 42: ",degree[42])

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

  • Line 4: The nx.degree() method retrieves a degree view mapping which can be converted to a dictionary. The corresponding degree to any node can be accessed through the dictionary.