# Networks and graphs, theory thereof

November 24, 2014 — October 20, 2021

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.

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

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

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?

### 6.1 Stochastic Petri Nets

- David A. Tanzer on Petri net programming
- John Baez’s current stochastic Petri network work

## 7 Graph software

## 8 Incoming

Suddenly planar graphs seem interesting

## 9 References

*Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing*. STOC ’05.

*Communications Magazine, IEEE*.

*Nature*.

*Bernoulli*.

*The European Physical Journal B-Condensed Matter and Complex Systems*.

*Neural Computation*.

*arXiv:1401.2906 [Math]*.

*arXiv:1408.0744 [Math]*.

*Nature Reviews Neuroscience*.

*Physical Review Letters*.

*Nature Physics*.

*Physical Review Letters*.

*Bulletin of the American Mathematical Society*.

*International Journal of Computer Vision*.

*Physical Review E*.

*Physical Review Letters*.

*Physical Review Letters*.

*Physical Review Letters*.

*Discrete & Computational Geometry*.

*Inferential network analysis*.

*ICML*.

*Physical Review X*.

*Advances In Neural Information Processing Systems*.

*The Annals of Applied Probability*.

*Proceedings of the National Academy of Sciences of the United States of America*.

*Networks, Crowds, and Markets: Reasoning about a Highly Connected World*.

*Discrete & Computational Geometry*.

*Publ. Math. Debrecen*.

*American Journal of Sociology*.

*Nature Physics*.

*arXiv:1608.00607 [Physics, q-Bio, Stat]*.

*Proceedings of the National Academy of Sciences*.

*Nature Physics*.

*Proceedings of the First ACM Conference on Online Social Networks*. COSN ’13.

*Proceedings of the First Edition Workshop on Politics, Elections and Data*. PLEAD ’12.

*Entropy*.

*Bulletin of the American Mathematical Society*.

*The Annals of Mathematical Statistics*.

*arXiv:1611.00718 [Math]*.

*Physical Review Letters*.

*The American Journal of Sociology*.

*Sociological Theory*.

*arXiv:1606.01586 [Math]*.

*arXiv:1711.00813 [Stat]*.

*Physics Reports*, Temporal Networks,.

*arXiv:1604.08305 [Math]*.

*13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)*.

*American Mathematical Monthly*.

*Physical Review E*.

*PLoS ONE*.

*Internet Mathematics*.

*arXiv:1609.02907 [Cs, Stat]*.

*Journal of Mathematical Chemistry*.

*Journal of Economic Behavior & Organization*.

*Games and Economic Behavior*.

*Proceedings of the National Academy of Sciences*.

*Journal of Applied Probability*.

*arXiv:1412.4857 [Math, Stat]*.

*Large Networks and Graph Limits*.

*The European Physical Journal B*.

*arXiv Preprint arXiv:1608.04845*.

*European Journal of Combinatorics*.

*Psychology Today*.

*Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th International Symposium on*.

*Random Structures & Algorithms*.

*Physical Review E*.

*Physical Review E*.

*Proceedings of the National Academy of Sciences*.

*Physical Review E*.

*Physical Review E*.

*Physical Review Letters*.

*Handbook of Combinatorics (Vol. 2)*.

*Proceedings of the IEEE*.

*IEEE Transactions on Pattern Analysis and Machine Intelligence*.

*Genome Biology*.

*PLoS ONE*.

*Physical Review E*.

*Advances in Complex Systems*.

*Proceedings of the European Conference on Complex Systems 2012*. Springer Proceedings in Complexity.

*PLoS ONE*.

*Physical Review Letters*.

*Physical Review Letters*.

*Computer and Information Sciences - ISCIS 2005*. Lecture Notes in Computer Science 3733.

*Proceedings of The 32nd International Conference on Machine Learning*.

*Siam Review*.

*The Bulletin of Mathematical Biophysics*.

*The Bulletin of Mathematical Biophysics*.

*The Bulletin of Mathematical Biophysics*.

*The Bulletin of Mathematical Biophysics*.

*arXiv:1311.1417 [q-Bio]*.

*Proceedings of the National Academy of Sciences*.

*Proceedings of the Second ACM Conference on Online Social Networks*. COSN ’14.

*arXiv:1307.4030 [Cond-Mat, Physics:physics]*.

*Science*.

*Proceedings of the National Academy of Sciences*.

*Genome Research*.

*PLoS Med*.

*Physical Review E*.

*Scientific Reports*.

*arXiv:2003.05924 [Nlin, Physics:physics]*.

*arXiv:math-Ph/0002049*.

*arXiv:1409.2344 [Math, Stat]*.

*Journal of Theoretical Probability*.

*arXiv:1304.3623 [Physics]*.

*arXiv:1512.03099 [Cs, Math, Stat]*.

*Proceedings of the National Academy of Sciences*.

*Nature*.

*Proceedings of the 20th International Conference on World Wide Web*. WWW ’11.

*Nature*.

*Journal of Theoretical Probability*.

*Nature Communications*.

*Discrete & Computational Geometry*.

*Scientific Reports*.