A spectral distribution approximation algorithm for network time series

• Grant number: 24/09195-3
• Support Opportunities: Regular Research Grants
• Start date: January 01, 2025
• End date: December 31, 2026
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: André Fujita
• Grantee: André Fujita
• Principal researcher abroad: Peter Florian Stadler
• Institution abroad: Leipzig University, Germany
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 24/03261-4 - Advancements in Network Statistics: extensions to HPC and hypergraphs., AP.R

Abstract

Advancements in sensor technology have made dynamic, time-evolving network data, such as functional brain networks, the Internet of Things (IoT), and stock market trading networks, more readily available. Analyzing these networks often involves examining the network spectral distribution, which provides insights into the network's structure and serves as a framework for statistical analysis. However, calculating the network spectral distribution for each time point is computationally intensive, with standard methods requiring O(n3) time and O(n2) space complexity for dense adjacency matrices. Various approximation algorithms have been proposed to address this challenge, yet they remain insufficient for large-scale network time series analysis. This study aims to develop an "online" spectral distribution computation algorithm that leverages the previous network spectral distribution to compute the current time point's spectral distribution, thereby avoiding the need for full recalculations. Our approach involves decomposing the spectral distribution node-wise, facilitating efficient updates. Implementing this algorithm on GPUs using CUDA is expected to accelerate computations significantly. We aim to advance the network spectral distribution approximation field by continuing the collaboration between Prof. Stadler (Germany) and Prof. Fujita (Brazil) and involving junior scientists who will gain international research experience and training. (AU)