Error-Correcting Decoders for Communities in Networks

Autor:	Bathina, Krishna C., Radicchi, Filippo
Rok vydání:	2019
Předmět:	Physics - Physics and Society Computer Science - Social and Information Networks
Druh dokumentu:	Working Paper
Popis:	As recent work demonstrated, the task of identifying communities in networks can be considered analogous to the classical problem of decoding messages transmitted along a noisy channel. We leverage this analogy to develop a community detection method directly inspired by a standard and widely-used decoding technique. We further simplify the algorithm to reduce the time complexity from quadratic to linear. We test the performance of the original and reduced versions of the algorithm on artificial benchmarks with pre-imposed community structure, and on real networks with annotated community structure. Results of our systematic analysis indicate that the proposed techniques are able to provide satisfactory results. Comment: 8 pages, 5 figures, 2 tables
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1902.00896 Zobrazit plný text záznamu View this record from Arxiv