T79.7003 Graphs and Networks
General Information
Instructor: Charalampos E. Tsourakakis
Classroom: Lecture hall T5 (CS building)
Original Web page link: T79.7003
Time: Fri 25pm
Email: tsourolampis at gmail dot com.
Grading
 3 homeworks, 5% each (total 15%)
 2 tests, 30% each (total 60%)
 1 Project, 25%
Homework policy
You may discuss the problems with other students but you must write your solutions
on your own and list your collaborators. You may not search the Web for solutions.
You may consult outside materials, but you must cite your sources in your solutions.
Violation of the policy may result in receiving a zero grade for the question or the assignment or even the whole course. The penalty will be assessed at the instructor’s discretion.
Handouts
 Lecture 1 (Sep 13, 2013): introduction
 Lecture 2 (Sep 20, 2013): thresholds for K4s and graph connectivity
 Optional readings
 Colorful Triangle Counting and a MapReduce Implementation
This paper contains the analysis of a randomized triangle counting algorithm
which is based on the second moment method.  Cayley’s formula (ch. 26)
We used Cayley’s formula to upper bound the expected number of components of order k
in G(n,p). This book contains four beautiful proofs of the formula.
 Colorful Triangle Counting and a MapReduce Implementation
 Optional readings

 Lecture 3 (Sep 27, 2013): Phase transition
 HW1 is out
 Suggested papers are out
 Lecture slides (pdf)
 Readings
 Simulation video, the evolution of the G(n,p) random graph
 Lecture 3 (Sep 27, 2013): Phase transition
 Lecture 4 (Oct 4, 2013): Probabilistic tools and random graph applications I
 Readings
 Concentration (read Sections 1,2, pages 110)
 Readings
 Lecture 5 (Oct 11, 2013): Probabilistic tools and random graph applications II
 Readings
 Concentration (read Section 3, pages 1026)
 Sharp concentration of the chromatic number on random graphs G(n,p)
 Optional Readings
 Readings
 Midterm exam (Oct. 18, 2013)
 Fall midterm break (Oct. 25, 2013)
 Lecture 6 (Nov 1, 2013): Properties and models of realworld networks. Degree sequence of preferential attachment
 Readings
 The degree sequence of a scalefree random graph process
 For a quick proof sketch check 4.1 from this book chapter.
 Navigation in a small world
 Collective dynamics of ‘smallworld’ networks
 Suggested Readings
 CHKNS model
 For more on the compressibility of the Web graph, read the paper Models for the Compressible Web and slides by Ravi Kumar on the above paper
 For an alternative way of obtaining degree sequences which follow a power law, read the paper Heuristically optimized tradeoffs: A new paradigm for power laws in the Internet
 Readings
 Lecture 7 (Nov 8, 2013): Random Walks on Graphs
 Lecture 8 (Nov 15, 2013): Spectral Clustering, Cheeger’s inequality
 Lecture notes, Chapter 1 from Grimmett’s book (pdf) (cont.)
 KDD’13 Tutorial (slides 133176)
 Readings
 Cheeger’s inequality I, Cheeger’s inequality II (Dan Spielman’s notes)
 Lecture 9 (Nov 22, 2013): One hour guest lecture on boostrap percolation by Dr. Thomas Vallier + project presentations
 Bootstrap percolation on G(n,p)
 Slides by Thomas Vallier
 Project Presentations
 Orestis
 Hristo
 Miquel
 Abdulmelik
 Lecture 10 (Nov 29, 2013): Project presentations
 Geraud, Louiza, Sanja
 Eric, Emanuelle
 Ehsan
 Polina
 HW3 is out
 Finland’s Independence Day (Dec 6, 2013)
 Lecture 11 (Dec 13, 2013): Various topics
 Readings
 Chapters 3,6 and 8 from Mathematical and Algorithmic Analysis of Network and Biological Data
 Spectral Sparsification of Graphs by Nikhil Srivastava
 Spectral Sparsification of Graphs and Approximations of Matrices I by Daniel Spielman
 Spectral Sparsification of Graphs and Approximations of Matrices II by Daniel Spielman
 Readings
Data Sources
Stanford Large Network Dataset Collection (SNAP)
The University of Florida Sparse Matrix Collection (UFS)
Twitter graph (2009)
Software, Libraries
NetworkX (Python)
JUNG (Java)
Stanford Large Network Analysis (SNAP system) (C++, Jure Leskovec)
MATLAB BGL (Matlab, David Gleich)
Mathematica, Graph and Network Modeling (Mathematica)
Visualization software
Related Web pages
David Aldous (Berkeley)
EaslyKleinberg (Cornell)
Dan Spielman (Yale)
Books, Notes
Rick Durrett’s book
Networks, Crowds, and Markets: Reasoning About a Highly Connected World
Remco Van Der Hofstad’s notes
Alan Frieze’s notes (handwritten)
Suggested papers
A list of suggested papers follows. I have grouped the papers by category to facilitate your search, but it is worth outlining that some papers could belong to more than one category.
Stochastic graph models

 A geometric preferential attachment model of networks
A. Flaxman, A. Frieze, J. Vera  Affiliation networks
S. Lattanzi and D. Sivakumar  The Diameter of a Scalefree Random Graph
B. Bollobas, O. Riordan  A General Model of Web Graphs
C. Cooper, A. Frieze  First to Market is not Everything: an Analysis of Preferential Attachment with Fitness
C. Borgs, J. Chayes, C. Daskalakis, S. Roch  Estimating and Understanding Exponential Random Graph Models
S. Chatterjee, P. Diaconis  Graph Evolution: Densification and Shrinking Diameter
J. Leskovec, J. Kleinberg, C. Faloutsos  Stochastic Kronecker graphs
M. Mahdian, Y. Xu  A Random Graph Model for Power Law Graphs
W. Aiello, F. Chung, L. Lu  The Diameter of Sparse Random Graphs
Fan Chung, Linyuan Lu  Stochastic models for the web graph (ps)
R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, E. Upfal  Models for the Compressible Web
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, and Prabhakar Raghavan  The Diameter of random power law graphs
Linyuan Lu
 A geometric preferential attachment model of networks
Estimating models from network data

 Winners don”t take all: Characterizing the competition for links on the Web
Pennock, D. M., Flake, G. W., Lawrence, S., Glover, E. J., and Giles, C. L.  Moment based estimation of stochastic Kronecker graph parameters
David F. Gleich and Art B. Owen  Kronecker graphs: An approach to modeling networks
Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, Zoubin Ghahramani
 Winners don”t take all: Characterizing the competition for links on the Web
Strategic graph models

 Anarchy is free in network creation
R. Graham, L. Hamilton, A. Levavi, P.S. Loh  The Price of Anarchy in Network Creation Games
E. Demaine, M. Hajiaghayi, H. Mahini, M. Zadimoghaddam  On a network creation game
A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, and S. Shenker.
Check also these  A Strategic Model of Social and Economic Networks
M. Jackson, A. Wolinsky
 Anarchy is free in network creation
Diffusion related (rumor spreading, cascades, network reconstruction etc.)

 Rumor Spreading in Social Networks.
F. Chierichetti, S. Lattanzi and A. Panconesi  Trace Complexity of Network Inference
B. Abrahao, F. Chierichetti, R. Kleinberg, and A. Panconesi  Inferring Networks of Diffusion and Influence
M. GomezRodriguez, J. Leskovec, A. Krause  Modeling Information Propagation with Survival Theory
Manuel Gomez Rodriguez, Jure Leskovec, Bernhard Schölkopf  Spotting Culprits in Epidemics: How many and Which ones?
B. A. Aditya, J. Vrekeen, C. Faloutsos  Rumors in a Network: Who’s the Culprit?
Devavrat Shah, Tauhid Zaman  Information Cascade at Group Scale
M. Eftekhar, Y. Ganjali, N. Koudas  Randomized Rumor Spreading
R. Karp, C. Schindelhauer, S. Shenker, B. Vöcking
 Rumor Spreading in Social Networks.
Social learning

 Dynamics of information exchange in endogenous social networks
Daron Acemoglu, Kostas Bimpikis, Asuman Ozdaglar  Bayesian learning in social networks
Daron Acemoglu, Munther Dahleh, Ilan Lobel, Asuman Ozdaglar
Check this out too.
 Dynamics of information exchange in endogenous social networks
Subgraphs

 Counting Arbitrary Subgraphs in Data Streams
Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun  Triangle counting in dynamic graph streams
K. Kutzkov, R. Pagh  On the Streaming Complexity of Computing Local Clustering Coefficients
K. Kutzkov, R. Pagh  Efficient Triangle Counting in Large Graphs via Degreebased Vertex Partitioning
Mihail N. Kolountzakis, Gary L. Miller, CET, Richard Peng  Counting Triangles in Data Streams
L. Buriol, G. Frahling, S. Leonardi, A. MarchettiSpaccamela, C. Sohler  Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections
J. Ugander, L. Backstrom, J. Kleinberg  Counting Stars and Other Small Subgraphs in Sublinear Time
Mira Gonen, Dana Ron, Yuval Shavitt
Check this nice talk on sublinear algorithms and property testing here.
 Counting Arbitrary Subgraphs in Data Streams
Dense subgraphs and graph partitioning

 A Local Algorithm for Finding WellConnected Clusters
Zeyuan A. Zhu, Silvio Lattanzi and Vahab Mirrokni  Streaming Balanced Graph Partitioning for Random Graphs
Isabelle Stanton  Spectral Partitioning of Random Graphs
Frank McSherry  Statistical Properties of Community Structure in Large Social and Information Networks
Jure Leskovec, Kevin Lang, Anirban Dasgupta, Michael Mahoney  On finding dense subgraphs
Samir Khuller and Barna Saha  Local Graph Partitioning using PageRank Vectors
R. Andersen, F. Chung, K. Lang  Balanced label propagation for partitioning massive graphs
Johan Ugander, Lars Backstrom
 A Local Algorithm for Finding WellConnected Clusters
Evolutionary dynamics on graphs

 Evolutionary dynamics on graphs and the Supplement
E. Lieberman, C. Hauert, M. Nowak  Natural models for evolution on networks.
G.B. Mertzios, S. Nikoletseas, C. Raptopoulos, P.G. Spirakis  Approximating fixation probabilities in the generalized Moran process
J. Diaz, L.A. Goldberg, G.B. Mertzios, D. Richerby, M. Serna, and P.G. Spirakis
 Evolutionary dynamics on graphs and the Supplement
Learning

 Learning from labeled and unlabeled data on a directed graph
D. Zhou, J. Huang, B. Schoelkopf  Fitting a graph to vector data
S. Daitch, J. Kelner, D. Spielman  Fast Random Walk with Restart and Its Applications
H. Tong, C. Faloutsos, J. Pan  Learning from labeled and unlabeled data using graph mincuts
A. Blum, S. Chawla  The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
J. Sun, S. Boyd, L. Xiao, and P. Diaconis
or/and a related NIPS paper
Colored Maximum Variance Unfolding
L. Song, A. Smola, K. Borgwardt, A. Gretton
 Learning from labeled and unlabeled data on a directed graph
Various
 On the Bias of Traceroute Sampling: or, PowerLaw Degree Distributions in Regular Graphs
D. Achlioptas, A. Clauset, D. Kempe, C. Moore  Trading in Networks: Theory and Experiment
S. Choi, A. Galeotti, S. Goyal  The Network Origins of Large Economic Downturns
D. Acemoglu, A. Ozdaglar, A. TahbazSalehi  A Random Graph Model of MultiHospital Kidney Exchanges
Panos Toulis, David Parkes  Suppressing cascades of load in interdependent networks
Charles D. Brummitt, Raissa M. D’Souza, and E. A. Leicht  Maximum Matchings in Random Bipartite Graphs and the Space Utilization of Cuckoo Hash Tables
Alan Frieze, Pall Melsted
A nice overview of cuckoo hashing and related results is presented in this thesis
Random Bipartite Graphs and their Application to Cuckoo Hashing
R. Kutzelnigg  The Spread of EvidencePoor Medicine via Flawed SocialNetwork Analysis
R. Lyons
[Of course in order to be able to understand the critique you also need to read the referred work of Christakis and Fowler]
Note
You are not obliged to pick one of the aforementioned papers. You can choose a paper of your own preference as long as it is related to the content of the class. Some conferences and journals where you can search for more papers follow.
 ACM Conference on Electronic Commerce (EC)
 KDD
 WWW
 WSDM
 ESA
 ICALP
 SODA
 Random structures and algorithms (RSA)
 Combinatorics, Probability and Computing (CPC)
 Internet Mathematics