Local clustering via approximate heat kernel PageRank with subgraph sampling

Abstract Graph clustering, a fundamental technique in network science for understanding structures in complex systems, presents inherent problems. Though studied extensively in the literature, graph clustering in large systems remains particularly challenging because massive graphs incur a prohibiti...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Zhenqi Lu, Johan Wahlström, Arye Nehorai
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/55d4c7abc1664b2aad71f02ed7131d26
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:55d4c7abc1664b2aad71f02ed7131d26
record_format	dspace
spelling	oai:doaj.org-article:55d4c7abc1664b2aad71f02ed7131d262021-12-02T18:49:33ZLocal clustering via approximate heat kernel PageRank with subgraph sampling10.1038/s41598-021-95250-w2045-2322https://doaj.org/article/55d4c7abc1664b2aad71f02ed7131d262021-08-01T00:00:00Zhttps://doi.org/10.1038/s41598-021-95250-whttps://doaj.org/toc/2045-2322Abstract Graph clustering, a fundamental technique in network science for understanding structures in complex systems, presents inherent problems. Though studied extensively in the literature, graph clustering in large systems remains particularly challenging because massive graphs incur a prohibitively large computational load. The heat kernel PageRank provides a quantitative ranking of nodes, and a local cluster can be efficiently found by performing a sweep over the heat kernel PageRank vector. But computing an exact heat kernel PageRank vector may be expensive, and approximate algorithms are often used instead. Most approximate algorithms compute the heat kernel PageRank vector on the whole graph, and thus are dependent on global structures. In this paper, we present an algorithm for approximating the heat kernel PageRank on a local subgraph. Moreover, we show that the number of computations required by the proposed algorithm is sublinear in terms of the expected size of the local cluster of interest, and that it provides a good approximation of the heat kernel PageRank, with approximation errors bounded by a probabilistic guarantee. Numerical experiments verify that the local clustering algorithm using our approximate heat kernel PageRank achieves state-of-the-art performance.Zhenqi LuJohan WahlströmArye NehoraiNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 11, Iss 1, Pp 1-19 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Zhenqi Lu Johan Wahlström Arye Nehorai Local clustering via approximate heat kernel PageRank with subgraph sampling
description	Abstract Graph clustering, a fundamental technique in network science for understanding structures in complex systems, presents inherent problems. Though studied extensively in the literature, graph clustering in large systems remains particularly challenging because massive graphs incur a prohibitively large computational load. The heat kernel PageRank provides a quantitative ranking of nodes, and a local cluster can be efficiently found by performing a sweep over the heat kernel PageRank vector. But computing an exact heat kernel PageRank vector may be expensive, and approximate algorithms are often used instead. Most approximate algorithms compute the heat kernel PageRank vector on the whole graph, and thus are dependent on global structures. In this paper, we present an algorithm for approximating the heat kernel PageRank on a local subgraph. Moreover, we show that the number of computations required by the proposed algorithm is sublinear in terms of the expected size of the local cluster of interest, and that it provides a good approximation of the heat kernel PageRank, with approximation errors bounded by a probabilistic guarantee. Numerical experiments verify that the local clustering algorithm using our approximate heat kernel PageRank achieves state-of-the-art performance.
format	article
author	Zhenqi Lu Johan Wahlström Arye Nehorai
author_facet	Zhenqi Lu Johan Wahlström Arye Nehorai
author_sort	Zhenqi Lu
title	Local clustering via approximate heat kernel PageRank with subgraph sampling
title_short	Local clustering via approximate heat kernel PageRank with subgraph sampling
title_full	Local clustering via approximate heat kernel PageRank with subgraph sampling
title_fullStr	Local clustering via approximate heat kernel PageRank with subgraph sampling
title_full_unstemmed	Local clustering via approximate heat kernel PageRank with subgraph sampling
title_sort	local clustering via approximate heat kernel pagerank with subgraph sampling
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/55d4c7abc1664b2aad71f02ed7131d26
work_keys_str_mv	AT zhenqilu localclusteringviaapproximateheatkernelpagerankwithsubgraphsampling AT johanwahlstrom localclusteringviaapproximateheatkernelpagerankwithsubgraphsampling AT aryenehorai localclusteringviaapproximateheatkernelpagerankwithsubgraphsampling
_version_	1718377560641896448

Local clustering via approximate heat kernel PageRank with subgraph sampling

Ejemplares similares