CS 8803 - Fall 2009
Network Science: Methods and Applications

Course info:

Instructor: Constantine Dovrolis
Office: KACB 3346
Office hours: Thursday 2-3, or by appointment
Email: dovrolis@cc.gatech.edu
Class meeting times: MW 4:05-5:25
Classroom: KACB1447
Swiki: link (it includes the class participation tasks)

Course Objectives

References

• A. Barrat, M. Barthelemy and A. Vespignani, Dynamical Processes on Complex Networks, Cambridge, 2008.
• T.G. Lewis, Network science: theory and applications, Wiley, 2009.
• E. Kolaczyk, Statistical analysis of network data, Springer, 2009.
• S. Wasserman, K. Faust, Social Network Analysis: Methods and Applications, Cambridge University press, 1994.
• U. Alon, An Introduction to Systems Biology: Design Principles of Biological Circuits, Chapman and Hall, 2006.
• M. A. Nowak, Evolutionary Dynamics: Exploring the Equations of Life, Belknap Press/Harvard, 2006.
• S. Strogatz, Nonlinear Dynamics And Chaos: With Applications To Physics, Biology, Chemistry, And Engineering, Westview Press, 2001.

Course Structure and Syllabus

• Overview - what does "network science" mean? (1 week)
  • Overview of basic concepts - brief history
  • Regular, random, small-world, and scale-free networks
  1. On the evolution of random graphs (see page 38), P.Erdos, A.Renyi, Publ.Math.Inst.Hung.Acad.Sci, 1960
  2. An experimental study of the small world problem, J.Travers, S.Milgram, Sociometry, 1969
  3. Collective Dynamics of "Small-world" networks, D.Watts and S.Strogatz, Nature, 1998
  4. Emergence of scaling in random networks, A.Barabasi, R.Albert, Science, 1999
  5. Scale-free networks, A.Barabasi and E.Bonabeau, Scientific American, 2003
  6. The structure and function of complex networks, M.Newman, SIAM review, 2003 (Review paper)
  7. Statistical mechanics of complex networks, R.Albert and A.Barabasi, Reviews of modern physics, 2002 (Review paper)

• Various application domains and key concepts (3.5 weeks)
  • Applications of network science in biology, ecology, the Web, the Internet, sociology, etc
  • Key concepts
  1. On power-law relationships of the Internet topology, M.Faloutsos et al., ACM SIGCOMM, 1999
  2. Graph structure in the Web, A.Broder et al., Computer Networks, 2000
  3. The large-scale organization of metabolic networks, H.Jeong, et al., Nature, 2000
  4. The structure of scientific collaboration networks", M.Newman, PNAS, 2001
  5. Lethality and centrality in protein-interaction networks, Jeong et al. Nature, 2001
  6. The small-world of human language, R.Ferrer-Cancho and V.Sole, Proc.R.Soc.Lond.B, 2001
  7. Food-web structure and network theory: the role of connectance and size, J.Dunne et al., PNAS, 2002
  8. Scale-free topology of e-mail networks, H.Ebel et al., Phys.Rev.E, 2002
  9. Community structure in social and biological networks, M.Girvan, M.Newman, PNAS, 2002
  10. Network motifs: simple building blocks of complex networks, R.Milo et al., Science, 2002
  11. Hierarchical organization in complex networks, E.Ravasz and A.Barabasi, Physical Review E, 2003
  12. Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs , C.Myers, Phys.Rev.E, 2003
  13. Network structure and the diffusion of knowledge, R.Cowan and N.Jonard, Journal Econ.Dynamics and Control, 2004
  14. Random Boolean network models and the yeast transcriptional network, S.Kauffman et al., PNAS, 2004
  15. Scale-Free Networks and Sexually Transmitted Diseases: A Description of Observed Patterns of Sexual Contacts in Britain and Zimbabwe, A.Schneeberger et al., Sex.Transm.Diseases, 2004
  16. The architecture of complex weighted networks, A.Barrat et al., PNAS, 2004
  17. Organization, development and function of complex brain networks, O.Sporns et al., Trends Cognitive Science, 2004
  18. Small-world networks and functional connectivity in Alzheimer's disease, C.Stam, Cereb.Cortex, 2007
  19. Effects of topology on network evolution, P.Oikonomou, P.Cluzel, Nature Physics, 2006
  20. The product space conditions the development of nations, C.Hidalgo et al., Science, 2007
  21. Ten years in the evolution of the Internet ecosystem, A.Dhamdhere and C.Dovrolis, ACM IMC, 2008
  22. Understanding the spreading patterns of mobile phone viruses, P.Wang et al., Science, 2009 (Optional reading)

• Network evolution models and the related debate (1 week)
  • SOC (self-organized criticality) vs HOT (highly-optimized tolerance) models
  • Common criticism of network science - facts vs myths
  1. Highly-optimized tolerance: a mechanism for power laws in designed systems, J.Carlson and J.Doyle, Phys.Rev.E, 1999
  2. A first-principles approach to understanding the internet's router-level topology, L.Li et al, ACM SIGCOMM, 2004
  3. Graphs over time: densification, laws, shrinking diameters and possible explanations, J.Leskovec et al., SIGKDD, 2005
  4. Revisiting "scale-free" networks, E.Keller, BioEssays, 2005
  5. Catching the "Network Science" Bug: Insight and Opportunity for the Operations Researcher, D.Alderson, Operations Research, 2008

• Vulnerability and robustness of complex networks (1 week)
  • Structural (static) robustness
  • Dynamic robustness
  • Cascade effects
  1. Error and attack tolerance in complex networks, R.Albert et al., Nature, 2000 (see also the correction)
  2. A natural class of robust networks, M.Aldana, P.Cluzel, PNAS, 2003
  3. Response of complex networks to stimuli, Y. Bar-Yam and I.Epstein, PNAS, 2004
  4. Cascade-based attacks on complex networks, A.Motter and Y-C.Lai, Phys.Rev.E, 2002

• Diffusion, epidemics, and rumours spreading on networks (1 week)
  • Diffusion processes and epidemic spreading
  • Rumour spreading and influence networks
  • Opinion formation and consensus formation networks
  1. Epidemic spreading in scale-free networks, R.Pastor-Satorras, A.Vespignani, Physical review letters, 2001
  2. Dynamical patterns of epidemic outbreaks in complex scale-free networks, M.Barthelemy et al., J.Theor.Biol, 2005
  3. Consensus formation on adaptive networks, B.Kozma and A.Barrat, Phys.Rev.E, 2008
  4. Stochastic opinion formation in scale-free networks, M.Bartolozzi, Phys.Rev.E, 2005

• Communities and modularity in complex networks (1 week)
  • Modularity in complex networks
  • Algorithms for community/module detection
  • How does modularity affect robustness and evolvability?
  1. Modularity and community structure in networks, M.Newman, PNAS, 2006
  2. Hierarchical organization of modularity in metabolic networks, E.Ravasz et al., Science, 2002
  3. Specificity and stability in topology of protein networks, S.Maslov, K.Sneppen, Science, 2002
  4. Spontaneous evolution of modularity and network motifs, N.Kashtan, U.Alon, PNAS, 2005

• Network motifs (1 week)
  • Network motifs as functional circuits
  • Algorithms for the detection of network motifs
  1. Superfamilies of evolved and designed networks, R.Milo et al., Scence, 2004
  2. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs, N.Kashtan et al., Bioinformatics, 2004
  3. Local graph alignment and motif search in biological networks, J.Berg and M.Lassig, PNAS, 2004 (OPTIONAL)
  4. Network motifs in the transcriptional regulation network of Escherichia coli, S.Shen-Orr et al., Nature Genetics, 2002
  5. Network motifs: structure does not define function, P.Ingram et al., BMC genomics, 2005

• Adaptive co-evolutionary networks (1 week)
  • Co-evolutionary networks
  • A nice example: the Jain-Krishna model
  • Applications of adaptive networks in learning
  1. Adaptive coevolutionary networks: a review, T.Gross and B.Blasius, J.Royal Society Interface, 2008 (Review paper)
  2. Dynamics of Networking Agents Competing for High Centrality and Low Degree, P.Holme et al., Phys.Rev.Letters, 2006
  3. A model for the emergence of cooperation, interdependence, and structure in evolving networks , S.Jain and S.Krishna, PNAS 2001
  4. Phenomenological models of socioeconomic network dynamics, G.Ehrhardt et al., Phys.Rev.E, 2006
  5. Adaptive learning by extremal dynamics and negative feedback, P.Bak and D.Chialvo, Phys.Rev.E, 2001

• Strategic network formation games (1 week)
  • Network formation games
  • Evolutionary dynamics on networks
  • Emergence of cooperation
  1. A survey of models of network formation: stability and efficiency, MO Jackson, Game theory and information, 2003 (Review paper)
  2. Cooperation and emergence of role differentiation in the dynamics of social networks, V.Eguiluz et al., Am.J.Social. 2005
  3. Incentives to Cooperate in Network Formation, H.Lugo et al., Comp.Economics, 2006
  4. A simple rule for the evolution of cooperation on graphs and social networks, H.Ohtsuki et al., Nature, 2006
  5. Evolutionary dynamics of social dilemmas in structured heterogeneous populations, F.Santos et al., PNAS, 2006

• Navigation and search in networks (1 week)
  • Searching with only local information
  • Network "navigability"
  • Geographic routing, social network routing
  1. The small-world phenomenon: an algorithm perspective, J.Kleinberg, ACM STOC, 2000
  2. Search in power-law networks, L.Adamic et al., Phys.Review E, 2001
  3. Geographic routing in social networks, D.Liben-Nowell, PNAS, 2005

• Synchronization processes on networks (1 week)
  • Coupled oscillators and the Kuramoto model
  • Synchronizability in complex networks
  1. From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators S.Strogatz, Physica D, 2000
  2. Synchronization in small-world systems, M.Barahona and L.Pecora, Physical Review Letters, 2002
  3. Synchronization in scale-free dynamics: robustness and fragility, X.Wang and G.Chen, IEEE Trans.Circuits and Systems, 2001
  4. Network synchronization, diffusion, and the paradox of heterogeneity, A.Motter et al., Physical Reviews E, 2005
  5. Spontaneous structure formation in a network of dynamic elements, J.Ito and K.Kaneko, Physical Reviews E, 2003
  6. Synchronization in complex networks, A.Arenas et al., Physics Reports, 2008 (Review paper)

• Network measurement bias - Algorithms for network inference (0.5 week)
  • How to measure a network - sampling biases
  • Algorithms for network inference
  1. What is the real size of a sampled network: The case of the Internet, F.Viger et al., Phys.Rev.E, 2007
  2. On the marginal utility of network topology measurements, P.Barford, ACM IMW 2001
  3. Exploring networks with traceroute-like probes: theory and simulations L.Dall'Asta et al., Theor.Comp.Sci, 2006

Student Projects and project milestones

Class participation

Link to class participation tasks

Network datasets

• Mark Newmann's pointers
• Eric Kolaczyk's pointers
• Duncan Watts' pointers
• Albert Barabasi's pointers
• Uri Alon's pointers
• The Pajek pointers
• Alex Arenas' pointers
• Jon Kleinberg's pointers
• Jure Leskovec's pointers
• Peter Skomoroch's pointers
• TrustLet project's pointers
• AOL dataset: 20M web queries collected from ~650k users over three months.
• "Reality mining" project dataset from MIT
• Our dataset for the evolution of the Internet AS ecosystem between 1998-2008
• pointers to more publicly available datasets are very welcomed

Network analysis tools

• Network Workbench (very interesting!)
• Pajek network visualization (Windows)
• Jung network analysis
• GraphViz
• Uri Alon's network motif detection software
• Matlab's Random Boolean Networks (RBN) toolbox

Network science links

• Network science research center at Central European University in Hungary
• Albert Barabasi's lab at Northeastern
• Network science center at West Point

Grading

• Class participation and mini-presentations: 50%
• Project and final presentation: 50%