1. Introduction to networks 1.1 Overview of the course: The premise of the course is that many phenomena are best modeled by processes that interact with an underlying network. Examples: Network Coordination Games, Viral Marketing, Epidemic Spread 1.2 Basic definitions: vertex or node, edge, neighbors, degree, shortest path, cycle, tree, complete graph, bipartite graphs, directed graphs, weighted graphs, adjacency matrix, connected components, etc. [Newman Ch 6] 1.3 Examples of technological networks (internet, telephone network, power grids, transportation networks), social networks (facebook, movie collaboration, paper collaboration), information networks (web), biological networks (neural networks, ecological networks), contact networks (HCW login netwoks), etc. [Newman Ch 1-3] 1.4 Overview of available network data. Newman's Graph data sets: http://www-personal.umich.edu/~mejn/netdata/ SNAP Graph library: http://snap.stanford.edu/data/ 1.5 Wikipedia entry on social network analysis software: http://en.wikipedia.org/wiki/Social_network_analysis_software Some information about programming in Python and the NetworkX library: http://networkx.lanl.gov/ A distribution of Python for scientific computing and visualization: http://www.enthought.com/products/epd.php 2. Random models of networks 2.1 The Erdos-Renyi model of random graph. Some basic properties such as degree distribution, component sizes, path lengths, etc. [Newman Ch 12] 2.2 The inadequacy of the Erdos-Renyi model: ``small-world'' networks, networks with high clustering coefficient, networks that have degree distribution that is not Poisson and may be heavy-tailed, etc. A simple alternate random graph model. [Watts and Strogatz Nature 1998] 2.3 The Kleinberg result showing that some graph models are not only small-world, but they permit "decentralized search." [Easley-Kleinberg Ch 20; Kleinberg STOC 2000] 2.4 Random graphs with general degree distributions. The configuration model. Probability generating functions. [Newman Ch 13] 2.4 Models of network formation. The ``preferential attachment'' model of Barabasi et al. [Newman Ch 14; Barabasi and Albert Science 1999] 2.5 Stochastic Kronecker Graphs [Leskovec et al. Faloutsous PKDD 2007] 3. The spread of "influence" through a network 3.1 The Christakis-Fowler work on the spread of obesity, happiness, etc. via social networks [Christakis and Fowler NEJM 2007; Fowler and Christakis BMJ 2008 and PNAS 2010] 3.2 Response to the Christakis-Fowler work on distnguishing between spread of influence over a network versus diffusion due to homophily [Sinan Aral et al PNAS 2009; Shalizi and Thomas 2011] 3.2 Modeling information cascades [Kleinberg-Easley Ch 19] 3.3 Viral Marketing [Kempe et al. KDD 2003; Leskovec et al. ACM Trans Web 2007] 4. Spread of disease on networks 4.1 Random mixing models: SI, SIS, SIR, SIRS, basic differential equations, etc. [Hethcote SIAM Review 2000; Newman Ch 17] 4.2 Basic Reproductive Number and analysis of branching processes [Easley-Kleinberg Ch 21] 4.3 Analysis of SIR on the Configuration model [Newman Ch 17] 4.4 Synchronization in disease incidence, explanation via models, and observational studies from Syphilis [Easley-Kleinberg Ch 21; Kuperman and Abramson Phys Rev Let 2001; Grassly et al. Nature 2005] 4.3 Example of studies with some specific diseases [Meyers et al. EID 2003] 5. Information Networks 5.1 The structure of the web [Easley-Kleinberg Ch 13] 5.2 Link analysis and web search, Page rank, Spectral Analysis of Page rank and hubs and authorities, random walks [Easley-Kleinberg Ch 14] 5.3 Auctions and matching markets [Easley-Kleinberg Chs 9 and 10] 5.4 Sponsored search markets [Easley-Kleinberg Ch 15] 6. Games on Networks 6.0 Basics of Game Theory: strategies, dominant strategies, dominated strategies, pure strategies and mixed strategies, Nash equilibrium 6.1 Modeling network traffic as a game; Braess Paradox; The price of anarchy [Easley-Kleinberg Ch 8; Roughgarden and Tardos JACM 2002] 6.2 Modeling Voluntary Vaccination as a game [Aspnes et al SODA 2006] 6.3 Example of game-theoretic analysis applied to flu vaccine behavior [Cornforth et al PLOS Comp Bio 2011] ------------------------------------------------------------------------------------------------------- Bibliography @book{EasleyKleinberg, author = {D. Easley and J. Kleinberg}, publisher = {Cambridge Univ Pr}, title = {Networks, crowds, and markets: Reasoning about a highly connected world}, year = {2010} } @book{Newman, author = {M. E. J. Newman}, title = {Networks: An Introduction}, publisher = {Oxford University Press}, year = {2010} } @article{Watts:1998p659, author = {DJ Watts and SH Strogatz}, journal = {Nature}, number = {6684}, pages = {440--442}, pmid = {14716149512146230113related:YZsDBQNEOswJ}, rating = {0}, read = {Yes}, title = {Collective dynamics of `small-world' networks}, uri = {papers://E3F215B9-D1A0-4FF8-9C33-BBAA65AAD38D/Paper/p659}, volume = {393}, year = {1998} } @article{Hethcote, author = {Herbert W. Hethcote}, doi = {10.1137/S0036144500371907}, journal = {SIAM Review}, keywords = {thresholds; basic reproduction number; contact number; epidemiology; infectious diseases}, number = {4}, pages = {599--653}, publisher = {SIAM}, title = {The Mathematics of Infectious Diseases}, url = {http://link.aip.org/link/?SIR/42/599/1}, volume = {42}, year = {2000} } @article{BarabasiAlbert, author = {Albert-L{\'a}szl{\'o} Barab{\'a}si and R{\'e}ka Albert}, journal = {Science}, number = {5439}, pages = {509--512}, title = {Emergence of Scaling in Random Networks}, volume = {286}, year = {1999} } @article{Meyers:2003p839, author = {L.A. Meyers and MEJ Newman and M. Martin and S. Schrag}, journal = {Emerging Infectious Diseases}, number = {2}, pages = {204--210}, publisher = {NATIONAL CENTER FOR INFECTIOUS DISEASES}, title = {Applying network theory to epidemics: control measures for Mycoplasma pneumoniae outbreaks}, volume = {9}, year = {2003} } @article{AspnesChangYampolskiy, author = {J Aspnes and K Chang and A Yampolskiy}, date-added = {2011-01-02 20:04:31 -0600}, date-modified = {2011-01-27 16:35:24 -0600}, journal = {Journal of Computer and System Sciences}, local-url = {file://localhost/Users/dcurtis/Dropbox/Papers/Papers/Aspnes/2006-Journal\%20of\%20Computer\%20and\%20System\%20Sciences-Inoculatio-1.pdf}, number = {6}, pages = {1077--1093}, pmid = {14820906302146272005related:BdvG3MFvrs0J}, rating = {0}, read = {Yes}, title = {Inoculation strategies for victims of viruses and the sum-of-squares partition problem}, uri = {papers://E3F215B9-D1A0-4FF8-9C33-BBAA65AAD38D/Paper/p1568}, volume = {72}, year = {2006} } @ariticle{Cornforth2011, author = {D.M. Cornforth and T.C. Reluga and E. Shim and C.T. Bauch and A.P. Galvani and L.A. Meyers}, title = {Erratic flu vaccination emerges from short-sighted behavior in contact networks}, journal = {PLoS Computational Biology}, volume = 7, number = 1, year = 2011 } @inproceedings{Kleinberg00, author = {Jon M. Kleinberg}, title = {The small-world phenomenon: an algorithm perspective}, booktitle = {STOC}, year = {2000}, pages = {163-170}, ee = {http://doi.acm.org/10.1145/335305.335325}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{Leskovecetal2010, title = {Kronecker Graphs: An approach to modeling networks}, author = {J. Leskovec and D. Chakrabarti and J. Kleinberg and C. Faloutsos and Z. Ghahramani}, title = {Journal of Machine Learning Research}, volume = 11, pages = {985--1042}, year = 2010 } @article{ChristakisFowler2007, title = {The Spread of Obesity in Social Networks}, author = {N.A. Christakis and J.H. Fowler}, journal = {New England Journal of Medicine}, volume = 357, number = 4, pages = {370--379}, year = 2007 } @article{FowlerChristakis2008, title = {Dynamic Spread of Happiness in a Large Social Network: Longitudinal Analysis Over 20 Years in the Framingham Heart Study}, author = {James H. Fowler and Nicholas A. Christakis}, journal = {British Medical Journal}, volume = 337, year = 2008 } @article{FowlerChristakis2010, title = {Cooperative Behavior Cascades in Human Social Networks}, author = {James H. Fowler and Nicholas A. Christakis}, title = {PNAS} volume = 107, number = 12, pages = {5334--5338}, year = 2010 } @article{Araletal, title = {Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks}, author = {Sinan Aral and Lev Muchnik and Arun Sundararajan}, journal = {PNAS}, year = 2009, volume = 106, number = 51, pages = {21544--21549} } @article{ShaliziThomas, author = {Cosma Rohilla Shalizi and Andrew C. Thomas}, title = {Homophily and Contagion Are Generically Confounded in Observational Social Network Studies}, journal = {Sociological Methods and Research}, volume = 40, year = 2011, pages = {211--239} } @inproceedings{KempeKleinbergTardos, author = {David Kempe and Jon M. Kleinberg and {\'E}va Tardos}, title = {Maximizing the spread of influence through a social network}, booktitle = {KDD}, year = {2003}, pages = {137-146}, ee = {http://doi.acm.org/10.1145/956750.956769}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{LeskovecAH07, author = {Jure Leskovec and Lada A. Adamic and Bernardo A. Huberman}, title = {The dynamics of viral marketing}, journal = {TWEB}, volume = {1}, number = {1}, year = {2007}, ee = {http://doi.acm.org/10.1145/1232722.1232727}, bibsource = {DBLP, http://dblp.uni-trier.de} } @article{KupermanAbramson, author = {M. Kuperman and G. Abramson}, title = {"Small World Effect in an Epidemiological Model"}, journal = {Physical Review Letters}, volume = 86, number = 13, pages = {2909--2912}, year = {2001} } @article{GrasslyFraserGarnett, author = {Grassly NC and Fraser C and Garnett GP}, year = 2005, title = {Host immunity and synchronized epidemics of syphilis across the United States}, journal = {Nature}, volume = 433, pages = {417--421} } @article{RoughgardenTardos2002, author = {Roughgarden, Tim and Tardos, \'{E}va}, title = {How bad is selfish routing?}, journal = {J. ACM}, volume = {49}, issue = {2}, month = {March}, year = {2002}, issn = {0004-5411}, pages = {236--259}, numpages = {24}, url = {http://doi.acm.org/10.1145/506147.506153}, doi = {http://doi.acm.org/10.1145/506147.506153}, acmid = {506153}, publisher = {ACM}, address = {New York, NY, USA}, keywords = {Braess's Paradox, Nash equilibria, network flow, selfish routing}, }