A Statistical Performance Analysis of Graph Clustering Algorithms

Pierre Miasnikof, Alexander Shestopaloff, Anthony J Bonner, Yuri Lawryshyn

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review


Measuring graph clustering quality remains an open problem. Here, we introduce three statistical measures to address the problem. We empirically explore their behavior under a number of stress test scenarios and compare it to the commonly used modularity and conductance. Our measures are robust, immune to resolution limit, easy to intuitively interpret and also have a formal statistical interpretation. Our empirical stress test results confirm that our measures compare favorably to the established ones. In particular, they are shown to be more responsive to graph structure, less sensitive to sample size and breakdowns during numerical implementation and less sensitive to uncertainty in connectivity. These features are especially important in the context of larger data sets or when the data may contain errors in the connectivity patterns.
Original languageEnglish
Title of host publicationAlgorithms and Models for the Web Graph
Subtitle of host publication15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings
EditorsAnthony Bonato, Pawel Pralat, Andrei Raigorodskii
PublisherSpringer Nature
ISBN (Electronic)978-3-319-92871-5
ISBN (Print)978-3-319-92870-8
Publication statusPublished - Jun 2018

Publication series

NameLecture Notes in Computer Science


Dive into the research topics of 'A Statistical Performance Analysis of Graph Clustering Algorithms'. Together they form a unique fingerprint.

Cite this