Projects per year
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.
|Title of host publication||Algorithms and Models for the Web Graph|
|Subtitle of host publication||15th International Workshop, WAW 2018, Moscow, Russia, May 17-18, 2018, Proceedings|
|Editors||Anthony Bonato, Pawel Pralat, Andrei Raigorodskii|
|Publication status||Published - Jun 2018|
|Name||Lecture Notes in Computer Science|