David Eppstein - Publications

Publications with Emma S. Spiro

• The h-index of a graph and its application to dynamic subgraph statistics.
  D. Eppstein and E. S. Spiro.
  arXiv:0904.3741.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada.
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 278–289.
  J. Graph Algorithms and Applications 16 (2): 543–567, 2012.

  We define the h-index of a graph to be the maximum h such that the graph has h vertices each of which has degree at least h. We show that the h-index, and a partition of the graph into high and low degree vertices, may be maintained in constant time per update. Based on this technique, we show how to maintain the number of triangles in a dynamic graph in time O(h) per update; this problem is motivated by Markov Chain Monte Caro simulation of the Exponential Random Graph Model used for simulation of social networks. We also prove bounds on the h-index for scale-free graphs and investigate the behavior of the h-index on a corpus of real social networks.

  (Slides)