The Living Thing / Notebooks : Network 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.

[1]prefixed “complex” to make sure one does not accidentally get sent to a an IT operations conference and have to talk to — brrr — engineers, whilst still letting it sound like it might be difficult and worthy, and certainly more difficult, if not less ambiguous, than “graphs”.

To learn:

To not mention:

Spectral methods

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


Achlioptas, D., Clauset, A., Kempe, D., & Moore, C. (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.
Adcock, A. B., Sullivan, B. D., & Mahoney, M. W.(2014) Tree decompositions and social graphs. arXiv:1411.1546 [physics, Stat].
Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002) A survey on sensor networks. Communications Magazine, IEEE, 40(8), 102–114.
Albert, R., Jeong, H., & Barabási, A.-L. (2000) Error and attack tolerance of complex networks. Nature, 406(6794), 378–382. DOI.
Andriani, P., & McKelvey, B. (2009) Perspective—From Gaussian to Paretian Thinking: Causes and Implications of Power Laws in Organizations. Organization Science, 20(6), 1053–1071. DOI.
Backhaus, S., & Chertkov, M. (2013) Getting a grip on the electrical grid. Physics Today, 66(5), 42. DOI.
Balicer, R. D.(2007) Modeling Infectious Diseases Dissemination Through Online Role-Playing Games:. Epidemiology, 18(2), 260–261. DOI.
Barrat, A., & Weigt, M. (2000) On the properties of small-world network models. The European Physical Journal B-Condensed Matter and Complex Systems, 13(3), 547–560.
Battiston, S., Gatti, D. D., Gallegati, M., Greenwald, B., & Stiglitz, J. E.(2012) Default cascades: When does risk diversification increase stability?. Journal of Financial Stability, 8(3), 138–149. DOI.
Belkin, M., & Niyogi, P. (2003) Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6), 1373–1396. DOI.
Borgs, C., Chayes, J. T., Cohn, H., & Zhao, Y. (2014a) An $L^p$ theory of sparse graph convergence II: LD convergence, quotients, and right convergence. arXiv:1408.0744 [math].
Borgs, C., Chayes, J. T., Cohn, H., & Zhao, Y. (2014b) An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions. arXiv:1401.2906 [math].
Bullmore, E., & Sporns, O. (2009) Complex brain networks: graph theoretical analysis of structural and functional systems. Nature Reviews Neuroscience, 10(3), 186–198. DOI.
Caldarelli, G., Capocci, A., De Los Rios, P., & Muñoz, M. (2002) Scale-Free Networks from Varying Vertex Intrinsic Fitness. Physical Review Letters, 89(25). DOI.
Caldarelli, G., Chessa, A., Pammolli, F., Gabrielli, A., & Puliga, M. (2013) Reconstructing a credit network. Nature Physics, 9(3), 125–126. DOI.
Callaway, D. S., Newman, M. E. J., Strogatz, S. H., & Watts, D. J.(2000) Network Robustness and Fragility: Percolation on Random Graphs. Physical Review Letters, 85(25), 5468–5471. DOI.
Carlsson, G. (2009) Topology and data. Bulletin of the American Mathematical Society, 46(2), 255–308. DOI.
Carlsson, G., Ishkhanov, T., Silva, V. de, & Zomorodian, A. (2008) On the Local Behavior of Spaces of Natural Images. International Journal of Computer Vision, 76(1), 1–12. DOI.
Clauset, A., Newman, M. E. J., & Moore, C. (2004) Finding community structure in very large networks. Physical Review E, 70(6), 066111. DOI.
Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2000) Resilience of the Internet to random breakdowns. Physical Review Letters, 85(21), 4626–4628. DOI.
Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2001) Breakdown of the Internet under intentional attack. Physical Review Letters, 86(16), 3682–3685. DOI.
Cohen, R., & Havlin, S. (2003) Scale-Free Networks Are Ultrasmall. Physical Review Letters, 90(5). DOI.
Cohen-Steiner, D., Edelsbrunner, H., & Harer, J. (2007) Stability of Persistence Diagrams. Discrete & Computational Geometry, 37(1), 103–120. DOI.
Daneshmand, H., Gomez-Rodriguez, M., Song, L., & Schölkopf, B. (2014) Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm. In ICML.
De Domenico, M., Solé-Ribalta, A., Cozzo, E., Kivelä, M., Moreno, Y., Porter, M. A., … Arenas, A. (2013) Mathematical Formulation of Multilayer Networks. Physical Review X, 3(4), 041022. DOI.
Diaconis, P., & Stroock, D. (1991) Geometric Bounds for Eigenvalues of Markov Chains. The Annals of Applied Probability, 1(1), 36–61. DOI.
Dorogovtsev, S. N., & Mendes, J. F.(2013) Evolution of Networks From Biological Nets to the Internet and WWW. . Oxford University Press
Doyle, J. C., Alderson, D. L., Li, L., Low, S., Roughan, M., Shalunov, S., … Willinger, W. (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, D., & Kleinberg, J. (2010) Networks, crowds, and markets: reasoning about a highly connected world. . New York: Cambridge University Press
Edelsbrunner, H., Letscher, D., & Zomorodian, A. (2002) Topological Persistence and Simplification. Discrete & Computational Geometry, 28(4), 511–533. DOI.
Erdős, P., & Rényi, A. (1959) On random graphs I. Publ. Math. Debrecen, 6, 290–297.
Fast Patchwork Bootstrap for Quantifying Estimation Uncertainties in Sparse Random Networks. (n.d.)
Feld, S. L.(1991) Why your friends have more friends than you do. American Journal of Sociology, 1464–1477.
Fosdick, B. K., Larremore, D. B., Nishimura, J., & Ugander, J. (2016) Configuring Random Graph Models with Fixed Degree Sequences. arXiv:1608.00607 [physics, Q-Bio, Stat].
Foster, J. G., Foster, D. V., Grassberger, P., & Paczuski, M. (2010) Edge direction and the structure of networks. Proceedings of the National Academy of Sciences, 107(24), 10815–10820. DOI.
Fox, R. F., & Keizer, J. E.(1990) Effect of molecular fluctuations on the description of chaos by macrovariable equations. Physical Review Letters, 64(3), 249–251. DOI.
Galbiati, M., Delpini, D., & Battiston, S. (2013) The power to control. Nature Physics, 9(3), 126–128. DOI.
Garas, A., Tomasello, M. V., & Schweitzer, F. (2014) Selection rules in alliance formation: strategic decisions or abundance of choice?. arXiv:1403.3298 [physics].
Garcia, D., Mavrodiev, P., & Schweitzer, F. (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.
Garcia, D., Mendez, F., Serdült, U., & Schweitzer, F. (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.
Garlaschelli, D., Ahnert, S., Fink, T., & Caldarelli, G. (2013) Low-Temperature Behaviour of Social and Economic Networks. Entropy, 15(8), 3148–3169. DOI.
Ghrist, R. (2008) Barcodes: The persistent topology of data. Bulletin of the American Mathematical Society, 45(1), 61–75. DOI.
Gilbert, E. N.(1959) Random Graphs. The Annals of Mathematical Statistics, 30(4), 1141–1144. DOI.
Gómez, S., Díaz-Guilera, A., Gómez-Gardeñes, J., Pérez-Vicente, C. J., Moreno, Y., & Arenas, A. (2013) Diffusion Dynamics on Multiplex Networks. Physical Review Letters, 110(2), 028701. DOI.
Granovetter, M. (1983) The strength of weak ties: A network theory revisited. Sociological Theory, 1(1), 201–233.
Granovetter, M. S.(1973) The Strength of Weak Ties. The American Journal of Sociology, 78(6), 1360–1380. DOI.
Greenhill, C., Isaev, M., Kwan, M., & McKay, B. D.(2016) The average number of spanning trees in sparse graphs with given degrees. arXiv:1606.01586 [math].
Holme, P., & Saramäki, J. (2012) Temporal networks. Physics Reports, 519(3), 97–125. DOI.
Hua, L., & Wang, W. (2014) The impact of network structure on innovation efficiency: An agent-based study in the context of innovation networks. Complexity, n/a–n/a. DOI.
Isaev, M., & McKay, B. D.(2016a) Complex martingales and asymptotic enumeration. arXiv:1604.08305 [math].
Isaev, M., & McKay, B. D.(2016b) On a bound of Hoeffding in the complex case. Electronic Communications in Probability, 21(0). DOI.
Kac, M. (1966) Can one hear the shape of a drum?. American Mathematical Monthly, 1–23.
Karsai, M., Kivelä, M., Pan, R. K., Kaski, K., Kertész, J., Barabási, A.-L., & Saramäki, J. (2011) Small but slow world: How network topology and burstiness slow down spreading. Physical Review E, 83(2), 025102. DOI.
Kaushik, R., & Battiston, S. (2013) Credit Default Swaps Drawup Networks: Too Interconnected to Be Stable?. PLoS ONE, 8(7), e61815. DOI.
Kim, M., & Leskovec, J. (2012) Multiplicative Attribute Graph Model of Real-World Networks. Internet Mathematics, 8(1-2), 113–160. DOI.
Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., & Makse, H. A.(2010) Identification of influential spreaders in complex networks. Nature Physics, 6(11), 888–893. DOI.
Klein, D. J., & Randić, M. (1993) Resistance distance. Journal of Mathematical Chemistry, 12(1), 81–95. DOI.
Koenig, M., Battiston, S., Napoletano, M., & Schweitzer, F. (2008) The Efficiency and Evolution of R&D Networks (SSRN Scholarly Paper No. ID 1271877). . Rochester, NY: Social Science Research Network
König, M. D., Battiston, S., Napoletano, M., & Schweitzer, F. (2011) Recombinant knowledge and the evolution of innovation networks. Journal of Economic Behavior & Organization, 79(3), 145–164. DOI.
König, M. D., Battiston, S., Napoletano, M., & Schweitzer, F. (2012) The efficiency and stability of R&D networks. Games and Economic Behavior, 75(2), 694–713. DOI.
Kramer, A. D. I., Guillory, J. E., & Hancock, J. T.(2014) Experimental evidence of massive-scale emotional contagion through social networks. Proceedings of the National Academy of Sciences, 111(24), 8788–8790. DOI.
Kurtz, T. G.(1970) Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes. Journal of Applied Probability, 7(1), 49. DOI.
Lei, J. (2014) A Goodness-of-fit Test for Stochastic Block Models. arXiv:1412.4857 [math, Stat].
Lovász, L. (2012) Large Networks and Graph Limits. . American Mathematical Soc.
Mahoney, M. W.(2016) Lecture Notes on Spectral Graph Methods. arXiv Preprint arXiv:1608.04845.
McKay, B. D., & Wormald, N. C.(1990) Asymptotic Enumeration by Degree Sequence of Graphs of High Degree. European Journal of Combinatorics, 11(6), 565–580. DOI.
Milgram, S. (1967) The small world problem. Psychology Today, 2(1), 60–67.
Miorandi, D., & De Pellegrini, F. (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
Molloy, M., & Reed, B. (1995) A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2-3), 161–180. DOI.
Newman, M. E. J.(2003) Mixing patterns in networks. Physical Review E, 67(2), 026126. DOI.
Newman, M. E. J.(2004) Fast algorithm for detecting community structure in networks. Physical Review E, 69(6), 066133. DOI.
Newman, M. E. J.(2006) Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582. DOI.
Newman, M. E. J., & Girvan, M. (2004) Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113. DOI.
Newman, M. E. J., Strogatz, S. H., & Watts, D. J.(2001) Random graphs with arbitrary degree distributions and their applications. Physical Review E, 64(2), 026118. DOI.
Noh, J. D.(2004) Random Walks on Complex Networks. Physical Review Letters, 92(11). DOI.
Odlyzko, A. M.(1995) Asymptotic Enumeration Methods. In R. L. Graham, M. Grötschel, & L. Lovász (Eds.), Handbook of Combinatorics (Vol. 2) (pp. 1063–1229). Cambridge, MA, USA: MIT Press
Olfati-Saber, R., Fax, J. A., & Murray, R. M.(2007) Consensus and Cooperation in Networked Multi-Agent Systems. Proceedings of the IEEE, 95(1), 215–233. DOI.
Orbanz, P., & Roy, D. M.(2015) Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2), 437–461. DOI.
Palacios, J. L.(2001) Resistance distance in graphs and random walks. International Journal of Quantum Chemistry, 81, 29–33. DOI.
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2004) Statistical mechanics of topological phase transitions in networks. Physical Review E, 69(4). DOI.
Pan, G., Zhang, W., Wu, Z., & Li, S. (2014) Online Community Detection for Large Complex Networks. PLoS ONE, 9(7), e102799. DOI.
Perony, N., Pfitzner, R., Scholtes, I., Tessone, C. J., & Schweitzer, F. (2013) Enhancing Consensus Under Opinion Bias by Means of Hierarchical Decision Making. Advances in Complex Systems, 16(06), 1350020. DOI.
Petri, G., Scolamiero, M., Donato, I., & Vaccarino, F. (2013a) Networks and Cycles: A Persistent Homology Approach to Complex Networks. In T. Gilbert, M. Kirkilionis, & G. Nicolis (Eds.), Proceedings of the European Conference on Complex Systems 2012 (pp. 93–99). Springer International Publishing
Petri, G., Scolamiero, M., Donato, I., & Vaccarino, F. (2013b) Topological Strata of Weighted Complex Networks. PLoS ONE, 8(6), e66506. DOI.
Pfitzner, R., Scholtes, I., Garas, A., Tessone, C. J., & Schweitzer, F. (2013) Betweenness Preference: Quantifying Correlations in the Topological Dynamics of Temporal Networks. Physical Review Letters, 110(19), 198701. DOI.
Pinto, P. C., Thiran, P., & Vetterli, M. (2012) Locating the Source of Diffusion in Large-Scale Networks. Physical Review Letters, 109(6), 068702. DOI.
Pons, P., & Latapy, M. (2005) Computing Communities in Large Networks Using Random Walks. In pInar Yolum, T. Güngör, F. Gürgen, & C. Özturan (Eds.), Computer and Information Sciences - ISCIS 2005 (pp. 284–293). Springer Berlin Heidelberg
Pouget-Abadie, J., & Horel, T. (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–197.
Rapoport, A. (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.
Rapoport, A. (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.
Rapoport, A. (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.
Rapoport, A. (1957) Contribution to the theory of random and biased nets. The Bulletin of Mathematical Biophysics, 19(4), 257–277. DOI.
Richardson, T. O., Perony, N., Tessone, C. J., Bousquet, C. A. H., Manser, M. B., & Schweitzer, F. (2013) Dynamical coupling during collective animal motion. arXiv:1311.1417 [q-Bio].
Rosvall, M., & Bergstrom, C. T.(2008) Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, 105(4), 1118–1123. DOI.
Sarigol, E., Garcia, D., & Schweitzer, F. (2014) Online Privacy as a Collective Phenomenon. arXiv:1409.6197 [cs].
Scholtes, I., Wider, N., Pfitzner, R., Garas, A., Tessone, C. J., & Schweitzer, F. (2013) Slow-Down vs Speed-Up of Diffusion in Non-Markovian Temporal Networks. arXiv:1307.4030 [cond-Mat, Physics:physics].
Schweitzer, F., Fagiolo, G., Sornette, D., Vega-Redondo, F., Vespignani, A., & White, D. R.(2009) Economic Networks: The New Challenges. Science, 325(5939), 422–425. DOI.
Smith, T. C., & Novella, S. P.(2007) HIV Denial in the Internet Era. PLoS Med, 4(8), e256. DOI.
Solé-Ribalta, A., De Domenico, M., Kouvaris, N. E., Díaz-Guilera, A., Gómez, S., & Arenas, A. (2013) Spectral properties of the Laplacian of multiplex networks. Physical Review E, 88(3), 032807. DOI.
Stegehuis, C., van der Hofstad, R., & van Leeuwaarden, J. S. H.(2016) Epidemic spreading on complex networks with community structures. Scientific Reports, 6, 29748. DOI.
Streater, R. F.(2000) Classical and Quantum Probability. arXiv:math-ph/0002049.
Tang, M., Athreya, A., Sussman, D. L., Lyzinski, V., & Priebe, C. E.(2014) A nonparametric two-sample hypothesis testing problem for random dot product graphs. arXiv:1409.2344 [math, Stat].
Tasca, P., Mavrodiev, P., & Schweitzer, F. (2014) Quantifying the impact of leveraging and diversification on systemic risk. Journal of Financial Stability, 15, 43–52. DOI.
Tedeschi, G., Vitali, S., & Gallegati, M. (2014) The dynamic of innovation networks: a switching model on technological change. Journal of Evolutionary Economics, 1–18. DOI.
Tetali, P. (1991) Random walks and the effective resistance of networks. Journal of Theoretical Probability, 4, 101–109. DOI.
Tomasello, M. V., Napoletano, M., Garas, A., & Schweitzer, F. (2013) The Rise and Fall of R&D Networks. arXiv:1304.3623 [physics].
Tomasello, M. V., Perra, N., Tessone, C. J., Karsai, M., & Schweitzer, F. (2014) The role of endogenous and exogenous mechanisms in the formation of R&D networks. Scientific Reports, 4. DOI.
Veitch, V., & Roy, D. M.(2015) The Class of Random Graphs Arising from Exchangeable Random Measures. arXiv:1512.03099 [cs, Math, Stat].
Verma, I. M.(2014) Editorial Expression of Concern: Experimental evidence of massivescale emotional contagion through social networks. Proceedings of the National Academy of Sciences, 201412469. DOI.
Watts, D. J., & Strogatz, S. H.(1998) Collective dynamics of “small-world” networks. Nature, 393(6684), 440–442. DOI.
Yang, S.-H., Long, B., Smola, A., Sadagopan, N., Zheng, Z., & Zha, H. (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.
Zanette, D. (2008) Playing by numbers. Nature, 453(7198), 988–989. DOI.
Zhou, X., Menche, J., Barabási, A.-L., & Sharma, A. (2014) Human symptoms–disease network. Nature Communications, 5. DOI.
Zhou, X. Y.(1993) Resistance dimension, random walk dimension and fractal dimension. Journal of Theoretical Probability, 6, 635–652. DOI.
Zomorodian, A., & Carlsson, G. (2005) Computing Persistent Homology. Discrete & Computational Geometry, 33(2), 249–274. DOI.
Zuev, K., Boguna, M., Bianconi, G., & Krioukov, D. (2015) Emergence of Soft Communities from Geometric Preferential Attachment. Scientific Reports, 5, 9421. DOI.