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
• “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 Graphons

One continuous limit of graphs is the graphon, which is a function on the unit square mapping to the unit interval, giving, in a certain sense, the probability of an edge between two nodes. This is a way of thinking about the limit of a sequence of graphs, and is a way of thinking about the limit of a graph as it gets very large.

• Graphons and graphexes (Cosma’s intro)

It is not to me very intuitive, and the reason for that might be that it doesn’t capture what I intuitively want a graph limit to capture, in that connectivity in graphs that I care about is given by covariates, not by an apparently arbitrary axis index.

6 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?

7 Graph software

See Graph computation

8 Incoming

• Suddenly planar graphs seem interesting

  • Kuratowski’s theorem
  • Planar graph

9 References