# Networks and graphs, theory thereof

Abstract networks[#]_ as in the bridges of Kaliningrad, graph theory and so on. the prevalence of online social networks in modern life leads us to naturally think of those, but networks provide a natural substrate for a bunch of processes, and passing backwards and forwards between linear-algebraic formalisms and graph formalisms can illuminate both.

To learn:

• specific graph counting based on generating functions (which is a “spectral” method but not normally what one means by spectral methods.)

• esp. use of approximating Fourier inversion/Cauchy path integrals. (the “asymptotic enumeration method”, McWo90, Odly95) I just saw Mikhael Isaev present on work with Brendan McKay and Catherine Greenhill (IsMc16a) on an interesting construction here based on concentration and complex martingales, which was surprisingly elementary, and constructed some complex martingales based on novel concentration equality based on complex generalisation of McDiarmid and Catoni type concentration inequalities. (IsMc16b)
• What graph theory gets us in understanding factor graphs and other graphical models.

• Relationship between graph theory and clustering, similarity metrics, dimensionality reduction.

• Spectral methods, which is to say least “graph Laplacian” ones. (For that see also matrix factorisation.)

• “Pagerank” et al. See Iterative reputation methods

• graphons and graphexes

• “Persistent Homology” - what is that?

To not mention:

• “Modularity” without domain-specific notion of modularity.

• Small world/scale-free/Erdős–Rényi, which are covered to the point of suffocation.

## Spectral methods

• Or take the Fourier transform and also learn some stuff.

• Kirchhoff's Theorem gives us, roughly, that the number of spanning trees in a graph is equal to the determinant of any cofactor of the graph Laplacian matrix (where a cofactor is a matrix with row and column $i$ deleted). Wow.

## Dynamic graphs

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

## 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.

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:

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

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?

### Interaction nets

What are these?

If you add in probability, are they the same as stochastic Petri nets?

## Graph software

Graph computation