A Tutorial on Information Flow in Directed Graphs

About

The goal of this tutorial is familiarizing the student with the notions of information flow in graphs. In particular, it will be considered the processes of consensus and diffusion on directed graphs.

• Different graph types: directed, undirected, multigraph, (spanning) trees, k-partite graphs.
• Elementary notions of graph theory: subgraph, induced graph, cycles, paths, walks, in- and out-degree, neighborhood. Euler and Hamilton cycles. Notions of connectedness for digraphs.
• Equivalence classes and partition into strong components. Condensation and “topological” ordering. Different types of adjacency matrices and of Laplacians for directed and undirected graphs.
• Basic Linear Algebra: Statements of Perron-Frobenius theorem and Jordan normal form. Relations between eigenvalues and eigenvectors of the Laplacian. Relation between spectrum and graph structure.
• Discussion of direction of arrows in digraphs. Definitions of consensus and diffusion. Linear differential equations and exponential of matrix. Relation between discrete and continuous processes.
• Characterization of the right and left kernel of the Laplacian. Asymptotics of consensus and diffusion in terms of these kernels. Consensus and diffusion are duals.
• The pagerank algorithm as a diffusion type algorithm. Pagerank as a consensus type algorithm.
• Related topics in the social sciences.

Prof. J. J. P. Veerman (Portland State University) will be the main speaker of the tutorial, covering most of the topics outlined above. Prof. Mario Eboli (Università “G. d’Annunzio”) will discuss the applications of graph theory and flow network theory to the modelling of direct contagion phenomena in financial markets. Prof. Luca Moscardelli (Università “G. d’Annunzio”) will present an overview of the studies on the coevolutionary and aggregation-based opinion formation processes in social networks.

Course leader

Prof. J. J. P. Veerman (Portland State University)

Target group

Postgraduate and advanced undergraduate students in mathematics, computer science or economics.

Course aim

The goal of this tutorial is familiarizing the student with the notions of information flow in graphs. In particular, it will be considered the processes of consensus and diffusion on directed graphs.