Quick detection of high-degree entities in large directed networks

K. Avrachenkov, Nelli Litvak, L. Ostroumova Prokhorenkova, E. Suyargulova

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)
76 Downloads (Pure)


In this paper we address the problem of quick detection of high-degree entities in large online social networks. Practical importance of this problem is attested by a large number of companies that continuously collect and update statistics about popular entities, usually using the degree of an entity as an approximation of its popularity. We suggest a simple, efficient, and easy to implement two-stage randomized algorithm that provides highly accurate solutions to this problem. For instance, our algorithm needs only one thousand API requests in order to find the top-100 most followed users, with more than 90% precision, in the online social network Twitter with approximately a billion of registered users. Our algorithm significantly outperforms existing methods and serves many different purposes such as finding the most popular users or the most popular interest groups in social networks. An important contribution of this work is the analysis of the proposed algorithm using Extreme Value Theory — a branch of probability that studies extreme events and properties of largest order statistics in random samples. Using this theory we derive an accurate prediction for the algorithm’s performance and show that the number of API requests for finding the top-k most popular entities is sublinear in the number of entities. Moreover, we formally show that the high variability of the entities, expressed through heavy-tailed distributions, is the reason for the algorithm’s efficiency. We quantify this phenomenon in a rigorous mathematical way.
Original languageUndefined
Title of host publicationIEEE International Conference on Data Mining (ICDM 2014)
Place of PublicationUSA
PublisherIEEE Computer Society
Number of pages10
ISBN (Print)978-1-4799-4303-6
Publication statusPublished - 14 Dec 2014
EventIEEE International Conference on Data Mining, ICDM 2014 - Shenzhen, China
Duration: 14 Dec 201417 Dec 2014

Publication series

PublisherIEEE Computer Society
ISSN (Print)1550-4786


ConferenceIEEE International Conference on Data Mining, ICDM 2014
Other14-17 December 2014


  • IR-95323
  • EWI-25881
  • METIS-312530

Cite this