Networks and graphs, theory thereof

November 24, 2014 — October 20, 2021

Figure 1

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

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

5.1 Stochastic Petri Nets

6 Graph software

See Graph computation

7 Incoming

8 References

Achlioptas, Clauset, Kempe, et al. 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. STOC ’05.
Akyildiz, Su, Sankarasubramaniam, et al. 2002. A Survey on Sensor Networks.” Communications Magazine, IEEE.
Albert, Jeong, and Barabási. 2000. Error and Attack Tolerance of Complex Networks.” Nature.
Aldous. 1999. Deterministic and Stochastic Models for Coalescence (Aggregation and Coagulation): A Review of the Mean-Field Theory for Probabilists.” Bernoulli.
Barrat, and Weigt. 2000. On the Properties of Small-World Network Models.” The European Physical Journal B-Condensed Matter and Complex Systems.
Belkin, and Niyogi. 2003. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.” Neural Computation.
Borgs, Chayes, Cohn, et al. 2014a. An \(L^p\) Theory of Sparse Graph Convergence I: Limits, Sparse Random Graph Models, and Power Law Distributions.” arXiv:1401.2906 [Math].
———, et al. 2014b. An \(L^p\) Theory of Sparse Graph Convergence II: LD Convergence, Quotients, and Right Convergence.” arXiv:1408.0744 [Math].
Bullmore, and Sporns. 2009. Complex Brain Networks: Graph Theoretical Analysis of Structural and Functional Systems.” Nature Reviews Neuroscience.
Caldarelli, G., Capocci, De Los Rios, et al. 2002. Scale-Free Networks from Varying Vertex Intrinsic Fitness.” Physical Review Letters.
Caldarelli, Guido, Chessa, Pammolli, et al. n.d. Reconstructing a Credit Network.” Nature Physics.
Callaway, Newman, Strogatz, et al. 2000. Network Robustness and Fragility: Percolation on Random Graphs.” Physical Review Letters.
Carlsson. 2009. Topology and Data.” Bulletin of the American Mathematical Society.
Carlsson, Ishkhanov, Silva, et al. 2008. On the Local Behavior of Spaces of Natural Images.” International Journal of Computer Vision.
Clauset, Newman, and Moore. 2004. Finding Community Structure in Very Large Networks.” Physical Review E.
Cohen, Erez, ben-Avraham, et al. 2000. Resilience of the Internet to Random Breakdowns.” Physical Review Letters.
———, et al. 2001. Breakdown of the Internet Under Intentional Attack.” Physical Review Letters.
Cohen, and Havlin. 2003. Scale-Free Networks Are Ultrasmall.” Physical Review Letters.
Cohen-Steiner, Edelsbrunner, and Harer. 2007. Stability of Persistence Diagrams.” 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. Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-Thresholding Algorithm.” In ICML.
De Domenico, Solé-Ribalta, Cozzo, et al. 2013. Mathematical Formulation of Multilayer Networks.” Physical Review X.
Defferrard, Bresson, and Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.” In Advances In Neural Information Processing Systems.
Diaconis, and Stroock. 1991. Geometric Bounds for Eigenvalues of Markov Chains.” The Annals of Applied Probability.
Doyle, Alderson, Li, et al. 2005. The ‘Robust yet Fragile’ Nature of the Internet.” 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. Topological Persistence and Simplification.” Discrete & Computational Geometry.
Erdős, and Rényi. 1959. On Random Graphs I.” Publ. Math. Debrecen.
Feld. 1991. Why Your Friends Have More Friends Than You Do.” American Journal of Sociology.
Fortunato, and Newman. 2022. 20 Years of Network Community Detection.” Nature Physics.
Fosdick, Larremore, Nishimura, et al. 2016. Configuring Random Graph Models with Fixed Degree Sequences.” arXiv:1608.00607 [Physics, q-Bio, Stat].
Foster, Foster, Grassberger, et al. 2010. Edge Direction and the Structure of Networks.” Proceedings of the National Academy of Sciences.
Galbiati, Delpini, and Battiston. n.d. The Power to Control.” Nature Physics.
Garcia, Mavrodiev, and Schweitzer. 2013. Social Resilience in Online Communities: The Autopsy of Friendster.” In Proceedings of the First ACM Conference on Online Social Networks. COSN ’13.
Garcia, Mendez, Serdült, et al. 2012. Political Polarization and Popularity in Online Participatory Media: An Integrated Approach.” In Proceedings of the First Edition Workshop on Politics, Elections and Data. PLEAD ’12.
Garlaschelli, Ahnert, Fink, et al. 2013. Low-Temperature Behaviour of Social and Economic Networks.” Entropy.
Ghrist. 2008. Barcodes: The Persistent Topology of Data.” Bulletin of the American Mathematical Society.
Gilbert. 1959. Random Graphs.” The Annals of Mathematical Statistics.
Glasscock. 2016. What Is a Graphon? arXiv:1611.00718 [Math].
Gómez, Díaz-Guilera, Gómez-Gardeñes, et al. 2013. Diffusion Dynamics on Multiplex Networks.” Physical Review Letters.
Granovetter, Mark S. 1973. The Strength of Weak Ties.” The American Journal of Sociology.
Granovetter, Mark. 1983. The Strength of Weak Ties: A Network Theory Revisited.” Sociological Theory.
Greenhill, Isaev, Kwan, et al. 2016. The Average Number of Spanning Trees in Sparse Graphs with Given Degrees.” arXiv:1606.01586 [Math].
Green, and Shalizi. 2017. Bootstrapping Exchangeable Random Graphs.” arXiv:1711.00813 [Stat].
Holme, and Saramäki. 2012. Temporal Networks.” Physics Reports, Temporal Networks,.
Isaev, and McKay. 2016. Complex Martingales and Asymptotic Enumeration.” arXiv:1604.08305 [Math].
Iyer, Liu, Jin, et al. 2018. ASAP: Fast, Approximate Graph Pattern Mining at Scale.” In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18).
Kac. 1966. Can One Hear the Shape of a Drum? American Mathematical Monthly.
Karsai, Kivelä, Pan, et al. 2011. Small but Slow World: How Network Topology and Burstiness Slow down Spreading.” Physical Review E.
Kaushik, and Battiston. 2013. Credit Default Swaps Drawup Networks: Too Interconnected to Be Stable? PLoS ONE.
Kim, and Leskovec. 2012. Multiplicative Attribute Graph Model of Real-World Networks.” Internet Mathematics.
Kipf, and Welling. 2016. Semi-Supervised Classification with Graph Convolutional Networks.” In arXiv:1609.02907 [Cs, Stat].
Klein, and Randić. 1993. Resistance Distance.” Journal of Mathematical Chemistry.
Koenig, Battiston, Napoletano, et al. 2008. The Efficiency and Evolution of R&D Networks.” SSRN Scholarly Paper ID 1271877.
König, Battiston, Napoletano, et al. 2011. Recombinant Knowledge and the Evolution of Innovation Networks.” Journal of Economic Behavior & Organization.
König, Battiston, Napoletano, et al. 2012. The Efficiency and Stability of R&D Networks.” Games and Economic Behavior.
Kramer, Guillory, and Hancock. 2014. Experimental Evidence of Massive-Scale Emotional Contagion Through Social Networks.” Proceedings of the National Academy of Sciences.
Kurtz. 1970. Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes.” Journal of Applied Probability.
Lei. 2014. A Goodness-of-Fit Test for Stochastic Block Models.” arXiv:1412.4857 [Math, Stat].
Lovász. 2012. Large Networks and Graph Limits.
Madar, Kalisky, Cohen, et al. 2004. Immunization and Epidemic Dynamics in Complex Networks.” The European Physical Journal B.
Mahoney. 2016. Lecture Notes on Spectral Graph Methods.” arXiv Preprint arXiv:1608.04845.
McKay, and Wormald. 1990. Asymptotic Enumeration by Degree Sequence of Graphs of High Degree.” European Journal of Combinatorics.
Milgram. 1967. The Small World Problem.” Psychology Today.
Miorandi, and 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.
Molloy, and Reed. 1995. A Critical Point for Random Graphs with a Given Degree Sequence.” Random Structures & Algorithms.
Newman. 2003. Mixing Patterns in Networks.” Physical Review E.
———. 2004. Fast Algorithm for Detecting Community Structure in Networks.” Physical Review E.
———. 2006. Modularity and Community Structure in Networks.” Proceedings of the National Academy of Sciences.
Newman, and Girvan. 2004. Finding and Evaluating Community Structure in Networks.” Physical Review E.
Newman, Strogatz, and Watts. 2001. Random Graphs with Arbitrary Degree Distributions and Their Applications.” Physical Review E.
Noh. 2004. Random Walks on Complex Networks.” Physical Review Letters.
Odlyzko. 1995. Asymptotic Enumeration Methods.” In Handbook of Combinatorics (Vol. 2).
Olfati-Saber, Fax, and Murray. 2007. Consensus and Cooperation in Networked Multi-Agent Systems.” Proceedings of the IEEE.
Orbanz, and Roy. 2015. Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures.” IEEE Transactions on Pattern Analysis and Machine Intelligence.
Otasek, Morris, Bouças, et al. 2019. Cytoscape Automation: Empowering Workflow-Based Network Analysis.” Genome Biology.
Pan, Zhang, Wu, et al. 2014. Online Community Detection for Large Complex Networks.” PLoS ONE.
Pastor-Satorras, and Vespignani. 2002. Immunization of Complex Networks.” Physical Review E.
Perony, Pfitzner, Scholtes, et al. 2013. Enhancing Consensus Under Opinion Bias by Means of Hierarchical Decision Making.” Advances in Complex Systems.
Petri, Scolamiero, Donato, et al. 2013a. Networks and Cycles: A Persistent Homology Approach to Complex Networks.” In Proceedings of the European Conference on Complex Systems 2012. Springer Proceedings in Complexity.
———, et al. 2013b. Topological Strata of Weighted Complex Networks.” PLoS ONE.
Pfitzner, Scholtes, Garas, et al. 2013. Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks.” Physical Review Letters.
Pinto, Thiran, and Vetterli. 2012. Locating the Source of Diffusion in Large-Scale Networks.” Physical Review Letters.
Pons, and Latapy. 2005. Computing Communities in Large Networks Using Random Walks.” In Computer and Information Sciences - ISCIS 2005. Lecture Notes in Computer Science 3733.
Pouget-Abadie, and Horel. 2015. Inferring Graphs from Cascades: A Sparse Recovery Framework.” In Proceedings of The 32nd International Conference on Machine Learning.
Protter. 1987. Can One Hear the Shape of a Drum? Revisited.” Siam Review.
Rapoport. 1953a. Spread of Information Through a Population with Socio-Structural Bias: I. Assumption of Transitivity.” The Bulletin of Mathematical Biophysics.
———. 1953b. Spread of Information Through a Population with Socio-Structural Bias: II. Various Models with Partial Transitivity.” The Bulletin of Mathematical Biophysics.
———. 1954. Spread of Information Through a Population with Socio-Structural Bias: III. Suggested Experimental Procedures.” The Bulletin of Mathematical Biophysics.
———. 1957. Contribution to the Theory of Random and Biased Nets.” The Bulletin of Mathematical Biophysics.
Richardson, Perony, Tessone, et al. 2013. Dynamical Coupling During Collective Animal Motion.” arXiv:1311.1417 [q-Bio].
Rosvall, and Bergstrom. 2008. Maps of Random Walks on Complex Networks Reveal Community Structure.” Proceedings of the National Academy of Sciences.
Sarigol, Garcia, and Schweitzer. 2014. Online Privacy As a Collective Phenomenon.” In Proceedings of the Second ACM Conference on Online Social Networks. COSN ’14.
Scholtes, Wider, Pfitzner, et al. 2013. Slow-Down Vs. Speed-Up of Diffusion in Non-Markovian Temporal Networks.” arXiv:1307.4030 [Cond-Mat, Physics:physics].
Schweitzer, Fagiolo, Sornette, et al. 2009. Economic Networks: The New Challenges.” Science.
Seshadhri, Sharma, Stolman, et al. 2020. The Impossibility of Low-Rank Representations for Triangle-Rich Complex Networks.” Proceedings of the National Academy of Sciences.
Shannon, Markiel, Ozier, et al. 2003. Cytoscape: A Software Environment for Integrated Models of Biomolecular Interaction Networks.” Genome Research.
Smith, and Novella. 2007. HIV Denial in the Internet Era.” PLoS Med.
Solé-Ribalta, De Domenico, Kouvaris, et al. 2013. Spectral Properties of the Laplacian of Multiplex Networks.” Physical Review E.
Stegehuis, van der Hofstad, and van Leeuwaarden. 2016. Epidemic Spreading on Complex Networks with Community Structures.” Scientific Reports.
St-Onge, Thibeault, Allard, et al. 2020. School Closures, Event Cancellations, and the Mesoscopic Localization of Epidemics in Networks with Higher-Order Structure.” arXiv:2003.05924 [Nlin, Physics:physics].
Streater. 2000. Classical and Quantum Probability.” arXiv:math-Ph/0002049.
Tang, Athreya, Sussman, et al. 2014. A Nonparametric Two-Sample Hypothesis Testing Problem for Random Dot Product Graphs.” arXiv:1409.2344 [Math, Stat].
Tetali. 1991. Random Walks and the Effective Resistance of Networks.” Journal of Theoretical Probability.
Tomasello, Napoletano, Garas, et al. 2013. The Rise and Fall of R&D Networks.” arXiv:1304.3623 [Physics].
Veitch, and Roy. 2015. The Class of Random Graphs Arising from Exchangeable Random Measures.” arXiv:1512.03099 [Cs, Math, Stat].
Verma. 2014. Editorial Expression of Concern: Experimental Evidence of Massivescale Emotional Contagion Through Social Networks.” Proceedings of the National Academy of Sciences.
Watts, and Strogatz. 1998. Collective Dynamics of ‘Small-World’ Networks.” Nature.
Yang, Long, Smola, et al. 2011. Like Like Alike: Joint Friendship and Interest Propagation in Social Networks.” In Proceedings of the 20th International Conference on World Wide Web. WWW ’11.
Zanette. 2008. Playing by Numbers.” Nature.
Zhou, Xian Y. 1993. Resistance Dimension, Random Walk Dimension and Fractal Dimension.” Journal of Theoretical Probability.
Zhou, XueZhong, Menche, Barabási, et al. 2014. Human Symptoms–Disease Network.” Nature Communications.
Zomorodian, and Carlsson. 2005. Computing Persistent Homology.” Discrete & Computational Geometry.
Zuev, Boguna, Bianconi, et al. 2015. Emergence of Soft Communities from Geometric Preferential Attachment.” Scientific Reports.