A Simple & Essential Introduction To Graphs

A short, easy, but essential introduction to Graphs to help you ace them.

Graphs are extensively used in modern systems and applications.

• Social media networks like LinkedIn and Facebook use them to model people and their relationships to others.

• Search engines like Google use them as Knowledge Graphs to compile factual information.

• Platforms like Netflix and Spotify use them to build Recommendation systems.

• Package managers pip and npm use them for dependency management.

• Banks use them in their fraud detection algorithms.

• Google Maps uses them for efficient navigation and routing.

• They are used as Graph neural networks for drug discovery and protein analysis.

• LLMs use them for better information retrieval during response generation in a system called GraphRAG.

If you’re a software or ML engineer, you will most probably work with them during your career.

Here is a short, easy, but essential introduction to Graphs to help you ace them.

---

What is a Graph?

A Graph is a data structure that has two main components:

• Vertices or Nodes: that represent individual data points

• Edges: Connections between the Vertices or Nodes

For example, in a graph representing a social network, the vertices are individuals, and the edges represent relationships between them (friendship, spousal, etc.).

Graph visualised (Image from author’s book titled “Computer Science In 100 Images”)

A graph can be classified into different types based on multiple characteristics.

1. Based on Direction

• Directed graph
  In this type of graph, edges have a direction that indicates the flow of the relationship between the vertices they connect.
  For example, follower connections on Twitter, where a user follows another user in a one-way relationship.

• Undirected graph: Edges do not have direction in this type of graph, and connections go both ways.
  For example, a Facebook friend connection that connects two individuals who are friends.

2. Based on Edge Weights

• Weighted graph
  Edges in this type of graph have a weight associated with them, which tells the strength of the relationship between vertices.
  For example, edge weights in a social network graph can represent the number of times two individuals communicate in a day.

• Non-weighted graph
  All edges are equally weighted in this type of graph, representing only the presence or absence of a relationship.
  For example, a graph of individuals related by the music they listen to.

3. Based on the Presence of Cycles

• Cyclic graph
  Loops exist between graph vertices in this type of graph. For example, a graph representing road networks in cities with roundabouts.

• Acyclic graph
  No loops exist between the graph vertices in this type of graph.

4. Based on the Connectivity Between All Vertices

• Connected graph
  A path between every pair of vertices in this type of graph.
  For example, a graph representing a subway network within a single city.

• Disconnected graph
  There is at least one pair of vertices for which no path exists between them in this type of graph.

Apart from these, there are three other graph types that you might encounter and must know about.