CS 8803 - Fall 2009
Network Science: Methods and Applications

Course info:

dovrolis@cc.gatech.edu

class participation tasks

Course Objectives

It is often the case that complex systems, both living and man-made, can be represented as static or dynamic networks of many interacting components. These components are typically much simpler than the overall system, while the latter often exhibits complex and emergent behaviors that the underlying components are not able to perform.

Network science is a new discipline that investigates the topology and dynamics of such complex networks, aiming to better understand the behavior and properties of the underlying systems.

The applications of network science cover physical, informational, biological, cognitive, and social systems. In this graduate seminar, we will study algorithmic, computational, and visualization methods of network science, as well as applications in communications, biology, ecology, brain science, sociology and economics. The course will go beyond the strictly structural concepts of small-world and scale-free networks, focusing on dynamic network processes (see syllabus).

References

We will mostly rely on recent research papers (See syllabus).

The following books will be useful references in certain parts of the course:

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

The course will start with a focus on network structure and topological properties. In the second half, the focus will be mostly on dynamic processes of networks and on networks. Even though most lectures will be given by the instructor, students will be participating in the lectures by giving "mini-presentations" (about 10 mins) of papers they are interested in.

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. Network synchronization, diffusion, and the paradox of heterogeneity, A.Motter et al., Physical Reviews E, 2005
3. Synchronization in complex networks, A.Arenas et al., Physics Reports, 2008 (Review paper)
Network measurement bias - "network statistics" (1 week)
- How to measure a network - sampling biases
- Statistical methods for estimation of network properties
1. Sampling biases in IP topology measurements, A.Lakhina et al., ACM SIGCOMM 2003.
2. What is the real size of a sampled network: The case of the Internet, F.Viger et al., Phys.Rev.E, 2007
3. Exploring networks with traceroute-like probes: theory and simulations L.Dall'Asta et al., Theor.Comp.Sci, 2006

Student Projects and project milestones

Ideally, every project in this course should have the potential to become an original research project, meaning that it focuses on a question that has not been previously answered in the literature. It is also acceptable to repeat the experiments or analysis of a research paper, if it is likely that the dataset will now be different or if you have doubts about the analysis.

Groups of 2-3 students are acceptable, as long as those projects require substantially more work than individual projects. Individual projects are also fine.

The objective of the projects is that students use what they learn from the course in their own research domain.

The instructor will work closely with every student/group during the semester.

All projects will be presented in class during the last week of the semester.

Project milestones

September 28: Project proposal (what you want to do, how you plan to do it, required data or other resources, 4-5 most related references - email to the instructor and also submit a hardcopy in class)
November 2: progress report
December 4: final paper and presentation slides due