Locating highly connected clusters in large networks with HyperLogLog counters

Research output: Working paper

Abstract

In this paper 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
PublisherarXiv.org
Publication statusPublished - 10 Jan 2021

Keywords

  • cs.SI
  • math.PR

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