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

Refs

ACKM05
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.
AdSM14
Adcock, A. B., Sullivan, B. D., & Mahoney, M. W.(2014) Tree decompositions and social graphs. arXiv:1411.1546 [physics, Stat].
ASSC02
Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002) A survey on sensor networks. Communications Magazine, IEEE, 40(8), 102–114.
AlJB00
Albert, R., Jeong, H., & Barabási, A.-L. (2000) Error and attack tolerance of complex networks. Nature, 406(6794), 378–382. DOI.
AnMc09
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.
BaCh13
Backhaus, S., & Chertkov, M. (2013) Getting a grip on the electrical grid. Physics Today, 66(5), 42. DOI.
Bali07
Balicer, R. D.(2007) Modeling Infectious Diseases Dissemination Through Online Role-Playing Games:. Epidemiology, 18(2), 260–261. DOI.
BaWe00
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.
BGGG12
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.
BeNi03
Belkin, M., & Niyogi, P. (2003) Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6), 1373–1396. DOI.
BCCZ14a
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].
BCCZ14b
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].
BuSp09
Bullmore, E., & Sporns, O. (2009) Complex brain networks: graph theoretical analysis of structural and functional systems. Nature Reviews Neuroscience, 10(3), 186–198. DOI.
CCDM02
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.
CCPG13
Caldarelli, G., Chessa, A., Pammolli, F., Gabrielli, A., & Puliga, M. (2013) Reconstructing a credit network. Nature Physics, 9(3), 125–126. DOI.
CNSW00
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.
Carl09
Carlsson, G. (2009) Topology and data. Bulletin of the American Mathematical Society, 46(2), 255–308. DOI.
CISZ08
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.
ClNM04
Clauset, A., Newman, M. E. J., & Moore, C. (2004) Finding community structure in very large networks. Physical Review E, 70(6), 066111. DOI.
CEAH00
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.
CEAH01
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.
CoHa03
Cohen, R., & Havlin, S. (2003) Scale-Free Networks Are Ultrasmall. Physical Review Letters, 90(5). DOI.
CoEH07
Cohen-Steiner, D., Edelsbrunner, H., & Harer, J. (2007) Stability of Persistence Diagrams. Discrete & Computational Geometry, 37(1), 103–120. DOI.
DGSS14
Daneshmand, H., Gomez-Rodriguez, M., Song, L., & Schölkopf, B. (2014) Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm. In ICML.
DSCK13
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.
DiSt91
Diaconis, P., & Stroock, D. (1991) Geometric Bounds for Eigenvalues of Markov Chains. The Annals of Applied Probability, 1(1), 36–61. DOI.
DoMe13
Dorogovtsev, S. N., & Mendes, J. F.(2013) Evolution of Networks From Biological Nets to the Internet and WWW. . Oxford University Press
DALL05
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.
EaKl10
Easley, D., & Kleinberg, J. (2010) Networks, crowds, and markets: reasoning about a highly connected world. . New York: Cambridge University Press
EdLZ02
Edelsbrunner, H., Letscher, D., & Zomorodian, A. (2002) Topological Persistence and Simplification. Discrete & Computational Geometry, 28(4), 511–533. DOI.
ErRé59
Erdős, P., & Rényi, A. (1959) On random graphs I. Publ. Math. Debrecen, 6, 290–297.
00
Fast Patchwork Bootstrap for Quantifying Estimation Uncertainties in Sparse Random Networks. (n.d.) http://www.mlgworkshop.org/2016/paper/MLG2016_paper_32.pdf.
Feld91
Feld, S. L.(1991) Why your friends have more friends than you do. American Journal of Sociology, 1464–1477.
FLNU16
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].
FFGP10
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.
FoKe90
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.
GaDB13
Galbiati, M., Delpini, D., & Battiston, S. (2013) The power to control. Nature Physics, 9(3), 126–128. DOI.
GaTS14
Garas, A., Tomasello, M. V., & Schweitzer, F. (2014) Selection rules in alliance formation: strategic decisions or abundance of choice?. arXiv:1403.3298 [physics].
GaMS13
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.
GMSS12
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.
GAFC13
Garlaschelli, D., Ahnert, S., Fink, T., & Caldarelli, G. (2013) Low-Temperature Behaviour of Social and Economic Networks. Entropy, 15(8), 3148–3169. DOI.
Ghri08
Ghrist, R. (2008) Barcodes: The persistent topology of data. Bulletin of the American Mathematical Society, 45(1), 61–75. DOI.
Gilb59
Gilbert, E. N.(1959) Random Graphs. The Annals of Mathematical Statistics, 30(4), 1141–1144. DOI.
GDGP13
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.
Gran83
Granovetter, M. (1983) The strength of weak ties: A network theory revisited. Sociological Theory, 1(1), 201–233.
Gran73
Granovetter, M. S.(1973) The Strength of Weak Ties. The American Journal of Sociology, 78(6), 1360–1380. DOI.
GIKM16
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].
HoSa12
Holme, P., & Saramäki, J. (2012) Temporal networks. Physics Reports, 519(3), 97–125. DOI.
HuWa14
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.
IsMc16a
Isaev, M., & McKay, B. D.(2016a) Complex martingales and asymptotic enumeration. arXiv:1604.08305 [math].
IsMc16b
Isaev, M., & McKay, B. D.(2016b) On a bound of Hoeffding in the complex case. Electronic Communications in Probability, 21(0). DOI.
Kac66
Kac, M. (1966) Can one hear the shape of a drum?. American Mathematical Monthly, 1–23.
KKPK11
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.
KaBa13
Kaushik, R., & Battiston, S. (2013) Credit Default Swaps Drawup Networks: Too Interconnected to Be Stable?. PLoS ONE, 8(7), e61815. DOI.
KiLe12
Kim, M., & Leskovec, J. (2012) Multiplicative Attribute Graph Model of Real-World Networks. Internet Mathematics, 8(1-2), 113–160. DOI.
KGHL10
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.
KlRa93
Klein, D. J., & Randić, M. (1993) Resistance distance. Journal of Mathematical Chemistry, 12(1), 81–95. DOI.
KBNS08
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
KBNS11
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.
KBNS12
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.
KrGH14
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.
Kurt70
Kurtz, T. G.(1970) Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes. Journal of Applied Probability, 7(1), 49. DOI.
Lei14
Lei, J. (2014) A Goodness-of-fit Test for Stochastic Block Models. arXiv:1412.4857 [math, Stat].
Lová12
Lovász, L. (2012) Large Networks and Graph Limits. . American Mathematical Soc.
Maho16
Mahoney, M. W.(2016) Lecture Notes on Spectral Graph Methods. arXiv Preprint arXiv:1608.04845.
McWo90
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.
Milg67
Milgram, S. (1967) The small world problem. Psychology Today, 2(1), 60–67.
MiDe10
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
MoRe95
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.
Newm03
Newman, M. E. J.(2003) Mixing patterns in networks. Physical Review E, 67(2), 026126. DOI.
Newm04
Newman, M. E. J.(2004) Fast algorithm for detecting community structure in networks. Physical Review E, 69(6), 066133. DOI.
Newm06
Newman, M. E. J.(2006) Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582. DOI.
NeGi04
Newman, M. E. J., & Girvan, M. (2004) Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113. DOI.
NeSW01
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.
Noh04
Noh, J. D.(2004) Random Walks on Complex Networks. Physical Review Letters, 92(11). DOI.
Odly95
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
OlFM07
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.
OrRo15
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.
Pala01
Palacios, J. L.(2001) Resistance distance in graphs and random walks. International Journal of Quantum Chemistry, 81, 29–33. DOI.
PDFV04
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2004) Statistical mechanics of topological phase transitions in networks. Physical Review E, 69(4). DOI.
PZWL14
Pan, G., Zhang, W., Wu, Z., & Li, S. (2014) Online Community Detection for Large Complex Networks. PLoS ONE, 9(7), e102799. DOI.
PPST13
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.
PSDV13a
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
PSDV13b
Petri, G., Scolamiero, M., Donato, I., & Vaccarino, F. (2013b) Topological Strata of Weighted Complex Networks. PLoS ONE, 8(6), e66506. DOI.
PSGT13
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.
PiTV12
Pinto, P. C., Thiran, P., & Vetterli, M. (2012) Locating the Source of Diffusion in Large-Scale Networks. Physical Review Letters, 109(6), 068702. DOI.
PoLa05
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
PoHo15
Pouget-Abadie, J., & Horel, T. (2015) Inferring Graphs from Cascades: A Sparse Recovery Framework. In Proceedings of The 32nd International Conference on Machine Learning.
Prot87
Protter, M. H.(1987) Can one hear the shape of a drum? Revisited. Siam Review, 29(2), 185–197.
Rapo53a
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.
Rapo53b
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.
Rapo54
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.
Rapo57
Rapoport, A. (1957) Contribution to the theory of random and biased nets. The Bulletin of Mathematical Biophysics, 19(4), 257–277. DOI.
RPTB13
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].
RoBe08
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.
SaGS14
Sarigol, E., Garcia, D., & Schweitzer, F. (2014) Online Privacy as a Collective Phenomenon. arXiv:1409.6197 [cs].
SWPG13
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].
SFSV09
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.
SmNo07
Smith, T. C., & Novella, S. P.(2007) HIV Denial in the Internet Era. PLoS Med, 4(8), e256. DOI.
SDKD13
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.
StHL16
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.
Stre00
Streater, R. F.(2000) Classical and Quantum Probability. arXiv:math-ph/0002049.
TASL14
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].
TaMS14
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.
TeVG14
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.
Teta91
Tetali, P. (1991) Random walks and the effective resistance of networks. Journal of Theoretical Probability, 4, 101–109. DOI.
TNGS13
Tomasello, M. V., Napoletano, M., Garas, A., & Schweitzer, F. (2013) The Rise and Fall of R&D Networks. arXiv:1304.3623 [physics].
TPTK14
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.
VeRo15
Veitch, V., & Roy, D. M.(2015) The Class of Random Graphs Arising from Exchangeable Random Measures. arXiv:1512.03099 [cs, Math, Stat].
Verm14
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.
WaSt98
Watts, D. J., & Strogatz, S. H.(1998) Collective dynamics of “small-world” networks. Nature, 393(6684), 440–442. DOI.
YLSS11
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.
Zane08
Zanette, D. (2008) Playing by numbers. Nature, 453(7198), 988–989. DOI.
ZMBS14
Zhou, X., Menche, J., Barabási, A.-L., & Sharma, A. (2014) Human symptoms–disease network. Nature Communications, 5. DOI.
Zhou93
Zhou, X. Y.(1993) Resistance dimension, random walk dimension and fractal dimension. Journal of Theoretical Probability, 6, 635–652. DOI.
ZoCa05
Zomorodian, A., & Carlsson, G. (2005) Computing Persistent Homology. Discrete & Computational Geometry, 33(2), 249–274. DOI.
ZBBK15
Zuev, K., Boguna, M., Bianconi, G., & Krioukov, D. (2015) Emergence of Soft Communities from Geometric Preferential Attachment. Scientific Reports, 5, 9421. DOI.