19 Dynamic graph theory techniques for node ranking and social network analysis

 

This section covers

  • Finding the most central network locations
  • Clustering the connections in a network
  • Understanding social graph analysis

In the previous section, we investigated several types of graphs. We examined web pages connected by directed links and also a network of roads spanning multiple counties. In our analysis, we’ve mostly treated the network as frozen, static objects—we’ve counted neighboring nodes as though they were frozen clouds in a photograph. In real life, clouds are constantly in motion, and so are many networks. Most networks worth studying are perpetually buzzing with dynamic activity. Cars race across networks of roads, causing traffic congestion near popular towns. In that same vein, web traffic flows across the internet as billions of users explore the many web links. Our social networks are also flowing with activity as gossip, rumors, and cultural memes spread across tight circles of close friends. Understanding this dynamic flow can help uncover friend groups in an automated manner. Understanding the flow can also help us identify the most heavily trafficked web pages on the internet. Such modeling of dynamic network activity is critical to the function of many large tech organizations. In fact, one of the modeling methods presented in this section led to the founding of a trillion-dollar company.

19.1 Uncovering central nodes based on expected traffic in a network

19.1.1 Measuring centrality using traffic simulations

19.2 Computing travel probabilities using matrix multiplication

19.2.1 Deriving PageRank centrality from probability theory

19.2.2 Computing PageRank centrality using NetworkX

19.3 Community detection using Markov clustering

19.4 Uncovering friend groups in social networks

Summary