1/1
2 files

Fast community detection with graph sparsification

conference contribution
posted on 2020-01-01, 00:00 authored by Jesse LaeuchliJesse Laeuchli
A popular model for detecting community structure in large graphs is the Stochastic Block Model (SBM). The exact parameters to recover the community structure of a SBM has been well studied, and many methods have been proposed to recover a nodes’ community membership. A popular approach is to use spectral methods where the Graph Laplacian L of the given graph is created, and the Fiedler vector of the graph is found. This vector is then used to cluster nodes in the same community. While a robust method, it can be expensive to compute the Fiedler vector exactly. In this paper we examine the types of errors that can be tolerated using spectral methods while still recovering the communities. The two sources of error considered are: (i) dropping edges using different sparsification strategies; and (ii) inaccurately computing the eigenvectors. In this way, spectral clustering algorithms can be tuned to be far more efficient at detecting community structure for these community models.

History

Event

Knowledge Discovery and Data Mining. Conference (24th : 2020 : Singapore)

Volume

12084

Series

Knowledge Discovery and Data Mining Conference

Pagination

291 - 304

Publisher

Springer

Location

Singapore

Place of publication

Cham, Switzerland

Start date

2020-05-11

End date

2020-05-14

ISSN

0302-9743

eISSN

1611-3349

ISBN-13

9783030474256

Language

eng

Publication classification

E1 Full written paper - refereed

Editor/Contributor(s)

H Lauw, R Chi-Wing Wong, A Ntoulas, E Lim, S Ng, S Pan

Title of proceedings

PAKDD 2020 : Proceedings of the 24th Pacific-Asia Conference on Knowledge Discovery and Data Mining