Clustering Vertex-Weighted Graphs by Spectral Methods

Juan-Luis García-Zapata and Clara Grácio
Additional contact information
Juan-Luis García-Zapata: Departamento de Matemáticas, Universidad de Extremadura, 10003 Cáceres, Spain
Clara Grácio: Departamento de Matematica, Universidad de Évora, 7004-516 Évora, Portugal

Mathematics, 2021, vol. 9, issue 22, 1-12

Abstract: 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 p -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 p -Laplacian (an analog of the Fiedler eigenvalue).

Keywords: clustering; partitioning; Laplacian graph; vertex-weighted graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/22/2841/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/22/2841/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:22:p:2841-:d:675505

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().