# Networks and graphs, theory thereof

November 24, 2014 — October 20, 2021

clustering
dynamical systems
networks
topology

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

• 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”, I saw Mikhael Isaev present on work with Brendan McKay and Catherine Greenhill ) 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.

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

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?

## 8 Incoming

• Suddenly planar graphs seem interesting

## 9 References

Achlioptas, Clauset, Kempe, et al. 2005. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing. STOC ’05.
Akyildiz, Su, Sankarasubramaniam, et al. 2002. Communications Magazine, IEEE.
Albert, Jeong, and Barabási. 2000. Nature.
Barrat, and Weigt. 2000. The European Physical Journal B-Condensed Matter and Complex Systems.
Belkin, and Niyogi. 2003. Neural Computation.
Borgs, Chayes, Cohn, et al. 2014a. arXiv:1401.2906 [Math].
———, et al. 2014b. arXiv:1408.0744 [Math].
Bullmore, and Sporns. 2009. Nature Reviews Neuroscience.
Caldarelli, G., Capocci, De Los Rios, et al. 2002. Physical Review Letters.
Caldarelli, Guido, Chessa, Pammolli, et al. n.d. Nature Physics.
Callaway, Newman, Strogatz, et al. 2000. Physical Review Letters.
Carlsson. 2009. Bulletin of the American Mathematical Society.
Carlsson, Ishkhanov, Silva, et al. 2008. International Journal of Computer Vision.
Clauset, Newman, and Moore. 2004. Physical Review E.
Cohen, Erez, ben-Avraham, et al. 2000. Physical Review Letters.
———, et al. 2001. Physical Review Letters.
Cohen, and Havlin. 2003. Physical Review Letters.
Cohen-Steiner, Edelsbrunner, and Harer. 2007. Discrete & Computational Geometry.
Coscia. 2020. “Generalized Euclidean Measure to Estimate Network Distances.”
Cranmer, Desmarais, and Morgan. 2021. Inferential network analysis.
Daneshmand, Gomez-Rodriguez, Song, et al. 2014. In ICML.
De Domenico, Solé-Ribalta, Cozzo, et al. 2013. Physical Review X.
Defferrard, Bresson, and Vandergheynst. 2016. In Advances In Neural Information Processing Systems.
Diaconis, and Stroock. 1991. The Annals of Applied Probability.
Doyle, Alderson, Li, et al. 2005. Proceedings of the National Academy of Sciences of the United States of America.
Easley, and Kleinberg. 2010. Networks, Crowds, and Markets: Reasoning about a Highly Connected World.
Edelsbrunner, Letscher, and Zomorodian. 2002. Discrete & Computational Geometry.
Erdős, and Rényi. 1959. Publ. Math. Debrecen.
Feld. 1991. American Journal of Sociology.
Fortunato, and Newman. 2022. Nature Physics.
Fosdick, Larremore, Nishimura, et al. 2016. arXiv:1608.00607 [Physics, q-Bio, Stat].
Foster, Foster, Grassberger, et al. 2010. Proceedings of the National Academy of Sciences.
Galbiati, Delpini, and Battiston. n.d. Nature Physics.
Garcia, Mavrodiev, and Schweitzer. 2013. In Proceedings of the First ACM Conference on Online Social Networks. COSN ’13.
Garcia, Mendez, Serdült, et al. 2012. In Proceedings of the First Edition Workshop on Politics, Elections and Data. PLEAD ’12.
Garlaschelli, Ahnert, Fink, et al. 2013. Entropy.
Ghrist. 2008. Bulletin of the American Mathematical Society.
Gilbert. 1959. The Annals of Mathematical Statistics.
Glasscock. 2016. arXiv:1611.00718 [Math].
Gómez, Díaz-Guilera, Gómez-Gardeñes, et al. 2013. Physical Review Letters.
Granovetter, Mark S. 1973. The American Journal of Sociology.
Granovetter, Mark. 1983. Sociological Theory.
Greenhill, Isaev, Kwan, et al. 2016. arXiv:1606.01586 [Math].
Green, and Shalizi. 2017. arXiv:1711.00813 [Stat].
Holme, and Saramäki. 2012. Physics Reports, Temporal Networks,.
Isaev, and McKay. 2016. arXiv:1604.08305 [Math].
Iyer, Liu, Jin, et al. 2018. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18).
Kac. 1966. American Mathematical Monthly.
Karsai, Kivelä, Pan, et al. 2011. Physical Review E.
Kaushik, and Battiston. 2013. PLoS ONE.
Kim, and Leskovec. 2012. Internet Mathematics.
Kipf, and Welling. 2016. In arXiv:1609.02907 [Cs, Stat].
Klein, and Randić. 1993. Journal of Mathematical Chemistry.
Koenig, Battiston, Napoletano, et al. 2008. SSRN Scholarly Paper ID 1271877.
König, Battiston, Napoletano, et al. 2011. Journal of Economic Behavior & Organization.
König, Battiston, Napoletano, et al. 2012. Games and Economic Behavior.
Kramer, Guillory, and Hancock. 2014. Proceedings of the National Academy of Sciences.
Kurtz. 1970. Journal of Applied Probability.
Lei. 2014. arXiv:1412.4857 [Math, Stat].
Lovász. 2012. Large Networks and Graph Limits.
Madar, Kalisky, Cohen, et al. 2004. The European Physical Journal B.
Mahoney. 2016. arXiv Preprint arXiv:1608.04845.
McKay, and Wormald. 1990. European Journal of Combinatorics.
Milgram. 1967. Psychology Today.
Miorandi, and De Pellegrini. 2010. In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th International Symposium on.
Molloy, and Reed. 1995. Random Structures & Algorithms.
Newman. 2003. Physical Review E.
———. 2004. Physical Review E.
———. 2006. Proceedings of the National Academy of Sciences.
Newman, and Girvan. 2004. Physical Review E.
Newman, Strogatz, and Watts. 2001. Physical Review E.
Noh. 2004. Physical Review Letters.
Odlyzko. 1995. In Handbook of Combinatorics (Vol. 2).
Olfati-Saber, Fax, and Murray. 2007. Proceedings of the IEEE.
Orbanz, and Roy. 2015. IEEE Transactions on Pattern Analysis and Machine Intelligence.
Otasek, Morris, Bouças, et al. 2019. Genome Biology.
Pan, Zhang, Wu, et al. 2014. PLoS ONE.
Pastor-Satorras, and Vespignani. 2002. Physical Review E.
Perony, Pfitzner, Scholtes, et al. 2013. Advances in Complex Systems.
Petri, Scolamiero, Donato, et al. 2013a. In Proceedings of the European Conference on Complex Systems 2012. Springer Proceedings in Complexity.
———, et al. 2013b. PLoS ONE.
Pfitzner, Scholtes, Garas, et al. 2013. Physical Review Letters.
Pinto, Thiran, and Vetterli. 2012. Physical Review Letters.
Pons, and Latapy. 2005. In Computer and Information Sciences - ISCIS 2005. Lecture Notes in Computer Science 3733.
Pouget-Abadie, and Horel. 2015. In Proceedings of The 32nd International Conference on Machine Learning.
Protter. 1987. Siam Review.
Rapoport. 1953a. The Bulletin of Mathematical Biophysics.
———. 1953b. The Bulletin of Mathematical Biophysics.
———. 1954. The Bulletin of Mathematical Biophysics.
———. 1957. The Bulletin of Mathematical Biophysics.
Richardson, Perony, Tessone, et al. 2013. arXiv:1311.1417 [q-Bio].
Rosvall, and Bergstrom. 2008. Proceedings of the National Academy of Sciences.
Sarigol, Garcia, and Schweitzer. 2014. In Proceedings of the Second ACM Conference on Online Social Networks. COSN ’14.
Scholtes, Wider, Pfitzner, et al. 2013. arXiv:1307.4030 [Cond-Mat, Physics:physics].
Schweitzer, Fagiolo, Sornette, et al. 2009. Science.
Seshadhri, Sharma, Stolman, et al. 2020. Proceedings of the National Academy of Sciences.
Shannon, Markiel, Ozier, et al. 2003. Genome Research.
Smith, and Novella. 2007. PLoS Med.
Solé-Ribalta, De Domenico, Kouvaris, et al. 2013. Physical Review E.
Stegehuis, van der Hofstad, and van Leeuwaarden. 2016. Scientific Reports.
St-Onge, Thibeault, Allard, et al. 2020. arXiv:2003.05924 [Nlin, Physics:physics].
Streater. 2000. arXiv:math-Ph/0002049.
Tang, Athreya, Sussman, et al. 2014. arXiv:1409.2344 [Math, Stat].
Tetali. 1991. Journal of Theoretical Probability.
Tomasello, Napoletano, Garas, et al. 2013. arXiv:1304.3623 [Physics].
Veitch, and Roy. 2015. arXiv:1512.03099 [Cs, Math, Stat].
Verma. 2014. Proceedings of the National Academy of Sciences.
Watts, and Strogatz. 1998. Nature.
Yang, Long, Smola, et al. 2011. In Proceedings of the 20th International Conference on World Wide Web. WWW ’11.
Zanette. 2008. Nature.
Zhou, Xian Y. 1993. Journal of Theoretical Probability.
Zhou, XueZhong, Menche, Barabási, et al. 2014. Nature Communications.
Zomorodian, and Carlsson. 2005. Discrete & Computational Geometry.
Zuev, Boguna, Bianconi, et al. 2015. Scientific Reports.