Implementation of efficient algorithms for network statistics

• Grant number: 21/10289-4
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: October 01, 2021
• End date: September 30, 2022
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: André Fujita
• Grantee: Christyan Ossamu Namikuchi
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 18/21934-5 - Network statistics: theory, methods, and applications, AP.TEM

Abstract

One of the bottlenecks of the methods for network statistics is the high computational cost to compute the spectral distribution (methods for parameter estimation, model selection, and comparison tests, for instance, are based on the spectral distribution of the graph) (Fujita et al., 2016; Takahashi et al., 2012). Currently, to estimate the spectral distribution of the graph, we compute all the eigenvalues of the adjacency matrix of the graph. However, this approach is very limited in the context of big graphs (even whether they are sparse). The purpose of this project is to implement efficient algorithms for network statistics. This scientific initiation project is related to sub-project 2.2.4 of the main document. The specific goals of this project are:1. To optimize the estimation of the spectral distribution of graphs.2. To implement in R, the algorithms to test/compare graphs that are not based on the spectral distribution. (AU)