Detection of Small-World Networks
Using the Spectral Test and the Tracy-Widom Distribution
E.K. Smit (TU Delft - Electrical Engineering, Mathematics and Computer Science)
N. Parolya – Mentor (TU Delft - Statistics)
Y.M. Blanter – Mentor (TU Delft - QN/Blanter Group)
S.W.H. Eijt – Graduation committee member (TU Delft - RST/Energy Materials)
J.L.A. Dubbeldam – Mentor (TU Delft - Mathematical Physics)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Since graphs represent many real-world networks, understanding their mathematical properties is essential to analyze, modify, and predict their behavior. To characterize these properties, one must first identify the type of graph under study — a task that is not always straightforward. This paper examines one such model, the Watts–Strogatz small-world network, and investigates how well it can be distinguished from the classical Erdős–Rényi random graph. This is because a Watts–Strogatz network canbe seen as an interpolation between a completely structured graph and a completely random graph.
Two statistical tests are considered: the Spectral Test, as presented by Cai et al. (2017), and a new test based on the Tracy–Widom distribution. These tests are applied to controlled data with known parameters, allowing their accuracy to be quantitatively evaluated. Both tests exhibit comparable power; however, only the Tracy–Widom Test maintains a controlled significance level 𝛼, making it the more reliable and preferable choice.