Computing triangle and open-wedge heavy-hitters in large networks

A. Pavan, P. Quint, S. Scott, N. V. Vinodchandran, J. Smith

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

Abstract

We formalize notions of triangle and open-wedge heavy-hitters in large networks. Intuitively, a node of a network G is a triangle heavy-hitter if it participates in relatively many triangles of G (analogously for open wedges). These notions have applications in social network analysis. We consider the triangle and open-wedge heavy-hitter problems: the computational problems of maintaining a set of nodes of a network that participate in many triangles and open wedges. We give sampling-based algorithms for these problems when the input network G comes as an edge stream. We prove theoretical guarantees on the quality of solutions, time and space complexity of these algorithms. This is the first work that studies the triangle and open-wedge heavy hitters problem on massive streaming networks. We evaluate the performance of our proposed algorithms by running on several real-world data sets. These experiments indicate that our algorithms efficiently detect heavy hitters while keeping both the false-positive and the false-negative errors very low.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE International Conference on Big Data, Big Data 2016
EditorsRonay Ak, George Karypis, Yinglong Xia, Xiaohua Tony Hu, Philip S. Yu, James Joshi, Lyle Ungar, Ling Liu, Aki-Hiro Sato, Toyotaro Suzumura, Sudarsan Rachuri, Rama Govindaraju, Weijia Xu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages998-1005
Number of pages8
ISBN (Electronic)9781467390040
DOIs
StatePublished - 2016
Event4th IEEE International Conference on Big Data, Big Data 2016 - Washington, United States
Duration: Dec 5 2016Dec 8 2016

Publication series

NameProceedings - 2016 IEEE International Conference on Big Data, Big Data 2016

Other

Other4th IEEE International Conference on Big Data, Big Data 2016
CountryUnited States
CityWashington
Period12/5/1612/8/16

Keywords

  • link and graph mining
  • social network analysis
  • stream data mining
  • triangle heavy hitters

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Computing triangle and open-wedge heavy-hitters in large networks'. Together they form a unique fingerprint.

  • Cite this

    Pavan, A., Quint, P., Scott, S., Vinodchandran, N. V., & Smith, J. (2016). Computing triangle and open-wedge heavy-hitters in large networks. In R. Ak, G. Karypis, Y. Xia, X. T. Hu, P. S. Yu, J. Joshi, L. Ungar, L. Liu, A-H. Sato, T. Suzumura, S. Rachuri, R. Govindaraju, & W. Xu (Eds.), Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016 (pp. 998-1005). [7840699] (Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2016.7840699