On the Tensor Approximation of Watts–strogatz Networks

Small-world networks are characterized by the existence, on average, of shortest paths between any arbitrary pair of nodes with only a few edges. In order to preserve the local clustering while permitting the existence of the small-world phenomenon, Watts and Strogatz introduced their celebrated network model (Nature, 1998), exemplifying what they observed in different types of networks, such as the neural network of C. elegans, the power grid network, or the collaboration network in cinema.

As the number of data increases, the networks and matrices that model it also do so, which makes it increasingly expensive to manipulate them. Recent work has shown the efficiency of tensor-based structures when performing, for example, matrix products, reducing the number of operations performed.

In the present work, we want to approximate the representative matrices of the Watts–Strogatz networks using tensor methods and compare the accuracy and the computational cost involved in operating with the original matrices and the matrices written in the approximate tensor form.