THE-SAS-MOM
Follow Us:
  • Welcome
  • About SAS-Mom
  • SAS Blog
  • Typical SAS Interview Questions
  • SAS Certifications
  • Python Blog
  • Contact SAS-Mom

GRAPH THEORY AND NETWORK ANALYSIS

27/7/2019

0 Comments

 
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.
Picture
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.
Picture
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
Picture
STEP 2 - DEFINE FUNCTIONS
Picture
STEP 3 - READ THE AIRPORT DATASET
Picture
STEP 4 - PREPROCESS THE DATASET
Picture
STEP 5 - GENERATE UNDIRECTED GRAPH
Picture
STEP 6 - CALCULATE THE DEGREE OF EACH NODE
Picture
STEP 7 - CALCULATE THE DEGREE CENTRALITY OF EACH NODE
Picture
STEP 8 - CALCULATE THE CLOSENESS CENTRALITY OF EACH NODE
Picture
STEP 9 - CALCULATE THE BETWEENNESS CENTRALITY OF EACH NODE
Picture
STEP 10 - CALCULATE THE EIGENVALUE CENTRALITY OF EACH NODE
Picture
STEP 11 - CALCULATE THE PAGERANK OF EACH NODE
Picture
STEP 12 - CALCULATE THE NETWORK DENSITY
Picture
STEP 13 - CALCULATE THE NETWORK ECCENTRICITY, DIAMETER AND RADIUS
Picture
STEP 14 - CALCULATE THE NETWORK TRANSITIVITY
Picture
STEP 15 - CALCULATE THE NETWORK ASSORTATIVITY
Picture
STEP 16 - CALCULATE THE AVERAGE SHORTEST PATH OF THE NETWORK
Picture
STEP 17 - CONNECTED COMPONENTS
Picture
STEP 18 - CENTER AND PERIPHERY OF GRAPH 
Picture
STEP 19 - DEGREE DISTRIBUTION AND HISTOGRAM 
Picture
Picture
STEP 20 - DRAW THE ENTIRE GRAPH
Picture
Picture
STEP 21 - EGO-CENTRIC ANALYSIS AT A PARTICULAR NODE
Picture
Picture
Picture
Picture
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.
0 Comments



Leave a Reply.

    Author

    My name is Vanessa Afolabi also known as @TheSASMom. I am a Data Scientist fluent in SAS, R, Python and SQL with a passion for Machine Learning and Research.

    Archives

    July 2019
    January 2019

    Categories

    All

    RSS Feed

Powered by Create your own unique website with customizable templates.