T-79.7003

Graphs and Networks

Graphs and Networks

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 in more than one category.

- 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 - 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 - 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 - 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 - 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. - 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. - 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 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 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 - 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]

- ACM Conference on Electronic Commerce (EC)
- KDD
- WWW
- WSDM
- ESA
- ICALP
- SODA
- Random structures and algorithms (RSA)
- Combinatorics, Probability and Computing (CPC)
- Internet Mathematics