{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:31:03Z","timestamp":1760236263877,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"22","license":[{"start":{"date-parts":[[2021,11,9]],"date-time":"2021-11-09T00:00:00Z","timestamp":1636416000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Government of Extremadura","award":["IB20040"],"award-info":[{"award-number":["IB20040"]}]},{"name":"Spanish Ministerio de Ciencia e Innovaci\u00f3n","award":["PID2019-110315RB-I00"],"award-info":[{"award-number":["PID2019-110315RB-I00"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics"],"abstract":"<jats:p>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).<\/jats:p>","DOI":"10.3390\/math9222841","type":"journal-article","created":{"date-parts":[[2021,11,9]],"date-time":"2021-11-09T21:39:07Z","timestamp":1636493947000},"page":"2841","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Clustering Vertex-Weighted Graphs by Spectral Methods"],"prefix":"10.3390","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1419-1672","authenticated-orcid":false,"given":"Juan-Luis","family":"Garc\u00eda-Zapata","sequence":"first","affiliation":[{"name":"Departamento de Matem\u00e1ticas, Universidad de Extremadura, 10003 C\u00e1ceres, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0397-5669","authenticated-orcid":false,"given":"Clara","family":"Gr\u00e1cio","sequence":"additional","affiliation":[{"name":"Departamento de Matematica, Universidad de \u00c9vora, 7004-516 \u00c9vora, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cosrev.2007.05.001","article-title":"Survey: Graph Clustering","volume":"1","author":"Schaeffer","year":"2007","journal-title":"Comput. Sci. Rev."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1272","DOI":"10.1137\/19M1290607","article-title":"Generalized K-Core Percolation in Networks with Community Structure","volume":"80","author":"Shang","year":"2020","journal-title":"SIAM J. Appl. Math."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Chung, F.R. (1997). Spectral Graph Theory, American Mathematical Soc.. CBMS.","DOI":"10.1090\/cbms\/092"},{"key":"ref_4","unstructured":"Shewchuk, J.R. (2016). Allow Me to Introduce Spectral and Isoperimetric Graph Partitioning, University of California Berkeley. Technical Report."},{"key":"ref_5","unstructured":"Ng, A.Y., Jordan, M.I., and Weiss, Y. (2002). Advances in Neural Information Processing Systems 14, MIT press. (NIPS 2001)."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/s41109-021-00390-7","article-title":"Historia Augusta Authorship: An Approach based on Measurements of Complex Networks","volume":"6","author":"Martins","year":"2021","journal-title":"Appl. Netw. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"072032","DOI":"10.1088\/1757-899X\/768\/7\/072032","article-title":"Weighted Laplacian Method and Its Theoretical Applications","volume":"Volume 768","author":"Xu","year":"2020","journal-title":"IOP Conference Series: Materials Science and Engineering 2020"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Carretero, J., Jeannot, E., and Zomaya, A. (2019). Ultrascale Computing Systems, Institution of Engineering and Technology.","DOI":"10.1049\/PBPC024E"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Berman, A., and Plemmons, R.J. (1994). Nonnegative Matrices in the Mathematical Sciences, SIAM.","DOI":"10.1137\/1.9781611971262"},{"key":"ref_10","unstructured":"Cvetkovic, D.M., Rowlinson, P., and Simic, S. (2010). An Introduction to the Theory of Graph Spectra, Cambridge University Press."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Beineke, L.W., Wilson, R.J., and Cameron, P.J. (2004). Topics in Algebraic Graph Theory, Cambridge University Press. Encyclopedia of Mathematics and Its Applications.","DOI":"10.1017\/CBO9780511529993"},{"key":"ref_12","unstructured":"Papadimitriou, C.H., and Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity, Dover Publications."},{"key":"ref_13","unstructured":"Lancaster, P., and Tismenetsky, M. (1985). The Theory of Matrices: With Applications, Academic Press."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Horn, R.A., and Johnson, C.R. (2012). Matrix Analysis, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9781139020411"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/j.laa.2006.07.020","article-title":"Spectral partitioning works: Planar graphs and finite element meshes","volume":"421","author":"Spielman","year":"2007","journal-title":"Linear Algebra Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0095-8956(89)90029-4","article-title":"Isoperimetric numbers of graphs","volume":"47","author":"Mohar","year":"1989","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Shang, Y. (2019). Isoperimetric Numbers of Randomly Perturbed Intersection Graphs. Symmetry, 11.","DOI":"10.3390\/sym11040452"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Boppana, R.B. (1987, January 12\u201314). Eigenvalues and graph bisection: An average-case analysis. Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), Los Angeles, CA, USA.","DOI":"10.1109\/SFCS.1987.22"},{"key":"ref_19","first-page":"13","article-title":"Laplacians of graphs and Cheeger\u2019s inequalities","volume":"2","author":"Chung","year":"1996","journal-title":"Comb. Paul Erdos Eighty"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"B\u0131y\u0131koglu, T., Leydold, J., and Stadler, P.F. (2007). Laplacian Eigenvectors of Graphs, Springer. Lecture Notes in Mathematics.","DOI":"10.1007\/978-3-540-73510-6"},{"key":"ref_21","unstructured":"Molitierno, J.J. (2012). Applications of Combinatorial Matrix Theory to Laplacian Matrices of Graphs, CRC Press."}],"container-title":["Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2227-7390\/9\/22\/2841\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:28:20Z","timestamp":1760167700000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2227-7390\/9\/22\/2841"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,9]]},"references-count":21,"journal-issue":{"issue":"22","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["math9222841"],"URL":"https:\/\/doi.org\/10.3390\/math9222841","relation":{},"ISSN":["2227-7390"],"issn-type":[{"type":"electronic","value":"2227-7390"}],"subject":[],"published":{"date-parts":[[2021,11,9]]}}}