Networks and graphs, theory thereof

1 To learn: basic

• What graph theory gets us in understanding factor graphs and other graphical models.
• Relationship between graph theory and clustering, similarity metrics, dimensionality reduction.
• signal processing on graphs. (For that see also matrix factorisation.)
• “Pagerank” et al. See Iterative reputation methods
• graphons and graphexes (Cosma’s intro)
• “Persistent Homology” — what is that?

2 To learn: advanced

• specific graph counting based on generating functions (which is a “spectral” method but not normally what one means by spectral methods.)
• use of approximating Fourier inversion/Cauchy path integrals. (the “asymptotic enumeration method”, (McKay and Wormald 1990; Odlyzko 1995) I saw Mikhael Isaev present on work with Brendan McKay and Catherine Greenhill (Greenhill et al. 2016; Isaev and McKay 2016)) on an interesting construction based on concentration and complex martingales, which was surprisingly elementary, using a novel concentration equality based on complex generalisation of McDiarmid and Catoni type concentration inequalities. Lots of fancy keywords in there.

3 Spectral methods

See signal processing on graphs.

4 Dynamic graphs

e.g. Volodymyr Miz, Kirell Benzi, Benjamin Ricaud, and Pierre Vandergheynst, Wikipedia graph mining: dynamic structure of collective memory.

5 As a topology for other processes

It’s not just nodes and edges and possibly a probability distribution over the occurrence of each. Networks are presumably interesting because they provide a topology upon which other processes occur. And the interaction between this theory and pure driven topology is much more complex and rich. Such models include circuit diagrams, probabilistic graphical models, neural networks, contagion processes reaction networks and others.

John Baez:

Scientists and engineers use diagrams of networks in many different ways. The Azimuth Project is investigating these, using the tools of modern mathematics. You can read articles about our research here:

• Parts 1-26: Chemical reaction networks and Petri nets.

• Parts 27-: Electrical circuits and control theory.

…You can watch 4 lectures, an overview of network theory, here:

• Network theory: Oxford talks.

For now, I’m interested in conductance in electrical networks, random walks on graphs and the connection betwixt them. Where can I find out more about that? And how about the connection from those to harmonic functions?

6 Graph software

See Graph computation

7 Incoming

• Suddenly planar graphs seem interesting

  • Kuratowski’s theorem
  • Planar graph

8 References