Skip to main content
SpringerLink
Log in

Complex Networks: from Graph Theory to Biology

  • Published:
Letters in Mathematical Physics Aims and scope Submit manuscript

Abstract

The aim of this text is to show the central role played by networks in complex system science. A remarkable feature of network studies is to lie at the crossroads of different disciplines, from mathematics (graph theory, combinatorics, probability theory) to physics (statistical physics of networks) to computer science (network generating algorithms, combinatorial optimization) to biological issues (regulatory networks). New paradigms recently appeared, like that of ‘scale-free networks’ providing an alternative to the random graph model introduced long ago by Erdös and Renyi. With the notion of statistical ensemble and methods originally introduced for percolation networks, statistical physics is of high relevance to get a deep account of topological and statistical properties of a network. Then their consequences on the dynamics taking place in the network should be investigated. Impact of network theory is huge in all natural sciences, especially in biology with gene networks, metabolic networks, neural networks or food webs. I illustrate this brief overview with a recent work on the influence of network topology on the dynamics of coupled excitable units, and the insights it provides about network emerging features, robustness of network behaviors, and the notion of static or dynamic motif.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Albert R., Barabasi A.L. (2001) Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97

    Article  MathSciNet  ADS  Google Scholar 

  2. Aldana M. (2003) Dynamics of Boolean networks with scale free topology. Physica D 185, 45–66

    Article  MATH  MathSciNet  ADS  Google Scholar 

  3. Aldana M., Coppersmith S., Kadanoff L.P. (2003) Boolean dynamics with random couplings. In: Kaplan E., Marsden J.E., Sreenivasan K.R. (eds) Perspectives and Problems in Nonlinear Science. A celebratory volume in honor of Lawrence Sirovich. Springer, Berlin Heidelberg New york

    Google Scholar 

  4. Barabasi A.L., Albert R. (1999) Emergence of scaling in random networks. Science 286, 509–512

    Article  MathSciNet  Google Scholar 

  5. Berg J., Lassig M. (2004) Local graph alignment and motif search in biological networks. Proc. Natl. Acad. Sci. USA 101, 14689–14694

    Article  ADS  Google Scholar 

  6. Bollobas B. (2001) Random Graphs. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  7. Carvunis, A.R., Latapy, M., Lesne, A., Magnien, C., Pezard, L.: Dynamics of three-state excitable units on random vs power-law networks. Physica A (2005 in press). Available at http://www.liafa.jussieu.fr/~latapy/index.php?item=publis&lang=fr

  8. Ciliberti S., Caldarelli G., De Los Rios P., Pietronero L., Zhang Y.C. (2000) Discretized diffusion processes. Phys. Rev. Lett. 85, 4848–4851

    Article  ADS  Google Scholar 

  9. Dorogovtsev S.N., Mendes J.F.F. (2003) Evolution of Networks: from Biological Nets to the Internet and WWW. Oxford University Press, Oxford

    Google Scholar 

  10. Erdös P., Rényi A. (1960) On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61

    MATH  Google Scholar 

  11. Ermentrout G.B., Edelstein-Keshet L. (1993) Cellular automata approaches to biological modelling. J. Theor. Biol. 160, 97–133

    Article  Google Scholar 

  12. Faloutsos M., Faloutsos P., Faloutsos C. (1999) On power-law relationships of the Internet topology. Comput. Commun. Rev. 29, 251–262

    Article  Google Scholar 

  13. Farkas I., Derényi I., Jeong H., Neda Z., Oltvai Z.N., Ravasz E., Schrubert A., Barabasi A.L. (2002) Networks in life: scaling properties and eigenvalues spectra. Physica A 314: 25–34

    Article  MATH  MathSciNet  ADS  Google Scholar 

  14. Fox Keller E. (2005) Revisiting “scale-free” networks. BioEssays 27, 1060–1068

    Article  Google Scholar 

  15. García-Pelayo R., Stadler P.F. (1997) Correlation length, isotropy and meta-stable states. Physica D 107, 240–254

    Article  ADS  Google Scholar 

  16. Gaveau B., Lesne A., Schulman L.S. (1999) Spectral signatures of hierarchical relaxation. Phys Lett A 258: 222–228

    Article  MATH  MathSciNet  ADS  Google Scholar 

  17. Gaveau B., Schulman L.S. (2005) Dynamical distance: coarse grains, pattern recognition and network analysis. Bull. Sci. Math. 129, 631–642

    Article  MATH  MathSciNet  Google Scholar 

  18. Guelzim N., Bottani S., Bourgine P., Képès F. (2002) Topological and causal structure of the yeast transcriptional regulatory network. Nat. Genet. 31, 60–63

    Article  Google Scholar 

  19. Guhr T., Müller-Groeling A., Weidenmüller H.A. (1998) Random-matrix theories in quantum physics: common concepts. Phys. Rep. 299, 189–425

    Article  MathSciNet  ADS  Google Scholar 

  20. Hopfield J.J. (1982) Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. USA 79, 2554–2558

    Article  MathSciNet  ADS  Google Scholar 

  21. Imbert, J.B., Lesne, A.: Improved ergodicity in constrained Monte Carlo sampling (2006, in preparation)

  22. Jeong H., Tombor B., Albert R., Oltvai Z.N., Barabasi A.L. (2000) The large-scale organization of metabolic networks. Nature 407, 651–654

    Article  ADS  Google Scholar 

  23. Kauffman S.A. (1993) The Origins of Order: Self-organization and Selection in Evolution. Oxford University Press, Oxford

    Google Scholar 

  24. Lesne A. (1998) Renormalization Methods. Wiley, New York

    MATH  Google Scholar 

  25. Lesne, A.: Disordered random graph models: scale-free out with a typical in-degree (2006, submitted)

  26. Lesne, A.: Scale-invariant behavior of scale-free graphs (2006, submitted)

  27. Lieberman E., Hauert C., Nowak M.A. (2005) Evolutionary dynamics on graphs. Nature 433, 312–316

    Article  ADS  Google Scholar 

  28. Marr C., Hütt M.T. (2005) Topology regulates pattern formation capacity of binary cellular automata on graphs. Physica A 354, 641–662

    Article  ADS  Google Scholar 

  29. Mazurie A., Bottani S., Vergassola M. (2005) An evolutionary and functional assessment of regulatory network motifs. Genome Biol. 6, R35

    Article  Google Scholar 

  30. Newman M.E.J. (2003) The structure and function of complex networks. SIAM Rev. 45, 167–256

    Article  MATH  MathSciNet  Google Scholar 

  31. Papin J.A., Reed J.L., Palsson B. (2004) Hierarchical thinking in network biology: the unbiased modularization of biochemical networks. Trends Biochem Sci. 29, 641–647

    Article  Google Scholar 

  32. Pastor-Satorras R., Vespignani A. (2004) Evolution and Structure of the Internet. Cambridge University Press, Cambridge

    Google Scholar 

  33. Pimm S.L. (1982) Food Webs. Chapman & Hall, London

    Google Scholar 

  34. Schnakenberg J. (1976) Network theory of microscopic and macroscopic behavior of solutions of master equations. Rev. Mod. Phys. 48, 571–585

    Article  MathSciNet  ADS  Google Scholar 

  35. Shen-Orr S., Milo R., Mangan S., Alon U. (2002) Network motifs in the transcriptional regulation network of Escherichia coli. Nat. Genet. 31, 64–68

    Article  Google Scholar 

  36. Shmulevich I., Kauffman S.A., Aldana M. (2005) Eukaryotic cells are dynamically ordered or critical but not chaotic. Proc. Natl. Acad. Sci. USA 102, 13439–13444

    Article  ADS  Google Scholar 

  37. Simon H.A. (1955) On a class of skew distribution functions. Biometrika 42, 425–440

    Article  MATH  MathSciNet  Google Scholar 

  38. Simonsen I (2005) Diffusion and networks: a powerful combination!. Physica A 357: 317–330

    Article  MathSciNet  ADS  Google Scholar 

  39. Sornette D. (2000) Critical Phenomena in Natural Sciences. Springer, Berlin heidelberg Newyork New York

    MATH  Google Scholar 

  40. Stadler P.F. (1996) Landscapes and their correlation functions. J. Math. Chem. 20, 1–45

    Article  MATH  MathSciNet  Google Scholar 

  41. Strogatz S.H. (2001) Exploring complex networks. Nature 410, 268–276

    Article  ADS  Google Scholar 

  42. Watts D.J., Strogatz S.H. (1998) Collective dynamics of “small-world” networks.[ Nature 393, 440–442

    Article  ADS  Google Scholar 

  43. Weinberger E.D. (1990) Correlated and uncorrelated fitness landscapes and how to tell the difference. Biol. Cybern. 63, 325–336

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université Pierre et Marie Curie-Paris 6, UMR 7600, Paris, 75005, France

    Annick Lesne

  2. Institut des Hautes Études Scientifiques, Le Bois-Marie, 35 route de Chartres, 91440, Bures-sur-Yvette, France

    Annick Lesne

Authors
  1. Annick Lesne
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Annick Lesne.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lesne, A. Complex Networks: from Graph Theory to Biology. Lett Math Phys 78, 235–262 (2006). https://doi.org/10.1007/s11005-006-0123-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11005-006-0123-1

Mathematics Subject Classification (2000)

Keywords

Search

Navigation