{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T02:26:28Z","timestamp":1775701588444,"version":"3.50.1"},"reference-count":29,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T00:00:00Z","timestamp":1613001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003030","name":"Ag\u00e8ncia de Gesti\u00f3 d'Ajuts Universitaris i de Recerca","doi-asserted-by":"publisher","award":["2020 FI_B 00495"],"award-info":[{"award-number":["2020 FI_B 00495"]}],"id":[{"id":"10.13039\/501100003030","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003329","name":"Ministerio de Econom\u00eda y Competitividad","doi-asserted-by":"publisher","award":["PID2019-104958RB-C41"],"award-info":[{"award-number":["PID2019-104958RB-C41"]}],"id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>This paper presents the benefits of using the random-walk normalized Laplacian matrix as a graph-shift operator and defines the frequencies of a graph by the eigenvalues of this matrix. A criterion to order these frequencies is proposed based on the Euclidean distance between a graph signal and its shifted version with the transition matrix as shift operator. Further, the frequencies of a periodic graph built through the repeated concatenation of a basic graph are studied. We show that when a graph is replicated, the graph frequency domain is interpolated by an upsampling factor equal to the number of replicas of the basic graph, similarly to the effect of zero-padding in digital signal processing.<\/jats:p>","DOI":"10.3390\/s21041275","type":"journal-article","created":{"date-parts":[[2021,2,12]],"date-time":"2021-02-12T16:12:10Z","timestamp":1613146330000},"page":"1275","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Random-Walk Laplacian for Frequency Analysis in Periodic Graphs"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4976-1313","authenticated-orcid":false,"given":"Rachid","family":"Boukrab","sequence":"first","affiliation":[{"name":"SPCOM Group, Universitat Polit\u00e8cnica de Catalunya-Barcelona Tech, 08034 Barcelona, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7087-7014","authenticated-orcid":false,"given":"Alba","family":"Pag\u00e8s-Zamora","sequence":"additional","affiliation":[{"name":"SPCOM Group, Universitat Polit\u00e8cnica de Catalunya-Barcelona Tech, 08034 Barcelona, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1644","DOI":"10.1109\/TSP.2013.2238935","article-title":"Discrete Signal Processing on Graphs","volume":"61","author":"Sandryhaila","year":"2013","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1109\/MSP.2012.2235192","article-title":"The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains","volume":"30","author":"Shuman","year":"2013","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Wagner, R.S., Baraniuk, R.G., Du, S., Johnson, D.B., and Cohen, A. (2006, January 19\u201321). An Architecture for Distributed Wavelet Analysis and Processing in Sensor Networks. Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN \u201906), Nashville, TN, USA.","DOI":"10.1145\/1127777.1127816"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Ciancio, A., Pattem, S., Ortega, A., and Krishnamachari, B. (2006, January 19\u201321). Energy-Efficient Data Representation and Routing for Wireless Sensor Networks Based on a Distributed Wavelet Compression Algorithm. Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN \u201906), Nashville, TN, USA.","DOI":"10.1145\/1127777.1127824"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1038\/nrn3214","article-title":"The economy of brain network organization","volume":"13","author":"Bullmore","year":"2012","journal-title":"Nat. Rev. Neurosci."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Sporns, O. (2010). Networks of the Brain, MIT Press.","DOI":"10.7551\/mitpress\/8476.001.0001"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Tian, D., Mansour, H., Knyazev, A., and Vetro, A. (2014, January 14\u201318). Chebyshev and conjugate gradient filters for graph image denoising. Proceedings of the 2014 IEEE International Conference on Multimedia and Expo Workshops (ICMEW), Chengdu, China.","DOI":"10.1109\/ICMEW.2014.6890711"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Pang, J., Cheung, G., Ortega, A., and Au, O.C. (2015, January 19\u201324). Optimal graph laplacian regularization for natural image denoising. Proceedings of the 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), South Brisbane, QLD, Australia.","DOI":"10.1109\/ICASSP.2015.7178380"},{"key":"ref_9","unstructured":"Kipf, T.N., and Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv."},{"key":"ref_10","unstructured":"Bruna, J., Zaremba, W., Szlam, A., and LeCun, Y. (2013). Spectral networks and locally connected networks on graphs. arXiv."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.acha.2010.04.005","article-title":"Wavelets on graphs via spectral graph theory","volume":"30","author":"Hammond","year":"2011","journal-title":"Appl. Comput. Harmonic Anal."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Saito, N. (2018, January 10\u201313). How Can We Naturally Order and Organize Graph Laplacian Eigenvectors?. Proceedings of the 2018 IEEE Statistical Signal Processing Workshop (SSP), Freiburg, Germany.","DOI":"10.1109\/SSP.2018.8450808"},{"key":"ref_13","unstructured":"Bamieh, B. (2018). Discovering the Fourier Transform: A Tutorial on Circulant Matrices Circular Convolution and the DFT. arXiv."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3042","DOI":"10.1109\/TSP.2014.2321121","article-title":"Discrete Signal Processing on Graphs: Frequency Analysis","volume":"62","author":"Sandryhaila","year":"2014","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_15","first-page":"871","article-title":"The Laplacian spectrum of graphs","volume":"Volume 2","author":"Mohar","year":"1991","journal-title":"Graph Theory, Combinatorics, and Applications"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0024-3795(94)90486-3","article-title":"Laplacian matrices of graphs: A survey","volume":"197","author":"Merris","year":"1994","journal-title":"Linear Algebra Appl."},{"key":"ref_17","unstructured":"Chung, F.R., and Graham, F.C. (1997). Spectral Graph Theory, American Mathematical Soc.. Number 92."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1109\/MSP.2019.2929832","article-title":"Understanding the Basis of Graph Signal Processing via an Intuitive Example-Driven Approach [Lecture Notes]","volume":"36","author":"Stankovic","year":"2019","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"6303","DOI":"10.1109\/TSP.2017.2752689","article-title":"On the Shift Operator, Graph Frequency, and Optimal Filtering in Graph Signal Processing","volume":"65","author":"Gavili","year":"2017","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_20","first-page":"1325","article-title":"Graph Laplacians and their convergence on random neighborhood graphs","volume":"8","author":"Hein","year":"2007","journal-title":"J. Mach. Learn. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/s11263-008-0159-z","article-title":"Local and nonlocal discrete regularization on weighted graphs for image and mesh processing","volume":"84","author":"Bougleux","year":"2009","journal-title":"Int. J. Comput. Vis."},{"key":"ref_22","unstructured":"Zhou, D., and Sch\u00f6lkopf, B. (2004, January 4\u20138). A regularization framework for learning from graph data. Proceedings of the ICML 2004 Workshop on Statistical Relational Learning and Its Connections to Other Fields (SRL 2004), Banff, AB, Canada."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Smola, A.J., and Kondor, R. (2003). Kernels and regularization on graphs. Learning Theory and Kernel Machines, Springer.","DOI":"10.1007\/978-3-540-45167-9_12"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Zhou, D., and Sch\u00f6lkopf, B. (2005). Regularization on discrete spaces. Joint Pattern Recognition Symposium, Springer.","DOI":"10.1007\/11550518_45"},{"key":"ref_25","unstructured":"Kurras, S. (2018). Variants of the Graph Laplacian with Applications in Machine Learning, Gesellschaft f\u00fcr Informatik eV."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"4972","DOI":"10.1073\/pnas.0709247105","article-title":"From time series to complex networks: The visibility graph","volume":"105","author":"Lacasa","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1090\/S0002-9939-1962-0133816-6","article-title":"The Kronecker product of graphs","volume":"13","author":"Weichsel","year":"1962","journal-title":"Proc. Am. Math. Soc."},{"key":"ref_28","unstructured":"Perraudin, N., Paratte, J., Shuman, D., Martin, L., Kalofolias, V., Vandergheynst, P., and Hammond, D.K. (2014). GSPBOX: A toolbox for signal processing on graphs. arXiv."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Tremblay, N., Gon\u00e7alves, P., and Borgnat, P. (2018). Design of graph filters and filterbanks. Cooperative and Graph Signal Processing, Elsevier.","DOI":"10.1016\/B978-0-12-813677-5.00011-0"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1275\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:22:44Z","timestamp":1760160164000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,11]]},"references-count":29,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["s21041275"],"URL":"https:\/\/doi.org\/10.3390\/s21041275","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,11]]}}}