Network-Dynamics-and-Learning

Material for the laboratories of the Network Dynamics and Learning course for the MSc in Data Science and Engineering at Politecnico di Torino.

Contents

Lab00: Introduction to NetworkX

• Graph Types
• Drawing graphs
• Algorithms

Lab01: Algebraic Graph Theory

• Introduction to numpy
• Spectral graph theory
• Invariant probability distributions
• Centrality measures
• Visualizing centrality measures
• Testing centrality measures

Lab02: Network Flows

• Max Flow - Min Cut Theorem and the Ford Fulkerson algorithm
• Python implementation of the Edmonds-Karp Algorithm
• Network flows optimization with CVXPY

Lab03: Averaging Dynamics with Stubborn Agents

• Simulating the averaging dynamics with stubborn nodes
• Optimal placement of stubborn nodes

Lab04: Markov Chains

• Random Walks on graphs and the Flow Dynamics
• Discrete Time Markov Chains
  • Simulating DTMC
  • Computing and approximating invariant probability distributions
• Continuous Time Markov Chains
  • Modelling CTMC: two equivalent approaches
  • Simulating CTMC
  • Estimating invariant probability distributions
  • Katz Theorem: equivalence of spatial and time averages

Lab05: Game Theoretic Learning Processes

• Discrete-time asynchronous Best Response dynamics
  • D-T BRD as a random walk on the BR transition graph
  • Asymptotic behaviour and invariant probability distribution
  • BRD for non-potential games: the Rock-Scissor-Paper game
• Continuous-time asynchronous Best Response dynamics
  • C-T BRD for network games: the network coordination game
  • BRD for potential games: local optimization of the potential function
• Continuous-time asyncronous Noisy Best Response dynamics
  • C-T NBRD for network games: the network coordination game
  • NBRD for potential games: asymptotic behaviour and invariant probability distribution
  • Global optimization of the potential function and the effect of noise

Lab06: Epidemic Models on Networks - Random Graphs

• Pairwise Interacting Network Systems
• Epidemic models on networks: SI, SIS, SIR models
• Example: the SI model on a grid graph
  • Modelling and simulation of the infection spread
• Random graphs as a model for a real world citation network
  • approximation with the Erdos-Renyi-model
  • approximation with the configuration model
  • approximation with the preferential attachment model
  • Comparing models