GRAPH THEORY AND NETWORK ANALYSIS

WHAT IS GRAPH THEORY AND NETWORK ANALYSIS

Graph Theory is the mathematical study of the properties and applications of graphs. Graphs are mathematical structures used to model pairwise relations between objects. Graphs are also referred to as networks and contain a set of vertices/nodes/points connected by edges/links/lines.

Graph Theory can be applied to Network Analysis, Link Analysis and Social Network Analysis. These types of analysis borrow notations from Graph Theory and are focused on investigating social structures represented as networks, by applying a variety of mathematical, computational and statistical techniques.

HISTORY OF GRAPH THEORY

Graph Theory was first introduced and studied in 1736 by Leonhard Euler who was interested in solving the Konigsberg Bridge Problem. Konigsberg was a city in Prussia, Russia with the river Pregel flowing through it creating two islands. The city and islands were connected by seven bridges. The goal of the Konigsberg Bridge Problem was to devise a walk through the city that would cross each of the 7 bridges once and only once with no doubling back, ensuring that you ended where you started.

Leonhard Euler's work with Graph Theory was used to prove that the Konigsberg Bridge Problem was unsolvable. More notable names in the evolution and growth of Graph Theory are A.F Mobius (1840), Gustav Kirchhoff (1845), H.Dudeney (1913) and Heinrich (1969), among others. 

NETWORKX

One way of utilizing Graph Theory in Network Analysis is by using a powerful python library called NetworkX. NetworkX is a python language software package and an open-source tool for the creation, manipulation and study of the structure, dynamics and functions of complex networks.

EXAMPLE APPLICATION OF NETWORK ANALYSIS USING GRAPH THEORY - AIRPORT DATA

The following python code will provide an in depth illustration of how Graph Theory can be used in Network Analysis. It will be applied to Airport Data where the nodes are Airport Abbreviations and the edges represent the Distance between those Airports. 

STEP 1 - IMPORT LIBRARIES

STEP 2 - DEFINE FUNCTIONS

STEP 3 - READ THE AIRPORT DATASET

STEP 4 - PREPROCESS THE DATASET

STEP 5 - GENERATE UNDIRECTED GRAPH

STEP 6 - CALCULATE THE DEGREE OF EACH NODE

STEP 7 - CALCULATE THE DEGREE CENTRALITY OF EACH NODE

STEP 8 - CALCULATE THE CLOSENESS CENTRALITY OF EACH NODE

STEP 9 - CALCULATE THE BETWEENNESS CENTRALITY OF EACH NODE

STEP 10 - CALCULATE THE EIGENVALUE CENTRALITY OF EACH NODE

STEP 11 - CALCULATE THE PAGERANK OF EACH NODE

STEP 12 - CALCULATE THE NETWORK DENSITY

STEP 13 - CALCULATE THE NETWORK ECCENTRICITY, DIAMETER AND RADIUS

STEP 14 - CALCULATE THE NETWORK TRANSITIVITY

STEP 15 - CALCULATE THE NETWORK ASSORTATIVITY

STEP 16 - CALCULATE THE AVERAGE SHORTEST PATH OF THE NETWORK

STEP 17 - CONNECTED COMPONENTS

STEP 18 - CENTER AND PERIPHERY OF GRAPH 

STEP 19 - DEGREE DISTRIBUTION AND HISTOGRAM 

STEP 20 - DRAW THE ENTIRE GRAPH

STEP 21 - EGO-CENTRIC ANALYSIS AT A PARTICULAR NODE

CONCLUSION
NetworkX is a powerful python library that can be used to experiment with Graph Theory and Network Analysis. It is a strong tool for studying the connections between nodes and can be used to derive statistics that pull out useful information about the structure, distribution and dynamic of a Graph.