Introduction to Graph Theory 101
Graphs are composed of primary objects called nodes and the relationship among objects called edges. In addition, graphs can be directed or undirected depending on the relations between nodes and the nature of the edges.
Nodes and Edges
Nodes and Edges are two primary objects in Graph Theory: Nodes are circles and represent some entity such as person, places, or webpages, or businesses. Edges represent the relationships between entities. In the graph above, Thoa is well connected to every single character on this graph. Whereas Amber is the least connected. She only connects to Thoa.
Directed vs Undirected Graphs
Figure 1 above depicts an undirected graph. The edges in an undirected graph represent a mutual connection between two nodes. There is mutual connection between Thoa and Maia, Thoa and Sydney, as well as between Maia and Sydney. The mutual relationship can be described as ‘Friends’ on ‘Facebook’ or ‘Connections’ on LinkedIn.
Figure 2 below depicts a directed graph. Each of the edges has an arrow indicating a direction. Depending on the direction of the arrow, one can say that there is a mutual relationship between nodes or it is just a one side relationship such as a LinkedIn member following anothers in order to stay up to date with his/her activities. On the graph below (fig.2) Thoa and Joy follow Ann and Maia. Ann doesn’t follow anyone. The relationship between Thoa and Amber is mutual. They both follow each other.
Connectedness
Connectedness is the number of edges connected to a node. In fig.1 — undirected graph, Thoa is well connected to everyone. The whole purpose of a graph is to find out who is the most influential person in a circle of friends. Joy follows everyone in the friends circle except Amber, and thus she is a follower and we -business analysts will not focus on her. Thoa has three followers out of five friends. She can be an influencer. From what we learn from her: her spending, book choices, clothing, types of credit card use… we may have known something about her friends on this graph. This is what Amazon Recommended System does to recommend services, goods based on the purchasing history and influencers.
Path Searching
The purpose of the path searching system is to find the shortest distance between two nodes. The longer the edge between two nodes, the weaker the relationship between them. Path searching systems also focus on the least steps a customer has gone through before completing an order on the website. The shortest the path, the stronger the relations between two nodes — entities, and the quicker the purchasing process.
Graph Theory: Simple and Shortest Paths using NetworkX
# import packages
import networkx as nx
import numpy as np
%matplotlib inline# Generated network
G = nx.navigable_small_world_graph(3, seed=3)
G = nx.relabel_nodes(G, dict(zip(G.nodes, ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])))
nx.draw(G, pos=nx.random_layout(G, seed=9), with_labels=True, node_color='#1cf0c7',node_size=500, font_weight='bold', width=2, alpha=0.8)
# Check if there is a path between two nodes
In [3] nx.has_path(G, ‘F’, ‘G’)
Out [3] True# Check if there is a path between two nodes
In [3] nx.has_path(G, ‘F’, ‘G’)
Out [3] True# Find the shortest path
In [4] nx.shortest_path(G, ‘F’, ‘G’]
Out[4] [ ‘F’ , ‘I’ , ‘G’]# Access the length of the shortest path
In [5] nx.shortest_path_lenght(G, ‘F’, ‘G’)
Out[5] 2# Access the edges
In[6] G.edges
Out[6]
# Retrieving a specific edge
In[7] G.edges[(‘F’, ‘E’)]
Out[7] { }# Retrieving outbound connections for a given node
In[8] G[‘F’]
Out[8] AtlasView( {‘A’: { } , ‘E’: { }, ‘G’: { }, ‘F’: { } })
# Coloring different edge
Summary
In this introduction to graph theory, you have learned two primary objects are nodes and edges, and the undirected or directed relationships among nodes. You are also exploring the fundamental concepts of paths in networks. Using built-in packages of networkX, you can create a network, find nodes, edges, and build a network of your choices.
