Representations of graphs

A graph is a structure that represents data in terms of vertices and edges. A graph is represented as aGraph = (𝓥, 𝓔), where 𝓥 represents a set of vertices and 𝓔 represents a set of edges. Note that aGraph has |𝓥| vertices and |𝓔| edges.

A vertex, 𝓋 ∈ 𝓥, represents a real-world object, such as a person, a computer, or an activity. An edge, 𝓋 ∈ 𝓔, connects two vertices in a network:

e(𝓋₁, 𝓋₂) | e ∈ 𝓔 & 𝓋_i ∈ 𝓥

The preceding equation indicates that in a graph, all edges belong to a set, 𝓔, and all vertices belong to a set, 𝓥.

An edge connects two vertices and so represents a relationship between them. For example, it can represent the following relationships:

• Friendships between people
• A person connected to a friend on LinkedIn
• A physical connection of two nodes in a cluster
• A person attending a research conference

In this chapter, we will be using the networkx Python package to represent graphs. Let's try to create a simple graph using the networtx package in Python. To begin with, let's try to create an empty graph, aGraph, with no vertex or node:

import networkx as nx
G = nx.Graph()

Let's add a single vertex:

G.add_node("Mike")

 We can also add a bunch of vertices using a list:

G.add_nodes_from(["Amine", "Wassim", "Nick"])

We can also add one edge between the existing vertices, as shown:

G.add_edge("Mike", "Amine") 

Let's now print the edges and vertices:

Please note that if we are adding an edge, this also leads to adding the associated vertices, if they do not already exist, as shown here:

G.add_edge("Amine","Imran")

If we print the list of nodes, the following is the output that we observe:

Note that the request to add a vertex that already exists is silently ignored. The request is ignored or entertained based on the type of graph we have created.