@inproceedings{d47ed25f702a4571ab6f6136fd18260b,
title = "Computing triangle and open-wedge heavy-hitters in large networks",
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.",
keywords = "link and graph mining, social network analysis, stream data mining, triangle heavy hitters",
author = "A. Pavan and P. Quint and S. Scott and Vinodchandran, {N. V.} and J. Smith",
note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 4th IEEE International Conference on Big Data, Big Data 2016 ; Conference date: 05-12-2016 Through 08-12-2016",
year = "2016",
doi = "10.1109/BigData.2016.7840699",
language = "English (US)",
series = "Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "998--1005",
editor = "Ronay Ak and George Karypis and Yinglong Xia and Hu, {Xiaohua Tony} and Yu, {Philip S.} and James Joshi and Lyle Ungar and Ling Liu and Aki-Hiro Sato and Toyotaro Suzumura and Sudarsan Rachuri and Rama Govindaraju and Weijia Xu",
booktitle = "Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016",
}