Quick Detection of High-degree Entities in Large Directed Networks

Abstract : 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 for this problem. For instance, our algorithm needs only one thousand API requests in order to find the top-100 most followed users in Twitter, a network with approximately a billion of registered users, with more than 90% precision. 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. We show that the complexity of the algorithm is sublinear in the network size, and that high efficiency is achieved in networks with high variability among the entities, expressed through heavy-tailed distributions.
Type de document :
Communication dans un congrès
ICDM 2014 - IEEE International Conference on Data Mining, Dec 2014, Shenzhen, China. pp.20 - 29 2014, 〈http://icdm2014.sfu.ca/program_advance_program.html〉. 〈10.1109/ICDM.2014.95〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01096353
Contributeur : Konstantin Avrachenkov <>
Soumis le : mercredi 17 décembre 2014 - 12:33:23
Dernière modification le : samedi 27 janvier 2018 - 01:31:41

Lien texte intégral

Identifiants

Collections

Citation

Konstantin Avrachenkov, Nelly Litvak, Liudmila Ostroumova, Euvgenia Suyargulova. Quick Detection of High-degree Entities in Large Directed Networks. ICDM 2014 - IEEE International Conference on Data Mining, Dec 2014, Shenzhen, China. pp.20 - 29 2014, 〈http://icdm2014.sfu.ca/program_advance_program.html〉. 〈10.1109/ICDM.2014.95〉. 〈hal-01096353〉

Partager

Métriques

Consultations de la notice

207