CS 297: Complex Systems

Papers

• Group A1: Cellular Automata
  1. J.Avnet. Computation, Dynamics and the Phase Transition Santa Fe Institute.
  2. M.Mitchell, J.P.Crutchfield, and P.T.Hraber. Dynamics, computation, and the ``edge of chaos'': A re-examination. In G. Cowan, D. Pines, and D. Melzner (editors), Complexity: Metaphors, Models, and Reality. Reading, MA: Addison-Wesley, 1994.
• Group A2: Cellular Automata
  1. J.P.Crutchfield and M.Mitchell. The evolution of emergent computation. PNAS, 92 (23): 10742, 1995.
  2. M.Mitchell, J.P.Crutchfield and R.Das. Evolving cellular automata to perform computations. In T. Back, D. Fogel, and Z. Michalewicz (editors), Handbook of Evolutionary Computation. Oxford: Oxford University Press, 1998.
• Group B1: Highly-Optimized Tolerance (HOT)
  1. J.M.Carlson and J.Doyle. Highly optimized tolerance: a mechanism for power laws in designed systems. Phys. Rev. E 60, 1412-1427.
  2. J.M.Carlson and J.Doyle. Complexity and robustness. Proc. Nat. Acad. Sci. 99 , 2538-2545.
• Group B2: Highly-Optimized Tolerance (HOT)
  1. D.Reynolds, J.Carlson and J.Doyle. Design degrees of freedom and mechanisms for complexity Phys. Rev. E 66, article 016108.
  2. T.Zhou, J.M. Carlson and J.Doyle. Mutation, Specialization, and Hypersensitivity in Highly Optimized Tolerance. PNAS, 2002.
• Group C1: Small-world graphs
  1. M.E.J.Newman. Models of the Small World: A Review . J.Stat.Phys. Vol. 101, 2000, pp. 819-841.
  2. M.E.J. Newman, C.Moore and D.J.Watts. Mean-field solution of the small-world network model. Phys. Rev. Lett. 84, 3201-3204 (2000).
  3. M.E.J.Newman. The structure and function of networks.
• Group C2: Scale-free graphs
  1. A.-L. Barabási, R. Albert, and H. Jeong Scale-free characteristics of random networks: The topology of the World Wide Web Physica A 281, 69-77 (2000).
  2. R.Albert, H.Jeong, and A.-L. Barabási. Error and attack tolerance in complex networks Nature 406 , 378 (2000).
  3. A.-L.Barabási, R.Albert and H.Jeong. Mean-field theory for scale-free random networks Physica A 272, 173-187 (1999).
• Group C3: Search in small-world graphs
  1. J.Kleinberg. The smallworld phenomenon: an algorithmic perspective.
  2. L.Adamic et al. Search in power-law networks . Phy Rev E, Vol. 64, 2001.
• Group D: Percolation
  1. N. Schwartz, R.Cohen, D.ben-Avrahm, A.-L.Barabási and S.Havlin. Percolation in directed scale-free networks. Physical Review E 66, 015104(R) (2002).
  2. R.Hanel, S.Kauffman and S.Thurner. The phase transition in random catalytic sets. Santa Fe Institute.
  3. R.Pastor-Satorras and A.Vespignani. Epidemic spreading in scale-free networks. Phy. Rev. Letters, Vol.86, No. 14, 2001.
  4. R.Meester and R.Roy. Lecture notes in percolation.
• Group E1: Phase transitions in Satisfiability
  1. P.Cheeseman et al. Where the really hard problems are . IJCAI 1991.
  2. Mitchell et al. Hard and easy distributions of sat problems. 10th National conf on AI, 1992.
  3. A.Bugacov et al. Threshold behavior in a boolean network model for SAT . Information Sciences Institute, USC.
• Group E2: Phase transitions in Satisfiability
  1. I.Rish and R.Dechter. Resolution vs. Search: Two Strategies for SAT.
  2. N.Een and N.Sorensson. An Extensible SAT-solver, SAT 2003.
• Group E3: Phase transitions in Satisfiability
  1. M.Mezard, G.Parisi and R.Zecchina. Analytic and Algorithmic Solution of Random Satisfiability Problems, Science, 2002,
  2. R.Monasson, R.Zecchina, S.Kirkpatrick, B.Selman and L.Troyansky. Determining computational complexity from characteristic 'phase transitions', Nature, 1999.
• Group E4: Phase transitions in Satisfiability
  1. A.Braunstein, M.Mezard, R.Zecchina. Survey propagation: an algorithm for satisfiability, Random Structures and Algorithms 27, 201-226 (2005)
  2. R.Williams, C.Gomes and B.Selman Backdoors To Typical Case Complexity, Proc. IJCAI-03 Acapulco, Mexico, 2003.
• Group E5: Phase transitions in Satisfiability
  1. M.Clegg, J.Edmonds and R.Impagliazzo. Using the Groebner basis algorithm to find proofs of unsatisfiability.
  2. P.Manolios and D.Vroon. Efficient Circuit to CNF Conversion. SAT 2007.
• Group F1: Boolean networks
  1. S.Bornholdt. Less is more in modeling large genetic networks, Science 310 (2005) pp.449.
  2. A.Wuensche. Discrete dynamical networks and their attractor basins. Santa Fe Institute.
  3. C.Gershenson. Introduction to Random Boolean Networks, In Bedau, M., P. Husbands, T. Hutton, S. Kumar, and H. Suzuki (eds.) Workshop and Tutorial Proceedings, Ninth International Conference on the Simulation and Synthesis of Living Systems (ALife IX). pp. 160-173.
• Group F2: Boolean networks
  1. F.Li, Y.Lu, T.Long, Q.Ouyang and C.Tang, The yeast cell-cycle network is robustly designed, PNAS 101 (14), 4781 (2004).#
  2. Y.Nochomovitz and H.Li. Highly designable phenotypes and mutational buffers emerge from a systematic mapping between network topology and dynamic output, PNAS, 2006 103(11):4180-5.
  3. M.Chaves, E.D.Sontag and R.Albert Methods of robustness analysis for Boolean models of gene control networks, IEE Proceedings in Systems Biology 153, 154-167 (2006)
• Group F3: Boolean networks
  1. R.Albert and H.G.Othmer. The topology of the regulatory interactions predicts the expression pattern of the Drosophila segment polarity genes, J.Theoretical Biology 223, 1-18 (2003)
  2. R.Albert and A.Barabási. Dynamics of complex systems: Scaling laws for the period of Boolean Networks. Physical Review Letters 84, 5660-5663 (2000).
  3. B.Luque. Measuring mutual information in random boolean networks.
• Group F4: Boolean networks
  1. H.Oktem et al. A computational model for simulating continuous time boolean networks .
  2. S.Bornholdt and T.Rohlf. Topological evolution of dynamical networks: Global criticality from local dynamics. Phys. Rev. Lett. 84 (2000) 6114-6117.
• Group G1: Topology and motifs
  1. R.Milo, S.Shen-Orr, S.Itzkovitz, N.Kashtan, D.Chklovskii and U.Alon. Network Motifs: Simple Building Blocks of Complex Networks. Science, 298:824-827 (2002).
  2. S.Shen-Orr, R.Milo, S.Mangan and U.Alon. Network motifs in the transcriptional regulation network of Escherichia coli. Nature Genetics, 31:64-68 (2002).
  3. O.Sporns and R.Kotter. Motifs in Brain Networks. PLoS Biology, Nov 2004.
• Group G2: Topology and motifs
  1. R.J.Prill, P.A.Iglesias, and A.Levchenko. Dynamic Properties of Network Motifs Contribute to Biological Network Organization, PLoS Biology Vol. 3, No. 11.
  2. T.M.A.Fink, E.Barillot and S.E.Ahnert, Dynamics of network motifs.
  3. R.Dobrin, Q.K.Beg and A.-L.Barabási. Aggregation of topological motifs in the Escherichia coli tranascriptional. BMC Bioinformatics 5: 10 (2004).
• Group H1: ODE Systems
  1. K.W.Kohn, J.Riss, O.Aprelikova, J.N.Weinstein, Y.Pommier, and J.C.Barretta. Properties of Switch-like Bioregulatory Networks Studied by Simulation of the Hypoxia Response Control System Mol Biol Cell. 2004 July; 15(7).
  2. Y.Yu, G.Wang, W.Peng, R.Simha, F.Turano and C.Zeng. Pathway Switching Explains the Sharp Response Characteristic of Hypoxia Response Network, PLoS Computational Biology Vol.3, No.8, August 2007.
• Group H2: ODE Systems
  1. N.Barkai et al. Robustness in simple biochemical networks. Nature, Vol 387, June 1997.
  2. G.von Dassow, M.E.Munro, G.M.Odell. The segment polarity network is a robust developmental module, Nature, 2000 Jul 13;406(6792):188-92.
  3. P.J.Ingram, M.P.H.Stumpf, and J.Stark. Network motifs: structure does not determine function, BMC Genomics, Vol. 7, 2006.
• Group H3: ODE Systems
  1. Slepchenko, B. M. and Terasaki, M. 2003. Cyclin aggregation and robustness of bio-switching. Mol. Biol. Cell. 14: 4695 - 4706.
  2. Slepchenko, B. M., Terasaki, M. 2004. Bio-switches: what makes them robust? Curr. Opin. Genet. Dev.14/4: 428-434.
• Group I: Bacterial intelligence
  1. I.Cohen, I.Golding, Y.Kozlovsky, E.Ben-Jacob, I.Ron. Continuous and discrete models of cooperation in complex bacterial colonies, Fractals 7 (3) 235-247 (1999).
  2. E. Ben Jacob, Y.Aharonov and Y.Shapira. Bacteria harnessing complexity, Biofilms, (2005) 1, pp.239-263
  3. E.Ben-Jacob. Harnessing Bacterial Intelligence: A Prerequisite for Human Habitation of Space, Beyond Earth, Chapter 13 (2006)
• Group J: Decomposition
  1. Principal Component Analysis.
  2. J.C.Liao, R.Boscolo, Y-L.Yang, L.M.Tran, C.Sabatti and V.Roychowdhury. Network component analysis: reconstruction of regulatory signals in biological systems. PNAS, Vol.100, No.26, Dec 2003.
• Group K: Network comparison
  1. B.McKay. Practical graph isomorphism. See also the NAUTY algorithm.
  2. J-L.Faulon. Isomorphism, automorphism partitioning and canonical labeling can be solved in polynomial-time for molecular graphs.
  3. R.T.Faizullin. Heuristic algorithm for solving the graph isomorphism problem.
  4. J.Siek. An implementation of graph isomorphism testing.
  5. J.Corneil et al. An efficient algorithm for graph isomorphism.
  6. H.Ogata et al. A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters.
• Miscellaneous
  1. M.Gell-Mann. What is complexity?. A high-level overview article on complexity by Nobel-laureate Murray Gell-Mann.
  2. B.Skyrms and R.Pemantle. A dynamic model of social network formation. PNAS, Aug 2000, Vol. 97, No. 16, pp. 9340-46.
  3. T.Kaizoji, S.Bornholdt and Y.Fujiwara. Dynamics of price and trading volume in a spin model of stock markets with heterogeneous agents. Physica A 316 (2002) 441-452.
  4. C.Kamp and S.Bornholdt. From HIV infection to AIDS: A dynamically induced percolation transition? Proc. R. Soc. London B 269 (2002) 2035-2040.
  5. E.Almaas, B.Kovacs, T.Vicsek, Z.N.Oltvai and A.-L.Barabási. Global organization of metabolic fluxes in the bacterium Escherichia coli. Nature 427, 839-843 (2004).
  6. S.Bornholdt and T.Roehl. Self-organized critical neural networks. Phys. Rev. E 67 (2003).
  7. E.Drinea et al. Balls and bins models with feedback.
  8. I.Welch. Sequential sales, learning and cascades.
  9. H.E.Stanley et al. Self-organized complexity in economics and finance. PNAS, Feb. 2002, pp.2561-2565.
  10. Molecular information theory.
  11. W.Harrison. An entropy-based measure of software complexity. IEEE. Trans. Soft. Engg. Vol. 18, No. 11, Nov 1992, pp. 1025-1029.
  12. M.Alber. Cellular Automaton Appproaches to Modeling Biological Cells.
  13. M.E.Csete and J.Doyle. Reverse Engineering of Biological Complexity. Science, 295, 1664 (2002)
  14. C.Moore. Unpredictability and undecidability in dynamical systems.
  15. A.Fabrikant. Heuristically optimized tradeoffs: a new paradigm for power laws in the internet.
  16. P.Fernandez and R.Sole. The role of computation in complex regulatory networks.
  17. X.Zhang, G.Neglia, J.Kurose and D. Towsley. Performance Modeling of Epidemic Routing UMass CMPSCI Technical Report 05-44, 2005.
  18. C.Zou, D.Towsley and W.Gong. Email virus propagation: modeling and analysis.
  19. R.Milo, S.Itzkovitz, N.Kashtan, R.Levitt, S.Shen-Orr, I.Ayzenshtat, M.Sheffer and U.Alon. Superfamilies of designed and evolved networks. Science, 303:1538-42 (2004).
  20. H.Ebel and S.Bornholdt. Evolutionary games and the emergence of complex networks.
  21. S.Bornholdt. Modeling Genetic Networks and Their Evolution: A Complex Dynamical Systems Perspective. Biological Chemistry 382 (2001) 1289-1299.
  22. R.Sole and P.Fernandez. Modularity for free in genome networks. Santa Fe Institute.
  23. B.Luque and R.Sole. Phase transitions in random networks: simple analytic determination of critical points. Phy Rev E, Jan 1997.
  24. I.Farkas, H.Jeong, T.Vicsek, A.-L.Barabási and Z.N.Oltvai. The topology of transcription regulatory network in the yeast, Saccharomyces cerevisiae. Physica A 318, 601-612 (2003).
  25. A.Vazquez, R.Dobrin, D.Sergi, J.-P.Eckmann, Z.N.Oltvai and A.-L.Barabási. The topological relationship between the large-scale attributes and local interactions patterns of complex networks. PNAS, 17940-17945 (2004).
  26. C.Moore and M.E.J.Newman. Exact solution of site and bond percolation on small-world networks Phys. Rev. E 62, 7059-7064 (2000).
  27. J.G.Esteve and F.Falceto. Phase transition in the assignment problem for random matrices.
  28. H.Kautz and B.Selman. The State of SAT, Discrete and Applied Math.