The Natural Science of Networks

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

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