Fall 2008

This course has been completed. I would like to thank to all the people that attended the seminars. Special thanks to those brave ones that attended
all of them.

All the best

C

Instructor:

Cesar A. Hidalgo PhD (personal webpage)

Goal:

Networks are an ubiquotous way to represent complex systems, including those in the social and economic sciences. To make sense of complex systems in the social sciences and economics using network it is important to begin by studying them from a fundamental point of view. In this course we introduce the basic, natural science of networks and some applications to social and economic sciences.

Summary:

Complex systems, such as the cell, cities or the economy, are formed by heterogeneous collections of components and interactions. During recent years the science of networks emerged as an alternative approach to analyze the structure and evolution of complex systems. In this seven course seminar we introduce the basic concepts and applications of network science, developed by natural scientists, for a social science audience. The seminar will cover (i) the most basic network models, (ii) the statistics used to characterize network structure and dynamics (iii) a few examples of applications in which these concepts have been applied, including applications to micro and macroeconomics.

Requirements:

An open mind and the will to learn.
The course is not for credit and does not require any out of class work.
The course is completely self contained. No significant academic background is necessary.

Room:

Perkins Room (4th Floor Rubenstein Building, Center for International Development, Harvard Kennedy School)

Schedule:

The Schedule Has Changed! Again! :-)
Classes 1-4 THEORY AND METHODS (Sept 16 th ,Sept 30 th, Oct 7 th, Oct 14th) 4:10pm– 5:30 pm
Classes 5-7 APPLICATIONS (Oct 21st, Nov 18 th, Nov 25 th ) 4:10pm– 5:30 pm

Syllabus: (download .pdf)

TOPICS
REVIEWED LITERATURE

Class 1: Random networks, simple graphs and basic network characteristics.

(download powerpoint ppt pptx)

- Introduction to network science.
- Erdos and Renyi random graphs (k,P(k))
- Clustering coefficient and percolation transition of Random Networks. (k,C,P c)
- The Small World Effect (L)
- Watts-Strogatz Small World Networks
- Bacon Numbers

BONUS SECTION:
Chaos.

1.- R. Albert, A.-L. Barabási
Statistical mechanics of complex networks
Reviews of Modern Physics 74, 47-97 (2002)
2.-D. J. Watts and S. H. Strogatz.
Collective dynamics of 'small-world' networks,
Nature, 393, 440-442 (1998)
3.-D. J. Watts, P. S. Dodds, M. E. J. Newman.
Identity and search in social networks.
Science, 296, 1302-1305 (2002)
4.- S. Milgram.
The Small World Problem.
Psychology Today, May 1967. pp 60 - 67
5.- R. Albert, H. Jeong, A.-L. Barabási
Diameter of the world wide web
Nature 401, 130-131 (1999)
 

Class 2: Scale-Free Networks

(download powerpoint ppt pptx)

- Scale Free Networks in Nature and Technology (P(k)) (NetLogo Demos)
- Barabasi-Albert Model
- Local Scale-Free Network Models
- Fitness Model
- Error and Attack Tolerance

BONUS SECTION:
Fractals.

1.- R. Albert, A.-L. Barabási
Statistical mechanics of complex networks
Reviews of Modern Physics 74, 47-97 (2002)
2.- A.-L. Barabási, R. Albert
Emergence of scaling in random networks
Science 286, 509–512 (1999)
3.- R. Albert, H. Jeong, A.-L. Barabási
Error and attack tolerance of complex networks
Nature 406, 378–482 (2000)
4.-G. Bianconi, A.-L. Barabási
Competition and multiscaling in evolving networks
Europhysics Letters 54, 436-442 (2001)
5.- A Vazquez
Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations
Physical Review E 67, 056104 (2003)
 

Class 3: Characterizing Network Topology

(download powerpoint ppt pptx)

- Centrality (k,BC,Eigenv.Centrality,Page Rank )
- Density (C,TO)
- Size (L,D,G c)
- Motifs
- Hierarchical Structure C(k)
- Directed Networks Bow Tie Structure
- Association Between Local and Global Topology
- Clustering on weighted networks

BONUS SECTION:
Drawing your own Networks using Cytoscape.
Files Used in the Tutorial .rar

1.-Freeman, L. C.
A set of measures of centrality based on betweenness. Sociometry 40, 35--41 (1977)
2.- S. Brin, L. Page
The anatomy of a large-scale hypertextual Web search engine
Computer Networks and ISDN Systems 30, 107-117(1998)
3.-
R. Milo, et al.
Network Motifs: Simple Building Blocks of Complex Networks
Science 298:824-827 (2002)
4.- E. Ravasz et al.
Hierarchical organization of modularity in metabolic networks
Science 297, 1551-1555 (2002)
5.- A. Vazquez et al.
The topological relationship between the large-scale attributes and local interactions patterns of complex networks
PNAS 101:17940-17945 (2004)
6.- G. Bianconi, N. Gulbahce, A. E. Motter,
Local structure of directed networks
Phys. Rev. Lett.  100, 118701 (2008)

7.- J. Saramäki et al.
Generalizations of the clustering coefficient to weighted complex networks,
Phys. Rev. E 75, 027105 (2007)

Class 4: Community Structure

download presentation

by James Bagrow PhD .pdf
by Sune Lehman PhD .pdf

- Graph Partitioning Methods
- Girvan, Newman
- Newman Modularity Matrix
- Clauset Matrix Method
- Clique Percolation Algorithm (Palla, Lehman)
- Local community finding methods (Bagrow)

BONUS SECTION:
Community finding software.

1.- M Girvan, MEJ Newman
Community structure in social and biological networks

PNAS , 2002
2.- G. Palla, I. Derényi, I. Farkas, T. Vicsek.
Uncovering the overlapping community structure of complex networks in nature and society.
Nature 435, 814 (2005)
3.- S. Lehmann, M. Schwartz, L. K. Hansen
Biclique communities
Physical Review E 78, 016108:1-9 (2008)
4.- JP Bagrow, EM Bollt,
Local method for detecting communities
Phys. Rev. E 72, 046108 (2005)
 

Class 5: Network Dynamics

(download powerpoint ppt pptx)

- Epidemic Spreading (Vespignani, Colizza (effects of P(k),P(w)))
- Mobile Phone Network Dynamics
- Kauffman Model
- Team Assembly Dynamics
- Triadic Closure

 

1.- G. Palla, A.-L. Barabási, T. Vicsek
Quantifying social group evolution
Nature 446:7136, 664-667 (2007)
2.-J.-P. Onnela, et al.

Structure and tie strengths in mobile communication networks

PNAS 104 (18), 7332-7336 (2007)
3.- C.A. Hidalgo, C. Rodriguez-Sickert
The dynamics of a mobile phone network
Physica A 387:12, 3017-3024 (2008)
4.-G. Kossinets and D. J. Watts.

Empirical Analysis of Evolving Social Networks.
Science, 311, 88-90 (2006)
5.- R Guimerà, Uzzi, Spiro, Amaral,
Team assembly mechanisms determine collaboration network structure and team performance,
Science 308, 697-702 (2005)

6.- V. Colizza, A. Barrat, M. Barthelemy, A. Vespignani
The role of the airline transportation network in the prediction and predictability of global epidemics
PNAS
103: 2015-2020 (2006)
7.-
R. Pastor-Satorras, A. Vespignani
Epidemic spreading in scale-free networks
Physical Review Letters 86, 3200-3203 (2001)

Class 6: Networks in Biology

(download powerpoint ppt pptx)

- The Basics of Molecular Biology
- Different Types of Biological Networks (PPI, Gene Regulation, Metabolic,Co-Expression, Food Webs, Cross-Pollination)
- Biological Network Properties (P(k),C(k),Connectivity and Lethality)
- Date and Party Hubs
- Disease Networks (Goh, Lee, Hidalgo)

1.- JDJ Han et al
Evidence for dynamically organized modularity in the yeast protein-protein interaction network

Nature, (2004)
2.-E. Almaas et al
Global organization of metabolic fluxes in the bacterium Escherichia coli
Nature 427, 839-843 (2004)

3.- Rual J-F, et al.
Towards a proteome-scale map of the human protein-protein interaction network.
Nature
437:1173-8, (2005)

4.- K.-I. Goh, et al.
The human disease network
PNAS 104 (21), 8685 (2007)
5.- D.-S. Lee et al.
The implications of human metabolic network topology for disease comorbidity
PNAS 105, 9880-9885 (2008).

 

Class 7: Networks in Economy

(download powerpoint ppt pptx)

- Axelrod's Tournament
- Networks and Game Theory
- The Product Space and economic development.
- BiPartite Network Analysis
- Countries, Products and Capabilities

 

1.- E. Lieberman, C. Hauert, MA Nowak
Evolutionary dynamics on graphs
Nature, 433:312-316 (2005)
2.- H. Ohtsuki, C. Hauert, E. Lieberman, MA Nowak
A simple rule for the evolution of cooperation on graphs and social networks
Nature 441:502-505
3.-
FC Santos, MD Santos, JM Pacheco
Social diversity promotes the emergence of cooperation in public good games
Nature 454:213-216
4.- J Gomez-Gardenez, M Campillo, LM Floria, Y Moreno
Dynamical Organization of Cooperation in Complex Topologies
Physical Review Letters 98, 108103 (2007)
5.- MA Nowak, K Sigmund
Tit for tat in heterogenous populations
Nature 355:250-252
6.- CA Hidalgo, B Klinger, A-L Barabasi, R Hausmann.
The Product Space and its Consequences for Economic Growth
Science 317: 482-487 (2007)
7.- C.A. Hidalgo, R. Hausmann
A Network View of Economic Development
Development Alternatives, Summer (2008)
8.- R Hausmann, B Klinger
The structure of the product space and the evolution of comparative advantage
CID working paper No. 146

ADDITIONAL SUGGESTED LITERATURE:

Books on Networks:

Albert-Laszlo Barabasi
Linked
R. Pastor-Satorras, A.Vespignani
Evolution & Structure of the Internet
M. Newman, A-L Barabasi, D.J. Watts
The Structure & Dynamics of Networks
Duncan J. Watts
Small Worlds
Guido Caldarelli
Scale-Free Networks