Locating highly connected clusters in large networks with HyperLogLog counters

Lotte Weedage*, Nelly Litvak, Clara Stegehuis

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
65 Downloads (Pure)

Abstract

In this article, we introduce a new method to locate highly connected clusters in a network. Our proposed approach adapts the HyperBall algorithm to localize regions with a high density of small subgraph patterns in large graphs in a memory-efficient manner. We use this method to evaluate three measures of subgraph connectivity: conductance, the number of triangles and transitivity. We demonstrate that our algorithm, applied to these measures, helps to identify clustered regions in graphs and provides good seed sets for community detection algorithms such as PageRank-Nibble. We analytically obtain the performance guarantees of our new algorithms and demonstrate their effectiveness in a series of numerical experiments on synthetic and real-world networks.
Original languageEnglish
Article numbercnab023
JournalJournal of Complex Networks
Volume9
Issue number2
DOIs
Publication statusPublished - 29 Jul 2021

Keywords

  • UT-Hybrid-D

Fingerprint

Dive into the research topics of 'Locating highly connected clusters in large networks with HyperLogLog counters'. Together they form a unique fingerprint.

Cite this