## Complex Networks

*02 Sep 2015 02:33*

Having written a whole pop-sci article about these things (see below), I won't explain them at all here. This notebook is more of a placeholder than usual.

Stuff I should learn more about: structural complexity measures for graphs
and ensembles of random graphs; Gibbs measures for
equilibrium ensembles of graphs; Markovian graphs. Why does it seem like
the *edges* are the important random variables, rather than the nodes?

Data analysis in general and community discovery in particular get their own notebooks. So does the connection between network topology and synchronization. The "homophily or influence?" problem. Graph limits and infinite exchangeable arrays. Embedding networks in hyperbolic spaces. Graph sampling algorithms, i.e., procedures for efficiently generating graphs with specified properties. Spectral properties.

See also: Biochemical Network Evolution; Citations and Citation Networks; Ecology; Graph Theory; Neuroscience; Signal Transduction, Gene Regulation and Control of Metabolism; Social Networks; Sociology of Science; Statistical Mechanics; Synchronization

- Recommended, big picture:
- Reka Albert and Albert-László Barabási, "Statistical Mechanics of Complex Networks," cond-mat/0106096
- Alain Barrat, Marc Barthelemy and Alessandro Vespignani, Dynamical Processes on Complex Networks
- Rick Durrett, Random Graph Dynamics
- Mark E. J. Newman
- "The structure and function of complex networks," cond-mat/0303516
- Networks: An Introduction [A.k.a. "the big black book"]

- Mark Newman, Albert-László Barabási, and Duncan Watts (eds.), "The Structure and Dynamics of Networks [Collects many of the most important papers from the pre-history of the 1950s up through the early 2000s]
- Duncan Watts
- Small Worlds
- "The 'New' Science of Networks", Annual
Review of Sociology
**30**(2004): 243--270

- Recommended, close-ups:
- Yael Artzy-Randrup, Sarel J. Fleishman, Nir Ben-Tal and Lewi Stone,
"Comment on 'Network Motifs: Simple Building Blocks of Complex Networks' and
'Superfamilies of Evolved and Designed Networks'", Science
**305**(2004): 1107 - M. Argollo de Menezes and A.-L. Barabási, "Fluctuations in network dynamics", Physical Review Letters 92 (2004): 028701, cond-mat/0306304
- Aaron Clauset and Cristopher Moore, "How Do Networks Become Navigable?", cond-mat/0309415
- Santo Fortunato, Alessandro Flammini, Filippo Menczer, "Scale-free network growth by ranking", cond-mat/0602081
- Vamsi Kalapala, Vishal Sanwalani, Aaron Clauset, and Cristopher
Moore, "Scale Invariance in Road
Networks", physics/0510198
= Physical Review E
**73**(2006): 026130 - Eben Kenah and James Robins, "Second look at the spread of epidemics on networks", q-bio.QM/0610057
- Raya Khanin and Ernst Wit, "How Scale-Free Are Biological
Networks?",
Journal of Computational Biology
**13**(2006): 810--818 [Ans.: not very scale-free at all.] - Evelyn Fox Keller, "Revisiting 'scale-free'
networks", BioEssays
**27**(2005): 1060--1068 - Judith Kleinfeld, "Could It Be a Big World After All? What the
Milgram Papers in the Yale Archive Reveal About the Original Small World Study"
[Six degrees of separation,
*for the general population,*is quite unsupported empirically. Of course it works for other kinds of networks, e.g., people in a common profession, or participating in a common institution; but that's different. Preprint.] - Arnon Levy and William Bechtel, "Abstraction and the Organization of Mechanisms", Philosophy
of Science
**80**(2013): 241--261 - Adrián López García de Lomana, Qasim K. Beg,
G. de Fabritiis and Jordi Villà-Freixa, "Statistical Analysis of Global
Connectivity and Activity Distributions in Cellular
Networks", Journal of
Computational Biology
**17**(2010): 869--878, arxiv:1004.3138 - Manul Middendorf, Etay Ziv and Chris Wiggins, "Inferring Network
Mechanisms: The
*Drosophila melanogaster*Protein Interaction Network", q-bio.QM/0408010 [Machine learning meets complex networks: specifically, learning decision trees to accurately classify networks by the process which grew them. Neat.] - Cristopher Moore, Gourab Ghoshal and Mark E. J. Newman, "Exact
solutions for models of evolving networks with addition and deletion of
nodes", cond-mat/0604069
= Physical Review
E
**74**(2006): 036121 [The most amusing result is that in a network where new nodes form links by preferential attachment, but the size of addition and deletion of nodes exactly balance, the degree distribution follows a stretched exponential (Weibull) distribution, rather than a power law. This suggests, as they note, that the current exponent for the web should increase as its growth-rate slows. "A sufficiently large exponent would make the distribution indistinguishable experimentally from an exponential or stretched exponential distribution, although we do not realistically anticipate seeing behaivor of this type any time in the near future."] - Mark E. J. Newman
- "Analysis of weighted networks", cond-mat/0407503
- "Assortative mixing in networks," cond-mat/0205405
- "Clustering and Preferential Attachment in Growing Networks," cond-mat/0104029
- "Ego-centered networks and the ripple effect," cond-mat/0111070
- "Exact solutions of epidemic models on networks," cond-mat/0201433
- "Properties of highly clustered networks," cond-mat/0303183
- "Random graphs as models of networks," cond-mat/0202208
- "The spread of epidemic disease on networks," cond-mat/0205009

- Robin Pemantle and Brian Skyrms, "Network formation by
reinforcement learning: the long and medium run", math.PR/0404106 =
Mathematical Social Sciences
**48**(2004): 315--327 - David M. Pennock et al., "Winners don't take all: Characterizing
the competition for links on the web", Proceedings of the National
Academy of Sciences
**99**(2002): 5207--5211 - Bo Söderberg, "A General Formalism for Inhomogeneous Random Graphs", cond-mat/0211063 [A re-invention of block models, but a clear one]
- Ricard V. Sole, Romualdo Pastor-Satorras, Eric Smith and Thomas
B. Kepler, "A model of large-scale proteome evolution," Advances in
Complex Systems
**5**(2002): 43ff = cond-mat/0207311 - R. Vilela Mendes, "Tools for Network Dynamics", International Journal
of Bifurcations and Chaos
**15**(2005): 1185--1213 [There is, admittedly, something of a bias here towards tools devised by Vilela Mendes and collaborators, but I daresay I'd do the same were I to write such a piece. More importantly, they're good stuff.] - Duncan Watts and Steven Strogatz, "Collective Dynamics of
`Small-World' Networks," Nature
**393**(1998): 440--442

- Noted, but not fully recommended:
- Kartik Anand and Ginestra Bianconi, "Entropy measures for networks:
Toward an information theory of complex
topologies", Physical
Review E
**80**(2009): 045102 = arxiv:0907.1514 [Basic calculations comparing the log of the number of graphs compatible with given macroscopic properties (the Boltzmann entropy; weirdly called the Gibbs entropy here) with the Shannon entropy of the distribution of graphs where those properties hold in the mean (which is the actual Gibbs entropy in statistical mechanics). These are not equivalent, which evidently causes some distress to the authors; no mention of the literature on ensemble in-equivalence and its roots (see e.g. the references here) or to the vast literature on exponential families of random graphs (i.e., ensembles of maximum Shannon entropy).]

- Modesty forbids me to recommend:
- CRS, "Growth, Form, Function, Crashes," Santa Fe Institute
Bulletin
**15:2**(2000) [On-line] - CRS, "Networks and Netwars"

- To read:
- Juan A. Acebrón, Sergi Lozano, and Alex Arenas,
"Amplified Signal Response in Scale-Free Networks by Collaborative Signaling",
Physical Review
Letters
**99**(2007): 128701 - Lada A. Adamic, R. M. Lukose, A. R. Puniyani and Bernardo A. Huberman, "Search in Power-Law Networks," cs.NI/0103016
- Reka Albert, Istvan Albert and Gary L. Nakarad, "Structural Vulnerability of the North American Power Grid", cond-mat/0401084
- David J. Aldous, "A Tractable Complex Network Model based on the Stochastic Mean-field Model of Distance", cond-mat/0304701
- Eivind Almaas and A.-L. Barabási, "Power laws in biological networks", q-bio.MN/0401010
- Tanya Araujo, R. Vilela Mendes and Joao Seixas, "A dynamical characterization of the small world phase," cond-mat/0204573
- Alex Arenas, Albert Diaz-Guilera, Jurgen Kurths, Yamir Moreno,
Changsong Zhou, "Synchronization in complex networks", Physics
Reports
**469**(2008): 93--153, arxiv:0805.2976 - M. Argollo de Menezes and A.-L. Barabási, "Separating internal and external dynamics of complex systems", cond-mat/0406421
- K. B. Athreya, A. P. Ghosh, S. Sethuraman, "Growth of preferential attachment random graphs via continuous-time branching processes", math.PR/0701649
- J. P. Bagrow, E. M. Bollt, J. D. Skufca, D. ben-Avraham, "Portraits of Complex Networks", cond-mat/0703470
- Duygu Balcan and Ayse Erzan, "Content-based networks: A pedagogical
overview", Chaos
**17**(2007): 026108 - Pierre Baldi et al., Modeling the Internet and the Web: Probabilistic Methods and Algorithms
- Frank Ball, Tom Britton, David Sirl, "A network with tunable clustering, degree correlation and degree distribution, and an epidemic thereon", arxiv:1207.3205
- Frank Ball and David Sirl, "An SIR epidemic model on a population with random network and household structure, and several types of individuals",
Advances in Applied
Probability
**44**(2012): 63--86 - L. Barnett, C. L. Buckley, S. Bullock, "A Graph Theoretic Interpretation of Neural Complexity", arxiv:1011.5334
- F. Barra and P. Gaspard, "Classical Dynamics on Graphs," nlin.CD/0011045
- Alain Barrat, Marc Barthelemy and Alessandro Vespignani
- "Weighted evolving networks: coupling topology and weights
dynamics", cond-mat/0401057
= PRL
**92**(2004): 228701 - "Modeling the evolution of weighted networks", cond-mat/0406238
- "The effects of spatial constraints on the evolution of weighted complex networks", physics/0504029

- "Weighted evolving networks: coupling topology and weights
dynamics", cond-mat/0401057
= PRL
- Yaneer Bar-Yam and Irving R. Epstein, "Response of complex networks to stimuli", Proceedings of the National Academy of Sciences 10.1073/pnas.0400673101
- E. Ben-Naim and P.L. Krapivsky, "Addition-Deletion Networks", cond-mat/0703636
- Eli Ben-Naim and Zoltan Toroczkai (eds.), Complex Networks
- N. Berger, C. Borgs, J. T. Chayes, R. M. D'Souza and R. D.
Kleinberg
- "Competition-Induced Preferential Attachment", cond-mat/0402268 [Short version]
- "Degree Distribution of Competition-Induced Preferential Attachment Graphs", cond-mat/0502205 [Version with proofs]

- Cristoly Biely and Stefan Thurner, "Statistical mechanics of scale-free networks at a critical point: Complexity without irreversibility?", cond-mat/0507670
- Ginestra Bianconi, "A statistical mechanics approach for scale-free networks and finite-scale networks", cond-mat/0703191
- Ginestra Bianconi and Matteo Marsili, "Clogging and self-organized
criticality in complex networks", Physical Review
E
**70**(2004): 035105(R), cond-mat/0312537 - Sven Bilke and C. Peterson, "Topological Properties of Citation and Metabolic Networks", cond-mat/0103361
- Sven Bilke and F. Sjunnesson, "Stability of the Kauffman Model," cond-mat/0107035
- Golnoosh Bizhani, Peter Grassberger, and Maya Paczuski, "Random
sequential renormalization and agglomerative percolation in networks:
Application to Erdos-Renyi and scale-free
graphs", Physical
Review E
**84**(2011): 066111 - Philippe Blanchard and T. Krueger, "The `Cameo Principle' and the Origin of Scale-Free Graphs in Social Networks," cond-mat/0302611
- Christian Borgs, Jennifer Chayes, Constantinos Daskalakis, Sebastien Roch, "First to Market is not Everything: an Analysis of Preferential Attachment with Fitness", arxiv:0710.4982 ["rigorous analysis of preferential attachment with fitness ... Depending on the shape of the fitness distribution, we observe three distinct phases: a first-mover-advantage phase, a fit-get-richer phase and an innovation-pays-off phase."]
- Stefan Bornholdt and H. G. Schuster (eds.), Handbook of Graphs and Networks: From the Genome to the Internet
- Romulus Breban, Raffaele Vardavas and Sally Blower,
"Linking population-level models with growing networks: A class of epidemic models", Physical Review E
**72**(2005): 046110 - Markus Brede and Sitabhra Sinha, "Assortative mixing by degree makes a network more unstable", cond-mat/0507710
- Tom Britton and Mathias Lindholm, "Dynamic Random Networks in Dynamic Populations", Journal of Statistical Physics
**139**(2010): 518--535 - Dirk Brockmann and Dirk Helbing, "The Hidden Geometry of Complex, Network-Driven Contagion Phenomena", Science
**342**(2013): 1337--1342 - Z. Burda, J. D. Correia and Andre Krzywicki, "Statistical ensemble of scale-free random graphs," cond-mat/0104155
- Guido Caldarelli, Scale-Free Networks: Complex Webs in Nature and Technology
- Guido Caldarelli and Alessandro Vespignani (eds.), Large Scale Structure and Dynamics of Complex Networks: From Information Technology to Finance and Natural Science
- Callaway, Hopcroft, Kleinberg, Newman and Strogatz, "Are Randomly Grown Graphs Really Random?" cond-mat/0104546
- J. Camacho, R. Guimera and L. A. N. Amaral, "Robust Patterns in Food Web Structure," cond-mat/0103114
- Andrea Capocci, G. Caldarelli and P. De Los Rios, "Quantitative description and modeling of real networks," cond-mat/0206336
- Damon Centola, "Failure in Complex Social Networks",
Journal of Mathematical
Sociology
**33**(2009): 654--68 - Sourav Chatterjee and Partha S. Dey, "Applications of Stein's method for concentration inequalities", Annals of Probability
**38**(2010): 2443--2485, arxiv:0906.1034 - Mario Chavez, Miguel Valencia, Vito Latora, Jacques Martinerie, "Complex networks: new trends for the analysis of brain connectivity", arxiv:1002.0697
- Fan Chung and Linyuan Lu, Complex Graphs and Networks
- L. Cisneros, J. Jimenez, M. G. Cosenza, and A. Parravano, "Information transfer and nontrivial collective behavior in chaotic coupled map networks," nlin.CD/0202010
- Jens Christian Claussen, "Offdiagonal Complexity: A computationally quick complexity measure for graphs and networks", q-bio.MN/0410024
- Mauro Copelli, Paulo R. A. Campos, "Excitable Scale Free Networks", q-bio.NC/0703004
- M. Copelli, R. M. Zorzenon dos Santos and J. S. Sa Martins, "Emergence of Hierarchy on a Network of Complementary Agents," cond-mat/0110350
- Francois Coppex, Michel Droz and Adam Lipowski, "Extinction dynamics of Lotka-Volterra ecosystems on evolving networks", q-bio.PE/0312030
- Luciano da F. Costa, Francisco A. Rodrigues, Gonzalo Travieso and P. R. Villas Boas, "Characterization of complex networks: A survey of measurements", cond-mat/0505185
- Luciano da F. Costa and Olaf Sporns, "Hierarchical Features of Large-Scale Cortical Connectivity", q-bio.NC/0508007
- R. W. R. Darling and J. R. Norris, "Structure of large random
hypergraphs", Annals of Applied
Probability
**15**(2005): 125--152, math.PR/0503460 - M. A. M. de Aguiar and Y. Bar-Yam, "Spectral Analysis and the Dynamic Response of Complex Networks", nlin.AO/0306043
- Charo I. Del Genio, Thilo Gross, and Kevin E. Bassler, "All Scale-Free Networks Are Sparse", Physical Review Letters
**107**(2011): 178701 - Peter Dodds and Duncan Watts, "Universal behavior in a generalized model of contagion", cond-mat/0403699
- S. N. Dorogovtsev, "Renormalization group for evolving networks," cond-mat/0301008
- S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes
- "Correlations in interacting systems with a network topology", cond-mat/0506002 [Claims to have an argument establishing "dramatic weakening of correlations between second and more distant neighbors on networks with fat-tailed degree distributions", such that in the large size limit "only the pair correlations between the nearest neighbors are observable". I'm skeptical that they could have an adequately general argument to really establish this, but I'll read it before coming to any conclusion.]
- "Ising Model on Networks with an Arbitrary Distribution of Connections," cond-mat/0203227
- "Pseudofractal Scale-free Web," cond-mat/0112143

- S. N. Dorogovtsev and J. F. F. Mendes
- "Comment on `Breakdown of the Internet under Intentional Attack'," cond-mat/0109083
- "Evolution of random networks," cond-mat/0106144
- Evolution of Networks: From Biological Nets to the Internet and WWW

- S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin
- "Anomalous percolating properties of growing networks," cond-mat/0106141
- "Giant strongly connected component of directed networks," cond-mat/0103629

- Raissa M. D'Souza, Soumen Roy, "Network Growth with Feedback", arxiv:0805.4020
- Holger Ebel, Lutz-Ingo Mielsch and Stefan Bornholdt, "Scale-free topology of e-mail networks," cond-mat/0201476
- Jean-Pierre Eckmann and Elisha Moses, "Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web," cond-mat/0110338
- Victor M. Eguiluz, Dante R. Chialvo, Guillermo A. Cecchi, Marwan
Baliki and A. Vania Apkarian, "Scale-free brain functional networks",
Physical Review
Letters
**94**(2005): 018102, cond-mat/0309092 - Ernesto Estrada and Juan A. Rodriguez-Velazquez
- "Complex Networks as Hypergraphs", physics/0505137
- "Subgraph Centrality in Complex Networks", cond-mat/0504730

- Ying Fan, Menghui Li, Jiawei Chen, Liang Gao, Zengru Di and Jinshan Wu, "Network of Econophysicists: a weighted network to investigate the development of Econophysics", cond-mat/0401054
- Nadia Farid and Kim Christensen, "Evolving networks through deletion and duplication", physics/0609172
- Iles Farkas, I. Derenyi, H. Jeong, Z. Neda, Z. N. Oltvai, E. Ravasz, A. Schubert, Albert-László Barabási and Tamas Vicsek, "Networks in life: Scaling properties and eigenvalue spectra," cond-mat/0303106
- Iles Farkas, I. Derenyi, G. Palla, and T. Vicsek, "Equilibrium statistical mechanics of network structures", cond-mat/0401640
- Iles J. Farkas, H. Jeong, Tamas Vicsek, Albert-László Barabási and
Z. N. Oltvai, "The topology of the transcription regulatory network in the
yeast,
*S. cerevisiae*," cond-mat/0205181 - Trevor Fenner, Mark Levene and George Loizou, "A Model for Collaboration Networks Giving Rise to a Power Law Distribution with an Exponential Cutoff", physics/0503184
- Ramon Ferrer i Cancho and Ricard V. Sole
- "The Small-World of Human Language," SFI Working Paper 01-03-016
- "Optimization in complex networks," cond-mat/01 1222

- Agata Fronczak, Piotr Fronczak, Janusz A. Holyst,
"Fluctuation-dissipation relations for complex
networks", cond-mat/0509042, Physical
Review E
**73**(2006): 016108 [The fluctuations are*fluctuations of the network structure*within an equilibrium ensemble. This is an interesting idea, though I'd need to not just read it but also think carefully before deciding whether it really applies to actual networks] - Diego Garlaschelli, Sebastian E. Ahnert, Thomas M. A. Fink and Guido Caldarelli, "Temperature in complex networks", cond-mat/0606805
- Kwang-Il Goh, B. Kahng, and D. Kim, "Spectra and eigenvectors of scale-free networks," cond-mat/0103337
- Kwang-Il Goh, E. S. Oh, H. Jeong, B. Kahng, and D. Kim, "Classification of scale free networks," cond-mat/0205232
- Michael Golosovsky and Sorin Solomon, "Stochastic Dynamical Model
of a Growing Citation Network Based on a Self-Exciting Point
Process", Physical
Review Letters
**109**(2012): 098701 - A. V. Goltsev, S. N. Dorogovtsev and J. F. F. Mendes, "Critical Phenomena in Networks," cond-mat/0204596
- Jesus Gomez-Gardenes and Vito Latora, "Entropy rate of diffusion processes on complex networks", Physical
Review E
**78**(2008): 065102 - Sean P. Gorman, Rajendra G. Kulkarni, Laurie A. Schintler and Roger R. Stough, "A Predator Prey Approach to Diversity Based Defenses in Heterogeneous Networks", cond-mat/0401017
- Geoffrey Grimmett, Probability on Graphs: Random Processes on Graphs and Lattices [Author's book site, including errata and PDF]
- Andreas Grönlund, "The difference in directed structure of Neural and Transcriptional Regulation Networks", cond-mat/0406268
- Andreas Grönlund, Kim Sneppen and Petter Minnhagen, "Correlations in Networks Associated to Preferential Growth", cond-mat/0401537
- Thilo Gross and Bernd Blasius, "Adaptive Coevolutionary Networks -- A Review", arxiv:0709.1858
- Jean-Loup Guillaume and Matthieu Latap, "A Realistic Model for Complex Networks," cond-mat/0307095
- Roger Guimera, A. Arenas and A. Diaz-Guilera, "Communication and optimal hierarchical networks," cond-mat/0103112
- Aric Hagberg, Pieter J. Swart and Daniel A. Schult, "Designing
threshold networks with given structural and dynamical properties", Physical Review
E
**74**(2006): 056116 - Laurent Hébert-Dufresne, Pierre-André Noël, Vincent Marceau, Antoine Allard, Louis J. Dubé, "Propagation dynamics on networks featuring complex topologies", arxiv:1005.1397
- Adriano de Jesus Holanda, Ivan Torres Pisa, Osame Kinouchi, Alexandre Souto Martinez and Evandro Eduardo Seron Ruiz, "Thesaurus as a complex network", cond-mat/0312586
- Petter Holme
- "Core-periphery organization of complex networks", physics/0506035
- "Scale-free networks with a large- to small-world transition", cond-mat/0607111
- "Signatures of Currency Vertices", arxiv:0812.3487

- Petter Holme, Christofer R. Edling and Frederik Liljeros,
"Structure and time evolution of an Internet dating community", Social
Networks
**26**(2004): 155-174 - Petter Holme and Gourab Ghoshal, "Dynamics of Networking Agents
Competing for High Centrality and Low
Degree", Physical Review
Letters
**96**(2006): 098701 - Petter Holme and Beom Jun Kim
- "Growing Scale-Free Networks with Tunable Clustering," cond-mat/0110452
- "Vertex overload breakdown in evolving networks," cond-mat/0204120

- Takashi Icinomiya, "Path-integral approach to the dynamics of a
sparse random network", cond-mat/0507285 = Physical Review
E
**72**(2005): 016109 - Mads Ipsen and Alexander S. Mikhailov, "Evolutionary reconstruction of networks," nlin.AO/0111023
- Shalev Itzkovitz, Reuven Levitt, Nadav Kashtan, Ron Milo, Michael Itzkovitz and Uri Alon, "Coarse-Graining and Self-Dissimilarity of Complex Networks", q-bio.MN/0405011
- Junji Ito and Kunihiko Kaneko, "Spontaneous structure formation in a network of chaotic units with variable connection strengths," cond-mat/0108408
- Sarika Jalan and R. E. Amritkar, "Self-organized and driven phase synchronization in coupled map scale free networks," nlin.AO/0201051
- Henrik Jeldtot Jensen, "Emergence of Network Structure in Models of Collective Evolution and Evolutionary Dynamics", arxiv:0709.2009
- Jürgen Jost and M. P. Joy, "Evolving networks with distance preferences," cond-mat/0202343
- Alon Keinan, Ben Sandbank, Claus C. Hilgetag, Isaac Meilijson and
Eytan Ruppin, "Fair Attribution of Functional Contribution in Artificial and
Biological Networks", Neural
Computation
**16**(2004): 1887--1915 - Susan Khor, "Concurrency and Network Disassortativity",
Artificial Life
**16**(2010): 225--232 - Beom Jun Kim, "Performance of networks of artificial neurons: The role of clustering", q-bio.NC/0402045
- Beom Jun Kim, Ala Trusina, Petter Holme, Petter Minnhagen, Jean S. Chung, and M. Y. Choi, "Dynamic instabilities induced by asymmetric influence: Prisoners' dilemma game on small-world networks," cond-mat/0206533
- Beom Jun Kim, Chang No Yoon, Seung Kee Han, and Hawoong Jeong, "Path finding strategies in scale-free networks," cond-mat/0111232
- J. Kim, P. L. Krapivsky, B. Kahng and Sidney Redner, "Evolving Protein Interaction Networks," cond-mat/0203167
- Osame Kinouchi, A. S. Martinez, G. F. Lima, G. M. Lourenco, S. Risau-Gusman, "Deterministic walks in random networks: an application to thesaurus graphs," cond-mat/0110217
- P. L. Krapivsky and Sidney Redner, "Finiteness and Fluctuations in Growing Networks," cond-mat/0207107
- P. L. Krapivsky, Sidney Redner, and F. Leyvraz, "Connectivity of Growing Random Networks," cond-mat/0005139
- Andre Krzywicki, "Defining statistical ensembles of random graphs," cond-mat/0110574
- Marcelo Kuperman and Damian Zanette, "Stochastic resonance in a
model of opinion formation on small-world networks,"
cond-mat/0111289 [
*Of course*social psychology has to be just like the Ising model; how else could physicists study it?] - Maciej Kurant and Patrick Thiran, "Layered Complex Networks", physics/0510194
- D.-S. Lee, K.-I. Goh, B. Kahng and D. Kim, "Sandpile avalanche dynamics on scale-free networks", cond-mat/0401531
- E. A. Leicht, Petter Holme, and M. E. J. Newman, "Vertex similarity in networks", physics/0510143
- Chunguang Li, Philip K. Maini, "An evolving network model with
community
structure", physics/0510239, Journal
of Physics A: Mathematical and General
**38**(2005): 9741--9749 - Lun Li, David Alderson, Reiko Tanaka, John C. Doyle and Walter Willinger, "Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications", cond-mat/0501169 ["Although the ``scale-free'' literature is large and growing, it gives neither a precise definition of scale-free graphs nor rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and verifiably false claims." Ouch.]
- Susanna C. Manrubia, Jordi Delgado, and Bartolo Luque, "Small-world behavior in a system of mobile elements," cond-mat/0102069
- Sergei Maslov and Kim Sneppen
- "Pattern Detection in Complex Networks: Correlation Profile of the Internet," cond-mat/0205379 [Physicists rediscover bootstrap testing]
- "Specificity and stability in topology of protein networks," cond-mat/0205380

- Vincent Marceau, Pierre-André Noël, Laurent Hébert-Dufresne, Antoine Allard, Louis J. Dubé, "Adaptive networks: coevolution of disease and topology", arxiv:1005.1299
- Carsten Marr, Marc-Thorsten Huett, "Outer-totalistic cellular automata on graphs", Physics Letters A
**373**(2008): 546--549, arxiv:0812.2408 - Raoul-Martin Memmesheimer and Marc Timme, "Designing Complex Networks", q-bio.NC/0606041 [i.e., designing networks of stylized neurons to spike in a given periodic pattern. Well, it's a start...]
- Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai
Shen-Orr, Inbal Ayzenshtat, Michal Sheffer and Uri Alon, "Superfamilies of
Evolved and Designed Networks", Science
**303**(2004): 1538--1542 - Andre A. Moreira, Jose S. Andrade, Hans J. Herrmann, Joseph O. Indekeu, "How to make a fragile network robust and vice versa",
Physical Review Letters
**102**(2009): 018701, arxiv:0812.3591 - Stefano Mossa, Marc Barthelemy, H. Eugene Stanley, and Luis A. Nunes Amaral, "Truncation of power law behavior in `scale-free' network models due to information filtering," cond-mat/0201421
- Adilson E. Motter, "Cascade control in complex networks", cond-mat/0401074
- Adilson E. Motter, Alessandro P. S. de Moura, Ying-Cheng Lai, and
Partha Dasgupta, "Topology of the conceptual network of language,"
cond-mat/0206530 =
Physical Review E
**65**(2002): 065102(R) - J. C. Nacher, T. Yamada, S. Goto, M. Kanehisa and T. Akutsu, "Two complementary representations of a scale-free network", physics/0402072
- M. E. J. Newman, I. Jensen and R. M. Ziff, "Percolation and epidemics in a two-dimensional small world," cond-mat/0108542
- Emi M. Nomura, Caterina Gratton, Renee M. Visser, Andrew
Kayser, Fernando Perez and Mark D'Esposito, "Double dissociation of two cognitive control networks in patients with focal brain lesions", Proceedings of the National Academy of Sciences (USA)
**107**(2010): 121017--12022 [Supposedly involved "graph-theory properties"] - Jukka-Pekka Onnela, Jari Saramaki, Janos Kertesz, and Kimmo Kaski,
"Intensity and coherence of motifs in weighted complex networks",
Physical Review
E
**71**(2005): 065103(R) - R. N. Onody and P. A. de Castro, "Nonlinear Barabási-Albert Network", cond-mat/0402315
- Pekka Orponen and Satu Elisa Schaeffer, "Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks", cond-mat/0406048
- Juyong Park and M. E. J. Newman, "The origin of degree correlations in the Internet and other networks," cond-mat/0303327
- Victor M. Preciado, Michael Zargham, Chinwendu Enyioha, Ali Jadbabaie, George Pappas, "Optimal Vaccine Allocation to Control Epidemic Outbreaks in Arbitrary Networks", arxiv:1303.3984
- Derek J. de Solla Price
- "Networks of scientific papers", Science
**149**(1965): 510--515 - "A general theory of bibliometric and other cumulative
advantage processes", J. Amer. Soc. Inform. Sci.
**27**(1976): 292--306 [= Journal of the American Society of Information Science?]

- "Networks of scientific papers", Science
- Natasa Przulj, Derek G. Corneil and Igor Jurisica, "Modeling Interactome: Scale-free or Geometric", q-bio.MN/0404017
- Amit Puniyani and Rajan Lukose, "Growing random networks under constraints," cond-mat/0107391
- Filippo Radicchi, Alain Barrat, Santo Fortunato, Jose J. Ramasco, "Renormalization flows in complex networks", Physical Review E
**79**(2009): 026104, arxiv:0811.2761 - Abolfazl Ramzanpour and V. Karimipour, "Simple models of small world networks with directed links," cond-mat/0205244
- Erzsebet Ravasz and Albert-László Barabási, "Hierarchical
organization in complex networks,"
cond-mat/0206130 =
Physical Review E
**67**(2003): 026112 - Hermann Riecke, Alex Roxin, Santiago Madruga and Sara A. Solla,
"Multiple attractors, long chaotic transients, and failure in small-world
networks of excitable
neurons", Chaos
**17**(2007): 026110 - Olivier Rivoire and Julien Barré "Exactly solvable models of adaptive networks", cond-mat/0606754 ["A satisfiability (SAT-UNSAT) transition takes place for many optimization problems when the number of constraints, graphically represented by links between variables nodes, is brought above some threshold. If the network of constraints is allowed to adapt by redistributing its links, the SAT-UNSAT transition may be delayed and preceded by an intermediate phase where the structure self-organizes to satisfy the constraints." Which means what, for the original logic problem? I should read the paper to see...]
- Hernan Rozenfeld and Daniel ben-Avraham, "Designer Nets from Local Strategies", cond-mat/0401196
- Hernan D. Rozenfeld, Joseph E. Kirk, Erik M. Bollt and Daniel ben-Avraham, "Statistics of Cycles: How Loopy is your Network?", cond-mat/0403536
- Manoj Pratim Samanta and Shoudan Liang, "Redundancies in Large-scale Protein Interaction Networks," physics/0303027
- Alejandro D. Sanchez, Juan M. Lopez and Miguel A. Rodriguez, "Nonequilibrium Phase Transitions in Directed Small-World Networks," cond-mat/0110500
- Leonard M. Sander, C. P. Warren and I. M. Sokolov, "Epidemics disorder, and percolation," cond-mat/0301394
- Nima Sarshar and Vwani Roychowdhury, "Scale-Free and Stable
Structures in Complex
*Ad hoc*Networks," cond-mat/0303041 - N. Schwartz, R. Cohen, D. ben-Avraham, A.-L. Barabási and S. Havlin, "Percolation in Directed Scale-Free Networks," cond-mat/0204523
- Philip Seliger, Stephen C. Young, and Lev S. Tsimring, "Plasticity and learning in a network of coupled phase oscillators," nlin.AO/0110044
- M. Angeles Serrano and Marian Boguna
- "Topology of the World Trade Web," cond-mat/0301015
- "Clustering in complex networks. I. General formalism", cond-mat/0608336
- "Clustering in complex networks. II. Percolation properties", cond-mat/0608337

- M. Angeles Serrano, Dmitri Krioukov and Marian Boguna,
"Self-Similarity of Complex Networks and Hidden Metric
Spaces", Physical Review
Letters
**100**(2008): 078701 - Dinghua Shi, Qinguha Chen and Liming Liu, "A Markov Chain-Based Numerical Method for Calculating Network Degree Distributions", math-ph/0409080
- Julian Sienkiewicz, Piotr Fronczak, and Janusz A. Holyst, "Log-periodic oscillations due to discrete effects in complex networks", cond-mat/0608273
- Tiago Simas, Luis M. Rocha, "Stochastic model for scale-free networks with cutoffs", arxiv:0901.0159
- Ingve Simonsen, Kasper Astrup Eriksen, Sergei Maslov and Kim
Sneppen, "Diffusion on Complex Networks : A way to probe their large scale
topological structures",
cond-mat/0312476
= Physica A
**336**(2004): 163--173 - Sitabhra Sinha and Sudeshna Sinha, "Evidence of universality for the May-Wigner stability theorem for random networks with local dynamics", nlin.AO/0402002
- Arne Skjeltorp and Alexander Belushkin (eds.), Dynamics of Complex Interconnected Systems: Networks and Bioprocesses
- David M. D. Smith, Chiu Fan Lee and Neil F. Johnson, "Realistic network growth using only local information: From random to scale-free and beyond", cond-mat/0608733
- Sara Nadiv Soffer and Alexei Vazquez, "Network clustering
coefficient without degree-correlation biases", Physical Review
E
**71**(2005): 057101 ["The clustering coefficient quantifies how well connected are the neighbors of a vertex in a graph. In real networks it decreases with the vertex degree, which has been taken as a signature of the network hierarchical structure. Here we show that this signature of hierarchical structure is a consequence of degree-correlation biases in the clustering coefficient definition. We introduce a definition in which the degree-correlation biases are filtered out, and provide evidence that in real networks the clustering coefficient is constant or decays logarithmically with vertex degree."] - Olaf Sporns, Networks of the Brain
- Russell K. Standish, "Complexity of Networks (reprise)", arxiv:0911.3482
- Dietrich Stauffer and Amnon Aharony, "Efficient Hopfield pattern recognition on a scale-free neural network," cond-mat/0212601
- Hrvoje Stefancic and Vinko Zlatic, "Preferential attachment with information filtering: node degree probability distribution properties", cond-mat/0404495
- Gyorgy Szabo and Gabor Fath, "Evolutionary games on graphs", cond-mat/0607344
- Gergely J Szollosi, Imre Derenyi, "Hierarchical meanfield theory of evolutionary games on structured populations", arxiv:0704.0357
- Kazuhiro Takemoto and Chikoo Oosawa, "Evolving networks by
merging cliques", Physical Review E
**72**(2005): 046116 - Makoto Uchida and Susumu Shirayama, "Effect of initial conditions on Glauber dynamics in complex networks", cond-mat/0702482
- S. Valverde, R. Ferrer i Cancho and R. V. Sole, "Scale-free Networks from Optimal Design," cond-mat/0204344
- J. van den Berg, Geoffrey R. Grimmett and Rinaldo B. Schinazi,
"Dependent Random Graphs and Spatial Epidemics", Annals of Applied
Probability
**8**(1998): 317--336 - Alexei Vazquez, "Statistics of citation networks", cond-mat/0105031
- Alexei Vazquez and Albert-László Barabási, "The inhomogeneous evolution of subgraphs and cycles in complex networks", cond-mat/0501399
- Alexei Vazquez and Martin Weigt, "Computational complexity arising from degree correlations in networks," cond-mat/0207035
- R. Vilela Mendes, "Network Dependence of Strong Reciprocity",
Advances in Complex
Systems
**7**(2004): 357--368 - Andreas Wagner, "How the global structure of protein interaction networks evolves," cond-mat/0207043
- C. P. Warren, Leonard M. Sander and I. M. Sokolov, "Geography in a Scale-Free Network Model," cond-mat/0207324
- Duncan J. Watts, Peter S. Dodds and Mark E. J. Newman, "Identity
and Search in Social Networks,"
Science
**296**(2002): 1302--1305, cond-mat/0205383 - Martin Weigt, "Dynamics of heuristic optimization algorithms on random graphs," cond-mat/0203281
- Chris Wiggins and Ilya Nemenman, "Process Pathway Inference via Time Series Analysis," physics/0206031
- Walter Willinger et al., "Scaling Phenomena in the Internet:
Critically Examining Criticality", Proceedings of the National
Academy of Sciences
**99**(2002): 2673--2580 - An-Cai Wu, Xin-Jian Xu, and Ying-Hai Wang, "Excitable
Greenberg-Hastings cellular automaton model on scale-free
networks", Physical Review
E
**75**(2007): 032901 - Ramon Xulvi-Brunet and I. M. Sokolov, "Evolving networks with disadvantaged long-range connections," cond-mat/0205136
- Jie Zhang, Changsong Zhou, Xiaoke Xu and Michael Small, "Mapping from Architeture to Dynamics: A Unified View of Dynamical Processes on Networks", arxiv:0908.2248 [From a quick scan, vastly less general and ambitious than the title or even the abstract promises; but worth looking at more closely.]
- Chaopin Zhu, Anthony Kuh, Juan Wang and Philippe De Wilde,
"Analysis of an evolving email
network", Physical
Review E
**74**(2006): 046109 - Etay Ziv, Manuel Middendorf and Chris Wiggins,
"Information-Theoretic Approach to Network Modularity", q-bio.QM/0411033 = PRE
**71**(2005): 046117 - Alexander Zumdieck, Marc Timme, Theo Geisel and Fred Wolf, "Long Chaotic Transients in Complex Networks", cond-mat/0401038