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”, (McKay and Wormald 1990; Odlyzko 1995) I just saw Mikhael Isaev present on work with Brendan McKay and Catherine Greenhill (Greenhill et al. 2016; Isaev and McKay 2016)) 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.
  • 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

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.

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:

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

Stochastic Petri Nets

Interaction nets

What are these?

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

Graph software

Graph computation

Achlioptas, Dimitris, Aaron Clauset, David Kempe, and Cristopher Moore. 2005. “On the Bias of Traceroute Sampling: Or, Power-Law Degree Distributions in Regular Graphs.” In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, 694–703. STOC ’05. New York, NY, USA: ACM.

Akyildiz, Ian F., Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci. 2002. “A Survey on Sensor Networks.” Communications Magazine, IEEE 40 (8): 102–14.

Albert, Reka, Hawoong Jeong, and Albert-László Barabási. 2000. “Error and Attack Tolerance of Complex Networks.” Nature 406 (6794): 378–82.

Aldous, David J. 1999. “Deterministic and Stochastic Models for Coalescence (Aggregation and Coagulation): A Review of the Mean-Field Theory for Probabilists.” Bernoulli 5 (1): 3–48.

Barrat, Alain, and Martin Weigt. 2000. “On the Properties of Small-World Network Models.” The European Physical Journal B-Condensed Matter and Complex Systems 13 (3): 547–60.

Belkin, Mikhail, and Partha Niyogi. 2003. “Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.” Neural Computation 15 (6): 1373–96.

Borgs, Christian, Jennifer T. Chayes, Henry Cohn, and Yufei Zhao. 2014a. “An $Lp̂$ Theory of Sparse Graph Convergence I: Limits, Sparse Random Graph Models, and Power Law Distributions.” January 13, 2014.

———. 2014b. “An $Lp̂$ Theory of Sparse Graph Convergence II: LD Convergence, Quotients, and Right Convergence.” August 4, 2014.

Bullmore, Ed, and Olaf Sporns. 2009. “Complex Brain Networks: Graph Theoretical Analysis of Structural and Functional Systems.” Nature Reviews Neuroscience 10 (3): 186–98.

Caldarelli, G., A. Capocci, P. De Los Rios, and M. Muñoz. 2002. “Scale-Free Networks from Varying Vertex Intrinsic Fitness.” Physical Review Letters 89 (25).

Caldarelli, Guido, Alessandro Chessa, Fabio Pammolli, Andrea Gabrielli, and Michelangelo Puliga. n.d. “Reconstructing a Credit Network.” Nature Physics 9 (3): 125–26. Accessed March 20, 2013.

Callaway, Duncan S., M. E. J. Newman, Steven H. Strogatz, and Duncan J. Watts. 2000. “Network Robustness and Fragility: Percolation on Random Graphs.” Physical Review Letters 85 (25): 5468–71.

Carlsson, Gunnar. 2009. “Topology and Data.” Bulletin of the American Mathematical Society 46 (2): 255–308.

Carlsson, Gunnar, Tigran Ishkhanov, Vin de Silva, and Afra Zomorodian. 2008. “On the Local Behavior of Spaces of Natural Images.” International Journal of Computer Vision 76 (1): 1–12.

Clauset, Aaron, Mark E J Newman, and Cristopher Moore. 2004. “Finding Community Structure in Very Large Networks.” Physical Review E 70 (6): 066111.

Cohen, Reuven, Keren Erez, Daniel ben-Avraham, and Shlomo Havlin. 2000. “Resilience of the Internet to Random Breakdowns.” Physical Review Letters 85 (21): 4626–8.

———. 2001. “Breakdown of the Internet Under Intentional Attack.” Physical Review Letters 86 (16): 3682–5.

Cohen, Reuven, and Shlomo Havlin. 2003. “Scale-Free Networks Are Ultrasmall.” Physical Review Letters 90 (5).

Cohen-Steiner, David, Herbert Edelsbrunner, and John Harer. 2007. “Stability of Persistence Diagrams.” Discrete & Computational Geometry 37 (1): 103–20.

Coscia, Michele. 2020. “Generalized Euclidean Measure to Estimate Network Distances,” 11.

Daneshmand, Hadi, Manuel Gomez-Rodriguez, Le Song, and Bernhard Schölkopf. 2014. “Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-Thresholding Algorithm.” In ICML.

De Domenico, Manlio, Albert Solé-Ribalta, Emanuele Cozzo, Mikko Kivelä, Yamir Moreno, Mason A. Porter, Sergio Gómez, and Alex Arenas. 2013. “Mathematical Formulation of Multilayer Networks.” Physical Review X 3 (4): 041022.

Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. 2016. “Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.” In Advances in Neural Information Processing Systems.

Diaconis, Persi, and Daniel Stroock. 1991. “Geometric Bounds for Eigenvalues of Markov Chains.” The Annals of Applied Probability 1 (1): 36–61.

Doyle, John C., David L. Alderson, Lun Li, Steven Low, Matthew Roughan, Stanislav Shalunov, Reiko Tanaka, and Walter Willinger. 2005. “The ‘Robust yet Fragile’ Nature of the Internet.” Proceedings of the National Academy of Sciences of the United States of America 102 (41): 14497–14502.

Easley, David, and Jon Kleinberg. 2010. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. New York: Cambridge University Press.

Edelsbrunner, Herbert, David Letscher, and Afra Zomorodian. 2002. “Topological Persistence and Simplification.” Discrete & Computational Geometry 28 (4): 511–33.

Erdős, Paul, and Alfréd Rényi. 1959. “On Random Graphs I.” Publ. Math. Debrecen 6: 290–97.

Feld, Scott L. 1991. “Why Your Friends Have More Friends Than You Do.” American Journal of Sociology, 1464–77.

Fosdick, Bailey K., Daniel B. Larremore, Joel Nishimura, and Johan Ugander. 2016. “Configuring Random Graph Models with Fixed Degree Sequences.” August 1, 2016.

Foster, Jacob G., David V. Foster, Peter Grassberger, and Maya Paczuski. 2010. “Edge Direction and the Structure of Networks.” Proceedings of the National Academy of Sciences 107 (24): 10815–20.

Galbiati, Marco, Danilo Delpini, and Stefano Battiston. n.d. “The Power to Control.” Nature Physics 9 (3): 126–28.

Garcia, David, Pavlin Mavrodiev, and Frank Schweitzer. 2013. “Social Resilience in Online Communities: The Autopsy of Friendster.” In Proceedings of the First ACM Conference on Online Social Networks, 39–50. COSN ’13. New York, NY, USA: ACM.

Garcia, David, Fernando Mendez, Uwe Serdült, and Frank Schweitzer. 2012. “Political Polarization and Popularity in Online Participatory Media: An Integrated Approach.” In Proceedings of the First Edition Workshop on Politics, Elections and Data, 3–10. PLEAD ’12. New York, NY, USA: ACM.

Garlaschelli, Diego, Sebastian Ahnert, Thomas Fink, and Guido Caldarelli. 2013. “Low-Temperature Behaviour of Social and Economic Networks.” Entropy 15 (8): 3148–69.

Ghrist, Robert. 2008. “Barcodes: The Persistent Topology of Data.” Bulletin of the American Mathematical Society 45 (1): 61–75.

Gilbert, E. N. 1959. “Random Graphs.” The Annals of Mathematical Statistics 30 (4): 1141–4.

Gómez, S., A. Díaz-Guilera, J. Gómez-Gardeñes, C. J. Pérez-Vicente, Y. Moreno, and A. Arenas. 2013. “Diffusion Dynamics on Multiplex Networks.” Physical Review Letters 110 (2): 028701.

Granovetter, Mark. 1983. “The Strength of Weak Ties: A Network Theory Revisited.” Sociological Theory 1 (1): 201–33.

Granovetter, Mark S. 1973. “The Strength of Weak Ties.” The American Journal of Sociology 78 (6): 1360–80.

Green, Alden, and Cosma Rohilla Shalizi. 2017. “Bootstrapping Exchangeable Random Graphs.” November 2, 2017.

Greenhill, Catherine, Mikhail Isaev, Matthew Kwan, and Brendan D. McKay. 2016. “The Average Number of Spanning Trees in Sparse Graphs with Given Degrees.” June 5, 2016.

Holme, Petter, and Jari Saramäki. 2012. “Temporal Networks.” Physics Reports, Temporal Networks, 519 (3): 97–125.

Isaev, Mikhail, and Brendan D. McKay. 2016. “Complex Martingales and Asymptotic Enumeration.” April 28, 2016.

Iyer, Anand Padmanabha, Zaoxing Liu, Xin Jin, Shivaram Venkataraman, Vladimir Braverman, and Ion Stoica. 2018. “ASAP: Fast, Approximate Graph Pattern Mining at Scale.” In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), 745–61. Carlsbad, CA: USENIX Association.

Kac, Mark. 1966. “Can One Hear the Shape of a Drum?” American Mathematical Monthly, 1–23.

Karsai, M., M. Kivelä, R. K. Pan, K. Kaski, J. Kertész, A.-L. Barabási, and J. Saramäki. 2011. “Small but Slow World: How Network Topology and Burstiness Slow down Spreading.” Physical Review E 83 (2): 025102.

Kaushik, Rahul, and Stefano Battiston. 2013. “Credit Default Swaps Drawup Networks: Too Interconnected to Be Stable?” PLoS ONE 8 (7): e61815.

Kim, Myunghwan, and Jure Leskovec. 2012. “Multiplicative Attribute Graph Model of Real-World Networks.” Internet Mathematics 8 (1-2): 113–60.

Kipf, Thomas N., and Max Welling. 2016. “Semi-Supervised Classification with Graph Convolutional Networks.” In.

Klein, D. J., and M. Randić. 1993. “Resistance Distance.” Journal of Mathematical Chemistry 12 (1): 81–95.

Koenig, Michael, Stefano Battiston, M. Napoletano, and Frank Schweitzer. 2008. “The Efficiency and Evolution of R&D Networks.” SSRN Scholarly Paper ID 1271877. Rochester, NY: Social Science Research Network.

König, Michael D., S. Battiston, M. Napoletano, and F. Schweitzer. 2011. “Recombinant Knowledge and the Evolution of Innovation Networks.” Journal of Economic Behavior & Organization 79 (3): 145–64.

König, Michael D., Stefano Battiston, Mauro Napoletano, and Frank Schweitzer. 2012. “The Efficiency and Stability of R&D Networks.” Games and Economic Behavior 75 (2): 694–713.

Kramer, A. D. I., J. E. Guillory, and J. T. Hancock. 2014. “Experimental Evidence of Massive-Scale Emotional Contagion Through Social Networks.” Proceedings of the National Academy of Sciences 111 (24): 8788–90.

Kurtz, Thomas G. 1970. “Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes.” Journal of Applied Probability 7 (1): 49.

Lei, Jing. 2014. “A Goodness-of-Fit Test for Stochastic Block Models.” December 15, 2014.

Lovász, László. 2012. Large Networks and Graph Limits. American Mathematical Soc.

Madar, N., T. Kalisky, R. Cohen, D. ben-Avraham, and S. Havlin. 2004. “Immunization and Epidemic Dynamics in Complex Networks.” The European Physical Journal B 38 (2): 269–76.

Mahoney, Michael W. 2016. “Lecture Notes on Spectral Graph Methods.” 2016.

McKay, Brendan D., and Nicholas C. Wormald. 1990. “Asymptotic Enumeration by Degree Sequence of Graphs of High Degree.” European Journal of Combinatorics 11 (6): 565–80.

Milgram, Stanley. 1967. “The Small World Problem.” Psychology Today 2 (1): 60–67.

Miorandi, Daniele, and Francesco De Pellegrini. 2010. “K-Shell Decomposition for Dynamic Complex Networks.” In Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), 2010 Proceedings of the 8th International Symposium on, 488–96. IEEE.

Molloy, Michael, and Bruce Reed. 1995. “A Critical Point for Random Graphs with a Given Degree Sequence.” Random Structures & Algorithms 6 (2-3): 161–80.

Newman, M. E. J. 2003. “Mixing Patterns in Networks.” Physical Review E 67 (2): 026126.

———. 2004. “Fast Algorithm for Detecting Community Structure in Networks.” Physical Review E 69 (6): 066133.

———. 2006. “Modularity and Community Structure in Networks.” Proceedings of the National Academy of Sciences 103 (23): 8577–82.

Newman, M. E. J., and M. Girvan. 2004. “Finding and Evaluating Community Structure in Networks.” Physical Review E 69 (2): 026113.

Newman, M. E. J., S. H. Strogatz, and D. J. Watts. 2001. “Random Graphs with Arbitrary Degree Distributions and Their Applications.” Physical Review E 64 (2): 026118.

Noh, Jae Dong. 2004. “Random Walks on Complex Networks.” Physical Review Letters 92 (11).

Odlyzko, A. M. 1995. “Asymptotic Enumeration Methods.” In Handbook of Combinatorics (Vol. 2), edited by R. L. Graham, M. Grötschel, and L. Lovász, 1063–1229. Cambridge, MA, USA: MIT Press.

Olfati-Saber, R., J. A. Fax, and R. M. Murray. 2007. “Consensus and Cooperation in Networked Multi-Agent Systems.” Proceedings of the IEEE 95 (1): 215–33.

Orbanz, P., and D. M. Roy. 2015. “Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures.” IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2): 437–61.

Otasek, David, John H. Morris, Jorge Bouças, Alexander R. Pico, and Barry Demchak. 2019. “Cytoscape Automation: Empowering Workflow-Based Network Analysis.” Genome Biology 20 (1): 185.

Pan, Gang, Wangsheng Zhang, Zhaohui Wu, and Shijian Li. 2014. “Online Community Detection for Large Complex Networks.” PLoS ONE 9 (7): e102799.

Pastor-Satorras, Romualdo, and Alessandro Vespignani. 2002. “Immunization of Complex Networks.” Physical Review E 65 (3): 036104.

Perony, Nicolas, René Pfitzner, Ingo Scholtes, Claudio J Tessone, and Frank Schweitzer. 2013. “Enhancing Consensus Under Opinion Bias by Means of Hierarchical Decision Making.” Advances in Complex Systems 16 (06): 1350020.

Petri, Giovanni, Martina Scolamiero, Irene Donato, and Francesco Vaccarino. 2013a. “Networks and Cycles: A Persistent Homology Approach to Complex Networks.” In Proceedings of the European Conference on Complex Systems 2012, edited by Thomas Gilbert, Markus Kirkilionis, and Gregoire Nicolis, 93–99. Springer Proceedings in Complexity. Springer International Publishing.

———. 2013b. “Topological Strata of Weighted Complex Networks.” PLoS ONE 8 (6): e66506.

Pfitzner, René, Ingo Scholtes, Antonios Garas, Claudio J. Tessone, and Frank Schweitzer. 2013. “Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks.” Physical Review Letters 110 (19): 198701.

Pinto, Pedro C., Patrick Thiran, and Martin Vetterli. 2012. “Locating the Source of Diffusion in Large-Scale Networks.” Physical Review Letters 109 (6): 068702.

Pons, Pascal, and Matthieu Latapy. 2005. “Computing Communities in Large Networks Using Random Walks.” In Computer and Information Sciences - ISCIS 2005, edited by pInar Yolum, Tunga Güngör, Fikret Gürgen, and Can Özturan, 284–93. Lecture Notes in Computer Science 3733. Springer Berlin Heidelberg.

Pouget-Abadie, Jean, and Thibaut Horel. 2015. “Inferring Graphs from Cascades: A Sparse Recovery Framework.” In Proceedings of the 32nd International Conference on Machine Learning.

Protter, M. H. 1987. “Can One Hear the Shape of a Drum? Revisited.” Siam Review 29 (2): 185–97.

Rapoport, Anatol. 1953a. “Spread of Information Through a Population with Socio-Structural Bias: I. Assumption of Transitivity.” The Bulletin of Mathematical Biophysics 15 (4): 523–33.

———. 1953b. “Spread of Information Through a Population with Socio-Structural Bias: II. Various Models with Partial Transitivity.” The Bulletin of Mathematical Biophysics 15 (4): 535–46.

———. 1954. “Spread of Information Through a Population with Socio-Structural Bias: III. Suggested Experimental Procedures.” The Bulletin of Mathematical Biophysics 16 (1): 75–81.

———. 1957. “Contribution to the Theory of Random and Biased Nets.” The Bulletin of Mathematical Biophysics 19 (4): 257–77.

Richardson, Thomas O., Nicolas Perony, Claudio J. Tessone, Christophe A. H. Bousquet, Marta B. Manser, and Frank Schweitzer. 2013. “Dynamical Coupling During Collective Animal Motion.” November 6, 2013.

Rosvall, Martin, and Carl T. Bergstrom. 2008. “Maps of Random Walks on Complex Networks Reveal Community Structure.” Proceedings of the National Academy of Sciences 105 (4): 1118–23.

Sarigol, Emre, David Garcia, and Frank Schweitzer. 2014. “Online Privacy as a Collective Phenomenon.” In Proceedings of the Second ACM Conference on Online Social Networks, 95–106. COSN ’14. New York, NY, USA: ACM.

Scholtes, Ingo, Nicolas Wider, Rene Pfitzner, Antonios Garas, Claudio Juan Tessone, and Frank Schweitzer. 2013. “Slow-down Vs. Speed-up of Diffusion in Non-Markovian Temporal Networks.” July 15, 2013.

Schweitzer, Frank, Giorgio Fagiolo, Didier Sornette, Fernando Vega-Redondo, Alessandro Vespignani, and Douglas R White. 2009. “Economic Networks: The New Challenges.” Science 325 (5939): 422–25.

Seshadhri, C., Aneesh Sharma, Andrew Stolman, and Ashish Goel. 2020. “The Impossibility of Low-Rank Representations for Triangle-Rich Complex Networks.” Proceedings of the National Academy of Sciences 117 (11): 5631–7.

Shannon, Paul, Andrew Markiel, Owen Ozier, Nitin S. Baliga, Jonathan T. Wang, Daniel Ramage, Nada Amin, Benno Schwikowski, and Trey Ideker. 2003. “Cytoscape: A Software Environment for Integrated Models of Biomolecular Interaction Networks.” Genome Research 13 (11): 2498–2504.

Smith, Tara C, and Steven P Novella. 2007. “HIV Denial in the Internet Era.” PLoS Med 4 (8): e256.

Solé-Ribalta, A., M. De Domenico, N. E. Kouvaris, A. Díaz-Guilera, S. Gómez, and A. Arenas. 2013. “Spectral Properties of the Laplacian of Multiplex Networks.” Physical Review E 88 (3): 032807.

Stegehuis, Clara, Remco van der Hofstad, and Johan S. H. van Leeuwaarden. 2016. “Epidemic Spreading on Complex Networks with Community Structures.” Scientific Reports 6 (July): 29748.

St-Onge, Guillaume, Vincent Thibeault, Antoine Allard, Louis J. Dubé, and Laurent Hébert-Dufresne. 2020. “School Closures, Event Cancellations, and the Mesoscopic Localization of Epidemics in Networks with Higher-Order Structure.” March 12, 2020.

Streater, R. F. 2000. “Classical and Quantum Probability.” February 27, 2000.

Tang, Minh, Avanti Athreya, Daniel L. Sussman, Vince Lyzinski, and Carey E. Priebe. 2014. “A Nonparametric Two-Sample Hypothesis Testing Problem for Random Dot Product Graphs.” September 8, 2014.

Tedeschi, Gabriele, Stefania Vitali, and Mauro Gallegati. 2014. “The Dynamic of Innovation Networks: A Switching Model on Technological Change.” Journal of Evolutionary Economics, July, 1–18.

Tetali, Prasad. 1991. “Random Walks and the Effective Resistance of Networks.” Journal of Theoretical Probability 4: 101–9.

Tomasello, Mario Vincenzo, Mauro Napoletano, Antonios Garas, and Frank Schweitzer. 2013. “The Rise and Fall of R&D Networks.” April 12, 2013.

Tomasello, Mario V., Nicola Perra, Claudio J. Tessone, Márton Karsai, and Frank Schweitzer. 2014. “The Role of Endogenous and Exogenous Mechanisms in the Formation of R&D Networks.” Scientific Reports 4 (July).

Veitch, Victor, and Daniel M. Roy. 2015. “The Class of Random Graphs Arising from Exchangeable Random Measures.” December 7, 2015.

Verma, Inder M. 2014. “Editorial Expression of Concern: Experimental Evidence of Massivescale Emotional Contagion Through Social Networks.” Proceedings of the National Academy of Sciences, July, 201412469.

Watts, Duncan J, and Steven H Strogatz. 1998. “Collective Dynamics of ’Small-World’ Networks.” Nature 393 (6684): 440–42.

Yang, Shuang-Hong, Bo Long, Alex Smola, Narayanan Sadagopan, Zhaohui Zheng, and Hongyuan Zha. 2011. “Like Like Alike: Joint Friendship and Interest Propagation in Social Networks.” In Proceedings of the 20th International Conference on World Wide Web, 537–46. WWW ’11. New York, NY, USA: ACM.

Zanette, Damián. 2008. “Playing by Numbers.” Nature 453 (7198): 988–89.

Zhou, Xian Y. 1993. “Resistance Dimension, Random Walk Dimension and Fractal Dimension.” Journal of Theoretical Probability 6: 635–52.

Zhou, XueZhong, Jörg Menche, Albert-László Barabási, and Amitabh Sharma. 2014. “Human Symptoms–Disease Network.” Nature Communications 5 (June).

Zomorodian, Afra, and Gunnar Carlsson. 2005. “Computing Persistent Homology.” Discrete & Computational Geometry 33 (2): 249–74.

Zuev, Konstantin, Marian Boguna, Ginestra Bianconi, and Dmitri Krioukov. 2015. “Emergence of Soft Communities from Geometric Preferential Attachment.” Scientific Reports 5 (April): 9421.