David Eppstein - Publications

Publications with Joseph Wang

• Fast approximation of centrality.
  D. Eppstein and J. Wang.
  arXiv:cs.DS/0009005.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 228–229.
  J. Graph Algorithms & Applications 8 (1): 39–45, 2004.

  We use random sampling to quickly estimate, for each vertex in a graph, the average distance to all other vertices.

  (SODA paper)

• A steady state model for graph power laws.
  D. Eppstein and J. Wang.
  2nd Int. Worksh. Web Dynamics, Honolulu, 2002.
  arXiv:cs.DM/0204001.

  We propose a random graph model that (empirically) appears to have a power law degree distribution. Unlike previous models, our model is based on a Markov process rather than incremental growth. We compare our model with others in its ability to predict web graph clustering behavior.