The Architecture of Complexity in Cellular Networks

1. The Architecture of Complexity: Structure and Modularity in Cellular Networks The Architecture of Complexity: Structure and Modularity in Cellular Networks Albert-Lszl Barabsi Albert-Lszl Barabsi University of Notre Dame University of Notre Dame www.nd.edu/~networks title title

2. Erds-Rnyi model (1960) - Democratic - Random Pl Erds Pl Erds (1913-1996) Connect with probability p p=1/6 N=10 k ~ 1.5 Poisson distribution

3. World Wide Web Over 3 billion documents ROBOT: collects all URLs found in a document and follows them recursively Nodes : WWW documents Links : URL links R. Albert, H. Jeong, A-L Barabasi, Nature , 401 130 (1999). WWW Expected P( k ) ~ k - Found Scale-free Network Exponential Network

4. Internet-Map

5. protein-gene interactions protein-protein interactions PROTEOME GENOME Citrate Cycle METABOLISM Bio-chemical reactions Bio-Map

6. Citrate Cycle METABOLISM Bio-chemical reactions

7. Boehring-Mennheim

8. Metabolic Network Nodes : chemicals (substrates) Links : bio-chemical reactions Metab-movie

9. Metabolic network Organisms from all three domains of life are scale-free networks! H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, and A.L. Barabasi, Nature , 407 651 (2000) Archaea Bacteria Eukaryotes Meta-P(k)

10. protein-gene interactions protein-protein interactions PROTEOME GENOME Citrate Cycle METABOLISM Bio-chemical reactions Bio-Map

11. protein-protein interactions PROTEOME

12. Topology of the protein network H. Jeong, S.P. Mason, A.-L. Barabasi, Z.N. Oltvai, Nature 411, 41-42 (2001) Prot P(k) Nodes : proteins Links : physical interactions (binding)

13. Scale-free model Barabsi & Albert, Science 286, 509 (1999) P(k) ~k -3 BA model (1) Networks continuously expand by the addition of new nodes WWW : addition of new documents GROWTH: add a new node with m links PREFERENTIAL ATTACHMENT: the probability that a node connects to a node with k links is proportional to k. (2) New nodes prefer to link to highly connected nodes. WWW : linking to well known sites

14. Can Latecomers Make It? Fitness Model SF model : k(t)~t (f irst mover advantage) Real systems : nodes compete for links -- fitness Fitness Model : fitness ( k( ,t)~t where = C G. Bianconi and A.-L. Barabsi, Europhyics Letters. 54 , 436 (2001).

15. Bose-Einstein Condensation in Evolving Networks G. Bianconi and A.-L. Barabsi, Physical Review Letters 2001; cond-mat/0011029 Network Bose gas Fit-gets-rich Bose-Einstein condensation

16. Robustness Complex systems maintain their basic functions even under errors and failures (cell mutations; Internet router breakdowns) node failure f c 0 1 Fraction of removed nodes, f 1 S Robustness

17. Robustness of scale-free networks 1 S 0 1 f f c Attacks 3 : f c =1 (R. Cohen et al PRL, 2000) Failures Robust-SF Albert, Jeong, Barabasi, Nature 406 378 (2000)

18. Real networks are fragmented into group or modules Society: Granovetter, M. S. (1973) ; Girvan, M., & Newman, M.E.J. (2001); Watts, D. J., Dodds, P. S., & Newman, M. E. J. (2002). WWW: Flake, G. W., Lawrence, S., & Giles. C. L. (2000). Biology: Hartwell, L.-H., Hopfield, J. J., Leibler, S., & Murray, A. W. (1999). Internet: Vasquez, Pastor-Satorras, Vespignani(2001). Modularity Traditional view of modularity: Ravasz, Somera, Mongru, Oltvai, A-L. B, Science 297, 1551 (2002).

19. Modular vs. Scale-free Topology Scale-free (a) Modular (b)

20. Hierarchical Networks T number of links between the neighbors k number of neighbors (connectivity) Clustering coefficient the measure of a vertex neighborhood interconnectivity.

21. Real Networks Hollywood Language Internet (AS) Vaquez et al,'01 WWW Eckmann & Moses, 02

22. Hierarchy in biological systems Metabolic networks Protein networks

23. Population density Router density Spatial Distributions Yook, Jeong and A.-L.B, PNAS 2002

24. Spatial Distribution of Routers Fractal set Box counting: N ( ) No. of boxes of size that contain routers N ( ) ~ -D f D f =1.5

25. Preferential Attachment Compare maps taken at different times ( t = 6 months) Measure k ( k ), increase in No. of links for a node with k links Preferential Attachment: k ( k ) ~ k

26. Modeling the effect of spatial distribution Model place nodes on a two dimensional space, forming a fractal D f Preferential attachment: Question: Could the distance dependence kill the power law? Numerical results: when <2 then P(k) is power law when >2 then P(k) is exponential For the Internet: =1 (!) thus the Internet could be scale-free.

27. Phase Diagram N ( ) ~ -D f D f =1.5 k ( k ) ~ k =1 P ( d ) ~ d - =1

28. Subgraphs Subgraph : a connected graph consisting of a subset of the nodes and links of a network Subgraph properties : n : number of nodes m : number of links (n=3,m=3) (n=3,m=2) (n=4,m=4) (n=4,m=5) .

29. Intracellular molecular interaction sub-networks Protein-protein interaction network N =5068 E =15117 Transcriptional- regulatory network N =688 E =1078 Metabolic network N =551 E =1698

30. Subgraph density in biological networks (n,m) Transcription Metabolic Protein E. coli S. cerevisiae E. coli S. cerevisiae S. cerevisiae (3,2) 12 19 101 72 70 (3,3) 0.30 0.31 5.0 5.8 4.1 (4,3) 169 220 4412 2041 2395 (4,6) 0.00 0.00 0.44 0.77 0.97 (5,4) 2492 2587 2.1x10 5 5.9x10 4 1.2x10 5 (5,10) 0.00 0.00 0.055 0.20 0.66 (6,5) 3.2x10 4 2.8x10 4 8.8x10 6 1.5x10 6 5.7x10 6 (6,15) 0.00 0.00 0.00 0.03 0.36 (7,6) 3.4x10 5 2.7x10 5 3.5x10 8 3.7x10 7 2.4x10 8 (7,21) 0.00 0.00 0.00 0.00 0.00 # of subgraphs/# of nodes

31. Motifs R. Milo et al., Science 298 , 824 (2002) Motifs: Subgraphs that have a significantly higher density in the real network than in the randomized version of the studied network Randomized networks: Ensemble of maximally random networks preserving the degree distribution of the original network

32. R Milo et al., Science 298 , 824-827 (2002).

33. R. Milo et al., Science 298 , 824 (2002) Hypothesis: desirable dynamical and signal processing features. Evolutionary selection of dynamically desirable building blocks. Feed-Forward (FF) Motif is a noise filter. Why do we have motifs?

34. Do motifs have biological relevance? -high degree of evolutionary conservation of the motifs within the protein interaction network (Wuchty et al., Nat. Genet. 2003) -convergent evolution in the transcriptional network of diverse species toward the same motif types (Canant and Wagner, Nat. Genet. 2003)

35. What determines the number of subgraphs in biological networks? (n,m) Transcription Metabolic Protein E. coli S. cerevisiae E. coli S. cerevisiae S. cerevisiae (3,2) 12 19 101 72 70 (3,3) 0.30 0.31 5.0 5.8 4.1 (4,3) 169 220 4412 2041 2395 (4,6) 0.00 0.00 0.44 0.77 0.97 (5,4) 2492 2587 2.1x10 5 5.9x10 4 1.2x10 5 (5,10) 0.00 0.00 0.055 0.20 0.66 (6,5) 3.2x10 4 2.8x10 4 8.8x10 6 1.5x10 6 5.7x10 6 (6,15) 0.00 0.00 0.00 0.03 0.36 (7,6) 3.4x10 5 2.7x10 5 3.5x10 8 3.7x10 7 2.4x10 8 (7,21) 0.00 0.00 0.00 0.00 0.00

36. Global network properties A.-L. B. and Z.N. Oltvai, Nat. Rev. Gen.(2004)

37. Average number of subgraphs passing by a node with degree k Average number of (n,m) subgraphs in the network Number of subgraphs with n nodes Probability of having m -( n -1) extra links Calculating the number of subgraphs: I

38. P ( k )~ k - , C ( k )~ k - , n << k max Type II subgraphs: Type I subgraphs: Calculating the number of subgraphs: II ~N

39. Phase boundary: Type I: Type II:

40. How do the subgraphs relate to each other? S. Cerevisiae transcription-regulatory network Subgraphs do not exist in isolation: aggregate into subgraph clusters.

41. From global to local T(k) number of direct links between the nodes k neighbors OR T(k) the number of triangles a node with k links participates in k=5 T(k) =2 (in the limit of large k ) P ( T ) probability that T triangles pass by a node

42. Validation

43. Generalization to arbitrary subgraphs n=3 t=1 m : number of links n : number of nodes t =m-n+1

44. Motif clusters: S. cerevisiae

45. Motif clusters The probability that a link connected to a node of degree k participates in a triangle is given by q(k) = 1 - [1 - C(k)] k-1 , which is the probability that the neighbor at the other end of the link is connected to at least one of the k - 1 remaining neighbors. If C(k) = C 0 k -1 , for large k we obtain q ~ 1 - exp(- C 0 ), independent of the node degree. calculating the size of the largest triangle cluster is equivalent with determining the largest cluster of connected nodes, after each link is removed with probability 1-q .

46. The emergence of subgraph clusters Lower bound percolation boundary: Phase boundary (Type I and II):

47. S 6, m Fraction of nodes in the largest cluster of (6, m ) subgraphs

48. Conclusions A sharp distinction between the local and global structure is not justified (they are equivalent ): From only two parameters, characterizing the networks global topology, we are able to derive the precise subgraph densities seen in biological networks Measuring the distribution of two motifs allows us to determine the exponents characterizing the networks large scale features. Subgraphs do not exist in isolation must aggregate into subgraphs clusters

49. http://www.nd.edu/~networks Zoltn N. Oltvai, Northwestern Med. School Zoltn N. Oltvai, Northwestern Med. School Hawoong Jeong, KAIST, Corea Hawoong Jeong, KAIST, Corea Rka Albert, Penn State Rka Albert, Penn State Erzsbet Ravasz, Notre Dame Erzsbet Ravasz, Notre Dame S.H. Yook, Notre Dame S.H. Yook, Notre Dame Eivind Almaas, Notre Dame Eivind Almaas, Notre Dame Baldvin Kovcs, Eotvos Univ. Budapest Baldvin Kovcs, Eotvos Univ. Budapest Tams Vicsek, Eotvos Univ. Budapest Tams Vicsek, Eotvos Univ. Budapest A. Vzquez, Notre Dame A. Vzquez, Notre Dame R. Dobrin, Northwestern R. Dobrin, Northwestern D. Sergi, U. de Genve D. Sergi, U. de Genve J.-P. Eckmann, U. de Genve J.-P. Eckmann, U. de Genve Stefan Wuchty, Notre Dame Stefan Wuchty, Notre Dame