Clustering Vertex-Weighted Graphs by Spectral Methods

Spectral techniques are often used to partition the set of vertices of a graph, or to form clusters. They are based on the Laplacian matrix. These techniques allow easily to integrate weights on the edges. In this work, we introduce a <i>p</i>-Laplacian, or a generalized Laplacian matrix...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Juan-Luis García-Zapata, Clara Grácio
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	clustering partitioning Laplacian graph vertex-weighted graph Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/c7d3a8b84b244797b620fbfb5420e7e8
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:c7d3a8b84b244797b620fbfb5420e7e8
record_format	dspace
spelling	oai:doaj.org-article:c7d3a8b84b244797b620fbfb5420e7e82021-11-25T18:16:27ZClustering Vertex-Weighted Graphs by Spectral Methods10.3390/math92228412227-7390https://doaj.org/article/c7d3a8b84b244797b620fbfb5420e7e82021-11-01T00:00:00Zhttps://www.mdpi.com/2227-7390/9/22/2841https://doaj.org/toc/2227-7390Spectral techniques are often used to partition the set of vertices of a graph, or to form clusters. They are based on the Laplacian matrix. These techniques allow easily to integrate weights on the edges. In this work, we introduce a <i>p</i>-Laplacian, or a generalized Laplacian matrix with potential, which also allows us to take into account weights on the vertices. These vertex weights are independent of the edge weights. In this way, we can cluster with the importance of vertices, assigning more weight to some vertices than to others, not considering only the number of vertices. We also provide some bounds, similar to those of Chegeer, for the value of the minimal cut cost with weights at the vertices, as a function of the first non-zero eigenvalue of the <i>p</i>-Laplacian (an analog of the Fiedler eigenvalue).Juan-Luis García-ZapataClara GrácioMDPI AGarticleclusteringpartitioningLaplacian graphvertex-weighted graphMathematicsQA1-939ENMathematics, Vol 9, Iss 2841, p 2841 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	clustering partitioning Laplacian graph vertex-weighted graph Mathematics QA1-939
spellingShingle	clustering partitioning Laplacian graph vertex-weighted graph Mathematics QA1-939 Juan-Luis García-Zapata Clara Grácio Clustering Vertex-Weighted Graphs by Spectral Methods
description	Spectral techniques are often used to partition the set of vertices of a graph, or to form clusters. They are based on the Laplacian matrix. These techniques allow easily to integrate weights on the edges. In this work, we introduce a <i>p</i>-Laplacian, or a generalized Laplacian matrix with potential, which also allows us to take into account weights on the vertices. These vertex weights are independent of the edge weights. In this way, we can cluster with the importance of vertices, assigning more weight to some vertices than to others, not considering only the number of vertices. We also provide some bounds, similar to those of Chegeer, for the value of the minimal cut cost with weights at the vertices, as a function of the first non-zero eigenvalue of the <i>p</i>-Laplacian (an analog of the Fiedler eigenvalue).
format	article
author	Juan-Luis García-Zapata Clara Grácio
author_facet	Juan-Luis García-Zapata Clara Grácio
author_sort	Juan-Luis García-Zapata
title	Clustering Vertex-Weighted Graphs by Spectral Methods
title_short	Clustering Vertex-Weighted Graphs by Spectral Methods
title_full	Clustering Vertex-Weighted Graphs by Spectral Methods
title_fullStr	Clustering Vertex-Weighted Graphs by Spectral Methods
title_full_unstemmed	Clustering Vertex-Weighted Graphs by Spectral Methods
title_sort	clustering vertex-weighted graphs by spectral methods
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/c7d3a8b84b244797b620fbfb5420e7e8
work_keys_str_mv	AT juanluisgarciazapata clusteringvertexweightedgraphsbyspectralmethods AT claragracio clusteringvertexweightedgraphsbyspectralmethods
_version_	1718411405127843840

Clustering Vertex-Weighted Graphs by Spectral Methods

Ejemplares similares