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 Scale-free 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

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

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

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. Gomez-Rodriguez, 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

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.

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 Degree-based Vertex Partitioning 
    Mihail N. Kolountzakis, Gary L. Miller, CET, Richard Peng
  • Counting Triangles in Data Streams 
    L. Buriol, G. Frahling, S. Leonardi, A. Marchetti-Spaccamela, 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.

Dense subgraphs and graph partitioning

• • A Local Algorithm for Finding Well-Connected 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

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

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

Various

• On the Bias of Traceroute Sampling: or, Power-Law 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. Tahbaz-Salehi
• A Random Graph Model of Multi-Hospital 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 Evidence-Poor Medicine via Flawed Social-Network 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