18 An introduction to graph theory and network analysis

 

This section covers

  • Representing diverse datasets as networks
  • Network analysis with the NetworkX library
  • Optimizing travel paths in a network

The study of connections can potentially yield billions of dollars. In the 1990s, two graduate students analyzed the properties of interconnected web pages. Their insights led them to found Google. In the early 2000s, an undergraduate began to digitally track connections between people. He went on to launch Facebook. Connection analysis can lead to untold riches, but it can also save countless lives. Tracking the connections between proteins in cancer cells can generate drug targets that will wipe out that cancer. Analyzing connections between suspected terrorists can uncover and prevent devious plots. These seemingly disparate scenarios have one thing in common: they can be studied using a branch of mathematics called network theory by some and graph theory by others.

18.1 Using basic graph theory to rank websites by popularity

18.1.1 Analyzing web networks using NetworkX

18.2 Utilizing undirected graphs to optimize the travel time between towns

18.2.1 Modeling a complex network of towns and counties

18.2.2 Computing the fastest travel time between nodes

Summary