Complex Networks

22 Feb 2008 18:21

---

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.

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

Recommended:
• Reka Albert and Albert-Laszlo Barabasi, "Statistical Mechanics of Complex Networks," cond-mat/0106096
• 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. Barabasi, "Fluctuations in network dynamics", cond-mat/0306304 = Physical Review Letters 92 (2004): 028701
• Aaron Clauset and Cristopher Moore, "How Do Networks Become Navigable?", cond-mat/0309415
• Vamsi Kalapala, Vishal Sanwalani, Aaron Clauset, and Cristopher Moore, "Scale Invariance in Road Networks", physics/0510198 = Physical Review E 73 (2006): 026130
• 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.]
• 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 entowrks 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
  • "Ego-centered networks and the ripple effect," cond-mat/0111070
  • "Random graphs as models of networks," cond-mat/0202208
  • "The structure and function of complex networks," cond-mat/0303516
• M. E. J. Newman, Steven H. Strogatz and Duncan J. Watts, "Random graphs with arbitrary degree distributions and their applications", Physical Review E 64 (2001): 026118 = cond-mat/0007235
• 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
• 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
• Duncan Watts, Small Worlds

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. Barabasi, "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
• M. Argollo de Menezes and A.-L. Barabasi, "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
• 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
• Yaneer Bar-Yam and Irving R. Epstein, "Response of complex networks to stimuli", Proceedings of the National Academy of Sciences 10.1073/pnas.0400673101
• Vladimir Batagelj and Ulrik Brandes, "Efficient generation of large random networks", Physical Review E 71 (2005): 036113
• 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
• Philippe Blanchard and T. Krueger, "The `Cameo Principle' and the Origin of Scale-Free Graphs in Social Networks," cond-mat/0302611
• Vincent Blondel, Anahi Gajardo, Maureen Heymans, Pierre Senellart, Paul Van Dooren, "A measure of similarity between graph vertices", cs.IR/0407061
• 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
• Markus Brede and Sitabhra Sinha, "Assortative mixing by degree makes a network more unstable", cond-mat/0507710
• 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 [author's book site]
• 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
• Michele Catanzaro, Marian Boguna and Romualdo Pastor-Satorras, "Generation of uncorrelated random scale-free networks", cond-mat/0408110
• Fan Chung and Linyuan Lu, Complex Graphs and Networks [Blurb]
• 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 ["The theme of this paper is the derivation of analytical formulae for certain large combinatorial structures. The formulae are obtained via fluid limits of pure jump-type Markov processes..."]
• M.A.M. de Aguiar and Y. Bar-Yam, "Spectral Analysis and the Dynamic Response of Complex Networks", nlin.AO/0306043
• 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 [Oxford U.P., 2003. Apparently the first serious monograph on the subject. Book's website.]
• 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
• Rick Durrett, Random Graph Dynamics [Durrett's site for the book, including the full text of the introductory chapter.]
• 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
• Andreas Engel, Remi Monasson and Alexander K. Hartmann, "On Large Deviation Properties of Erdos-Renyi Random Graphs", Journal of Statistical Physics 117 (2004): 387--426
• 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-Laszlo Barabasi 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-Laszlo Barabasi 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
• Santo Fortunato, Alessandro Flammini, Filippo Menczer, "Scale-free network growth by ranking", cond-mat/0602081
• O. Frank and D. Strauss, "Markov graphs", Journal of the American Statistical Association 81 (1986): 832--842
• 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
• A. V. Goltsev, S. N. Dorogovtsev and J. F. F. Mendes, "Critical Phenomena in Networks," cond-mat/0204596
• 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
• 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
• Matthew Haag and Roger Lagunoff, "Social Norms, Local Interaction, and Neighborhood Planning," ewp-game/9907004
• Aric Hagberg, Pieter J. Swart and Daniel A. Schult, "Designing threshold networks with given structural and dynamical properties", Physical Review E 74 (2006): 056116
• 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
• 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
• Eben Kenah and James Robins, "Second look at the spread of epidemics on networks", q-bio.QM/0610057
• 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 ["We consider methods for quantifying the similarity of vertices in networks. We propose a measure of similarity based on the concept that two vertices are similar if their immediate neighbors in the network are themselves similar. This leads to a self-consistent matrix formulation of similarity that can be evaluated iteratively using only a knowledge of the adjacency matrix of the network. We test our similarity measure on computer-generated networks for which the expected results are known, and on a number of real-world networks."]
• 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
• 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
• 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
• Mark E. J. Newman
  • "Clustering and Preferential Attachment in Growing Networks," cond-mat/0104029
  • "Exact solutions of epidemic models on networks," cond-mat/0201433
  • "Properties of highly clustered networks," cond-mat/0303183
  • "The spread of epidemic disease on networks," cond-mat/0205009
• M. E. J. Newman, I. Jensen and R. M. Ziff, "Percolation and epidemics in a two-dimensional small world," cond-mat/0108542
• 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 Barabasi-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
• 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
• 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?]
• Natasa Przulj, Derek G. Corneil and Igor Jurisica, "Modeling Interactome: Scale-free or Geometric", q-bio.MN/0404017
• Anatolii A. Puhalskii, "Stochastic processes in random graphs", math.PR/0402183 [Large deviations for Erdos-Renyi graphs. Memo to self: how much work would it be to extend this to Markovian graphs?]
• Amit Puniyani and Rajan Lukose, "Growing random networks under constraints," cond-mat/0107391
• Abolfazl Ramzanpour and V. Karimipour, "Simple models of small world networks with directed links," cond-mat/0205244
• A. Rapoport
  • "Contribution to the theory of random and biased nets", Bulletin of Mathematical Biophysics 19 (1957): 257--277
  • "Cycle distribution in random nets", Bulletin of Mathematical Biophysics 10 (1968): 145--157
• Erzsebet Ravasz and Albert-Laszlo Barabasi, "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. Barabasi 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
• 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
• Bo Söderberg, "A General Formalism for Inhomogeneous Random Graphs", cond-mat/0211063 [Marked as "to appear" in PRE, look up reference later]
• 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."]
• R. Solomonoff and A. Rapoport, "Connectivity of Random Nets", Bulletin of Mathematical Biophysics 13 (1951): 107--117 [Yes, the R. Solomonoff]
• 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
• 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 [JSTOR]
• Alexei Vazquez, "Statistics of citation networks," cond-mat/0105031
• Alexei Vazquez and Albert-Laszlo Barabasi, "The inhomogeneous evolution of subgraphs and cycles in complex networks", cond-mat/0501399
• Alexei Vazquez, A. Flammini, A. Maritan, and A. Vespignani, "Modeling of protein interaction networks," cond-mat/0108043
• 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
• Dmitri Volchenkov and Ph. Blanchard, "An Algorithm Generating Scale Free Graphs," cond-mat/0204126
• 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, "The 'New' Science of Networks", Annual Review of Sociology 30 (2004): 243--270
• Duncan J. Watts, Peter S. Dodds and Mark E. J. Newman, "Identity and Search in Social Networks," cond-mat/0205383 = Science 296 (2002): 1302--1305
• Martin Weigt, "Dynamics of heuristic optimization algorithms on random graphs," cond-mat/0203281
• Harrison White, Markets from Networks: Socioeconomic Models of Production
• 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
• Damian H. Zanette, "Dynamics of rumor propagation on small-world networks," cond-mat/0110324
• W.-X. Zhou, D. Sornette, R. A. Hill and R. I. M. Dunbar, "Discrete Hierarchical Organization of Social Group Sizes", cond-mat/0403299
• 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