Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 15261719
DOI: 10.7155/jgaa.00273 The hIndex of a Graph and its Application to Dynamic Subgraph Statistics David Eppstein and Emma S. Spiro Vol. 16, no. 2, pp. 543567, 2012. Regular paper Abstract We describe a data structure that maintains the number of triangles in a dynamic undirected graph, subject to insertions and deletions of edges and of degreezero vertices. More generally it can be used to maintain the number of copies of each possible threevertex subgraph in time O(h) per update, where h is the hindex of the graph, the maximum number such that the graph contains h vertices of degree at least h. We also show how to maintain the hindex itself, and a collection of h highdegree vertices in the graph, in constant time per update. Our data structure has applications in social network analysis using the exponential random graph model (ERGM); its bound of O(h) time per edge is never worse than the Θ(√m) time per edge necessary to list all triangles in a static graph, and is strictly better for graphs obeying a power law degree distribution. In order to better understand the behavior of the hindex statistic and its implications for the performance of our algorithms, we also study the behavior of the hindex on a set of 136 realworld networks.

Submitted: December 2011. Accepted: August 2012. Final: August 2012. Published: August 2012. Communicated by Susanne Albers 
Journal of Graph Algorithms and Applications 