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.
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.
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.
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.
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?
Stochastic Petri Nets
What are these?
If you add in probability, are they the same as stochastic Petri nets?
- MoRe95: (1995) A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2–3), 161–180. DOI
- Lei14: (2014) A Goodness-of-fit Test for Stochastic Block Models. ArXiv:1412.4857 [Math, Stat].
- TASL14: (2014) A nonparametric two-sample hypothesis testing problem for random dot product graphs. ArXiv:1409.2344 [Math, Stat].
- ASSC02: (2002) A survey on sensor networks. Communications Magazine, IEEE, 40(8), 102–114. DOI
- BCCZ14a: (2014a) An \(L^p\) theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions. ArXiv:1401.2906 [Math].
- BCCZ14b: (2014b) An \(L^p\) theory of sparse graph convergence II: LD convergence, quotients, and right convergence. ArXiv:1408.0744 [Math].
- McWo90: (1990) Asymptotic Enumeration by Degree Sequence of Graphs of High Degree. European Journal of Combinatorics, 11(6), 565–580. DOI
- Odly95: (1995) Asymptotic Enumeration Methods. In Handbook of Combinatorics (Vol. 2) (pp. 1063–1229). Cambridge, MA, USA: MIT Press
- Ghri08: (2008) Barcodes: The persistent topology of data. Bulletin of the American Mathematical Society, 45(1), 61–75. DOI
- OrRo15: (2015) Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2), 437–461. DOI
- PSGT13: (2013) Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks. Physical Review Letters, 110(19), 198701. DOI
- GrSh17: (2017) Bootstrapping Exchangeable Random Graphs. ArXiv:1711.00813 [Stat].
- CEAH01: (2001) Breakdown of the Internet under intentional attack. Physical Review Letters, 86(16), 3682–3685. DOI
- Kac66: (1966) Can one hear the shape of a drum? American Mathematical Monthly, 1–23.
- Prot87: (1987) Can one hear the shape of a drum? Revisited. Siam Review, 29(2), 185–197.
- Stre00: (2000) Classical and Quantum Probability. ArXiv:Math-Ph/0002049.
- WaSt98: (1998) Collective dynamics of “small-world” networks. Nature, 393(6684), 440–442. DOI
- BuSp09: (2009) Complex brain networks: graph theoretical analysis of structural and functional systems. Nature Reviews Neuroscience, 10(3), 186–198. DOI
- IsMc16: (2016) Complex martingales and asymptotic enumeration. ArXiv:1604.08305 [Math].
- PoLa05: (2005) Computing Communities in Large Networks Using Random Walks. In Computer and Information Sciences - ISCIS 2005 (pp. 284–293). Springer Berlin Heidelberg
- ZoCa05: (2005) Computing Persistent Homology. Discrete & Computational Geometry, 33(2), 249–274. DOI
- FLNU16: (2016) Configuring Random Graph Models with Fixed Degree Sequences. ArXiv:1608.00607 [Physics, q-Bio, Stat].
- OlFM07: (2007) Consensus and Cooperation in Networked Multi-Agent Systems. Proceedings of the IEEE, 95(1), 215–233. DOI
- Rapo57: (1957) Contribution to the theory of random and biased nets. The Bulletin of Mathematical Biophysics, 19(4), 257–277. DOI
- DeBV16: (2016) Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances In Neural Information Processing Systems.
- KaBa13: (2013) Credit Default Swaps Drawup Networks: Too Interconnected to Be Stable? PLoS ONE, 8(7), e61815. DOI
- BGGG12: (2012) Default cascades: When does risk diversification increase stability? Journal of Financial Stability, 8(3), 138–149. DOI
- GDGP13: (2013) Diffusion Dynamics on Multiplex Networks. Physical Review Letters, 110(2), 028701. DOI
- RPTB13: (2013) Dynamical coupling during collective animal motion. ArXiv:1311.1417 [q-Bio].
- SFSV09: (2009) Economic Networks: The New Challenges. Science, 325(5939), 422–425. DOI
- FFGP10: (2010) Edge direction and the structure of networks. Proceedings of the National Academy of Sciences, 107(24), 10815–10820. DOI
- Verm14: (2014) Editorial Expression of Concern: Experimental evidence of massivescale emotional contagion through social networks. Proceedings of the National Academy of Sciences, 201412469. DOI
- ZBBK15: (2015) Emergence of Soft Communities from Geometric Preferential Attachment. Scientific Reports, 5, 9421. DOI
- PPST13: (2013) Enhancing Consensus Under Opinion Bias by Means of Hierarchical Decision Making. Advances in Complex Systems, 16(06), 1350020. DOI
- StHL16: (2016) Epidemic spreading on complex networks with community structures. Scientific Reports, 6, 29748. DOI
- AlJB00: (2000) Error and attack tolerance of complex networks. Nature, 406(6794), 378–382. DOI
- DGSS14: (2014) Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm. In ICML.
- KrGH14: (2014) Experimental evidence of massive-scale emotional contagion through social networks. Proceedings of the National Academy of Sciences, 111(24), 8788–8790. DOI
- Newm04: (2004) Fast algorithm for detecting community structure in networks. Physical Review E, 69(6), 066133. DOI
- NeGi04: (2004) Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113. DOI
- ClNM04: (2004) Finding community structure in very large networks. Physical Review E, 70(6), 066111. DOI
- DiSt91: (1991) Geometric Bounds for Eigenvalues of Markov Chains. The Annals of Applied Probability, 1(1), 36–61. DOI
- BaCh13: (2013) Getting a grip on the electrical grid. Physics Today, 66(5), 42. DOI
- SmNo07: (2007) HIV Denial in the Internet Era. PLoS Med, 4(8), e256. DOI
- ZMBS14: (2014) Human symptoms–disease network. Nature Communications, 5. DOI
- PoHo15: (2015) Inferring Graphs from Cascades: A Sparse Recovery Framework. In Proceedings of The 32nd International Conference on Machine Learning.
- MiDe10: (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 (pp. 488–496). IEEE
- BeNi03: (2003) Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6), 1373–1396. DOI
- Lová12: (2012) Large Networks and Graph Limits. American Mathematical Soc.
- Maho16: (2016) Lecture Notes on Spectral Graph Methods. ArXiv Preprint ArXiv:1608.04845.
- YLSS11: (2011) Like Like Alike: Joint Friendship and Interest Propagation in Social Networks. In Proceedings of the 20th International Conference on World Wide Web (pp. 537–546). New York, NY, USA: ACM DOI
- PiTV12: (2012) Locating the Source of Diffusion in Large-Scale Networks. Physical Review Letters, 109(6), 068702. DOI
- GAFC13: (2013) Low-Temperature Behaviour of Social and Economic Networks. Entropy, 15(8), 3148–3169. DOI
- RoBe08: (2008) Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4), 1118–1123. DOI
- DSCK13: (2013) Mathematical Formulation of Multilayer Networks. Physical Review X, 3(4), 041022. DOI
- Newm03: (2003) Mixing patterns in networks. Physical Review E, 67(2), 026126. DOI
- Bali07: (2007) Modeling Infectious Diseases Dissemination Through Online Role-Playing Games: Epidemiology, 18(2), 260–261. DOI
- Newm06: (2006) Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582. DOI
- KiLe12: (2012) Multiplicative Attribute Graph Model of Real-World Networks. Internet Mathematics, 8(1–2), 113–160. DOI
- CNSW00: (2000) Network Robustness and Fragility: Percolation on Random Graphs. Physical Review Letters, 85(25), 5468–5471. DOI
- PSDV13a: (2013a) Networks and Cycles: A Persistent Homology Approach to Complex Networks. In Proceedings of the European Conference on Complex Systems 2012 (pp. 93–99). Springer International Publishing
- EaKl10: (2010) Networks, crowds, and markets: reasoning about a highly connected world. New York: Cambridge University Press
- ErRé59: (1959) On random graphs I. Publ. Math. Debrecen, 6, 290–297.
- ACKM05: (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 (pp. 694–703). New York, NY, USA: ACM DOI
- CISZ08: (2008) On the Local Behavior of Spaces of Natural Images. International Journal of Computer Vision, 76(1), 1–12. DOI
- BaWe00: (2000) On the properties of small-world network models. The European Physical Journal B-Condensed Matter and Complex Systems, 13(3), 547–560.
- PZWL14: (2014) Online Community Detection for Large Complex Networks. PLoS ONE, 9(7), e102799. DOI
- SaGS14: (2014) Online Privacy as a Collective Phenomenon. ArXiv:1409.6197 [Cs].
- Zane08: (2008) Playing by numbers. Nature, 453(7198), 988–989. DOI
- GMSS12: (2012) Political Polarization and Popularity in Online Participatory Media: An Integrated Approach. In Proceedings of the First Edition Workshop on Politics, Elections and Data (pp. 3–10). New York, NY, USA: ACM DOI
- Gilb59: (1959) Random Graphs. The Annals of Mathematical Statistics, 30(4), 1141–1144. DOI
- NeSW01: (2001) Random graphs with arbitrary degree distributions and their applications. Physical Review E, 64(2), 026118. DOI
- Teta91: (1991) Random walks and the effective resistance of networks. Journal of Theoretical Probability, 4, 101–109. DOI
- Noh04: (2004) Random Walks on Complex Networks. Physical Review Letters, 92(11). DOI
- KBNS11: (2011) Recombinant knowledge and the evolution of innovation networks. Journal of Economic Behavior & Organization, 79(3), 145–164. DOI
- CCPG13: (2013) Reconstructing a credit network. Nature Physics, 9(3), 125–126. DOI
- CEAH00: (2000) Resilience of the Internet to random breakdowns. Physical Review Letters, 85(21), 4626–4628. DOI
- Zhou93: (1993) Resistance dimension, random walk dimension and fractal dimension. Journal of Theoretical Probability, 6, 635–652. DOI
- KlRa93: (1993) Resistance distance. Journal of Mathematical Chemistry, 12(1), 81–95. DOI
- CoHa03: (2003) Scale-Free Networks Are Ultrasmall. Physical Review Letters, 90(5). DOI
- CCDM02: (2002) Scale-Free Networks from Varying Vertex Intrinsic Fitness. Physical Review Letters, 89(25). DOI
- KiWe16: (2016) Semi-Supervised Classification with Graph Convolutional Networks. In arXiv:1609.02907 [cs, stat].
- SWPG13: (2013) Slow-Down vs Speed-Up of Diffusion in Non-Markovian Temporal Networks. ArXiv:1307.4030 [Cond-Mat, Physics:Physics].
- KKPK11: (2011) Small but slow world: How network topology and burstiness slow down spreading. Physical Review E, 83(2), 025102. DOI
- GaMS13: (2013) Social Resilience in Online Communities: The Autopsy of Friendster. In Proceedings of the First ACM Conference on Online Social Networks (pp. 39–50). New York, NY, USA: ACM DOI
- Kurt70: (1970) Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes. Journal of Applied Probability, 7(1), 49. DOI
- SDKD13: (2013) Spectral properties of the Laplacian of multiplex networks. Physical Review E, 88(3), 032807. DOI
- Rapo53a: (1953a) Spread of information through a population with socio-structural bias: I Assumption of transitivity. The Bulletin of Mathematical Biophysics, 15(4), 523–533. DOI
- Rapo53b: (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–546. DOI
- Rapo54: (1954) Spread of information through a population with socio-structural bias: III Suggested experimental procedures. The Bulletin of Mathematical Biophysics, 16(1), 75–81. DOI
- CoEH07: (2007) Stability of Persistence Diagrams. Discrete & Computational Geometry, 37(1), 103–120. DOI
- HoSa12: (2012) Temporal networks. Physics Reports, 519(3), 97–125. DOI
- GIKM16: (2016) The average number of spanning trees in sparse graphs with given degrees. ArXiv:1606.01586 [Math].
- VeRo15: (2015) The Class of Random Graphs Arising from Exchangeable Random Measures. ArXiv:1512.03099 [Cs, Math, Stat].
- TeVG14: (2014) The dynamic of innovation networks: a switching model on technological change. Journal of Evolutionary Economics, 1–18. DOI
- KBNS08: (2008) The Efficiency and Evolution of R&D Networks (SSRN Scholarly Paper No. ID 1271877). Rochester, NY: Social Science Research Network
- KBNS12: (2012) The efficiency and stability of R&D networks. Games and Economic Behavior, 75(2), 694–713. DOI
- GaDB13: (2013) The power to control. Nature Physics, 9(3), 126–128. DOI
- TNGS13: (2013) The Rise and Fall of R&D Networks. ArXiv:1304.3623 [Physics].
- DALL05: (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.
- TPTK14: (2014) The role of endogenous and exogenous mechanisms in the formation of R&D networks. Scientific Reports, 4. DOI
- Milg67: (1967) The small world problem. Psychology Today, 2(1), 60–67.
- Gran73: (1973) The Strength of Weak Ties. The American Journal of Sociology, 78(6), 1360–1380. DOI
- Gran83: (1983) The strength of weak ties: A network theory revisited. Sociological Theory, 1(1), 201–233.
- EdLZ02: (2002) Topological Persistence and Simplification. Discrete & Computational Geometry, 28(4), 511–533. DOI
- PSDV13b: (2013b) Topological Strata of Weighted Complex Networks. PLoS ONE, 8(6), e66506. DOI
- Carl09: (2009) Topology and data. Bulletin of the American Mathematical Society, 46(2), 255–308. DOI
- Feld91: (1991) Why your friends have more friends than you do. American Journal of Sociology, 1464–1477.