FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams

DOI10.1007/S10618-019-00630-6zbMATH Open1458.68283arXiv1611.06615OpenAlexW2554164694WikidataQ128015152 ScholiaQ128015152MaRDI QIDQ2218366FDOQ2218366

Yongsub Lim, Min-Soo Jung, U. Kang, Sunmin Lee

Publication date: 15 January 2021

Published in: Data Mining and Knowledge Discovery (Search for Journal in Brave)

Abstract: How can we accurately estimate local triangles for all nodes in simple and multigraph streams? Local triangle counting in a graph stream is one of the most fundamental tasks in graph mining with important applications including anomaly detection and social network analysis. Although there have been several local triangle counting methods in a graph stream, their estimation has a large variance which results in low accuracy, and they do not consider multigraph streams which have duplicate edges. In this paper, we propose FURL, an accurate local triangle counting method for simple and multigraph streams. FURL improves the accuracy by reducing a variance through biased estimation and handles duplicate edges for multigraph streams. Also, FURL handles a stream of any size by using a fixed amount of memory. Experimental results show that FURL outperforms the state-of-the-art method in accuracy and performs well in multigraph streams. In addition, we report interesting patterns discovered from real graphs by FURL, which include unusual local structures in a user communication network and a core-periphery structure in the Web.

Full work available at URL: https://arxiv.org/abs/1611.06615

zbMATH Keywords

edge samplinggraph streamlocal triangle counting

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Title not available (Why is that?)
• Random sampling with a reservoir
• Finding and counting given length cycles
• Main-memory triangle computations for very large (sparse (power-law)) graphs
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Computational Statistics
• Probabilistic counting algorithms for data base applications
• Min-wise independent permutations

Cited In (1)

• Title not available (Why is that?)

Uses Software

• DOULION

This page was built for publication: FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2218366)