Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting

Sepehr Assadi, Hoai An Nguyen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The h-index is a metric used to measure the impact of a user in a publication setting, such as a member of a social network with many highly liked posts or a researcher in an academic domain with many highly cited publications. Specifically, the h-index of a user is the largest integer h such that at least h publications of the user have at least h units of positive feedback. We design an algorithm that, given query access to the n publications of a user and each publication's corresponding positive feedback number, outputs a (1 ±ε)-approximation of the h-index of this user with probability at least 1 - δ in time O(n·lnε2(1·h/δ)), where h is the actual h-index which is unknown to the algorithm a-priori. We then design a novel lower bound technique that allows us to prove that this bound is in fact asymptotically optimal for this problem in all parameters n, h, ε, and δ. Our work is one of the first in sublinear time algorithms that addresses obtaining asymptotically optimal bounds, especially in terms of the error and confidence parameters. As such, we focus on designing novel techniques for this task. In particular, our lower bound technique seems quite general - to showcase this, we also use our approach to prove an asymptotically optimal lower bound for the problem of estimating the number of triangles in a graph in sublinear time, which now is also optimal in the error and confidence parameters. This latter result improves upon prior lower bounds of Eden, Levi, Ron, and Seshadhri (FOCS'15) for this problem, as well as multiple follow-up works that extended this lower bound to other subgraph counting problems.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022
EditorsAmit Chakrabarti, Chaitanya Swamy
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772495
DOIs
StatePublished - Sep 1 2022
Event25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022 - Virtual, Urbana-Champaign, United States
Duration: Sep 19 2022Sep 21 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume245
ISSN (Print)1868-8969

Conference

Conference25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022
Country/TerritoryUnited States
CityVirtual, Urbana-Champaign
Period9/19/229/21/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Sublinear time algorithms
  • asymptotically optimal bounds
  • h-index
  • lower bounds
  • subgraph counting

Fingerprint

Dive into the research topics of 'Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting'. Together they form a unique fingerprint.

Cite this