Sampling methods for network comparison

Network comparison is a fundamental task in the analysis of complex systems, yet it poses substantial computational challenges when applied to large-scale graphs. This thesis investigates the trade-off between computational efficiency and topological fidelity by analysing the impact of network sampling on alignment-free comparison metrics. Focusing on static, unweighted networks, the performance of several sampling strategies is evaluated, ranging from simple random node selection to exploration-based techniques with graph induction, with the aim of preserving local structural properties captured by the Egodist framework. From a methodological perspective, the study first shows that the Euclidean distance between discretised cumulative distribution functions provides a more robust measure of structural similarity than the commonly used Kolmogorov–Smirnov statistic. An extensive experimental analysis on synthetic networks generated by Erdős–Rényi, Barabási–Albert, and Geometric Random Graph models then demonstrates that, while Random Walk with Induction achieves the highest fidelity in preserving local topology, even simpler approaches such as Node Sampling can remain effective for macroscopic classification tasks. The results indicate that, when network classes are clearly distinct, high classification accuracy ($\mathrm{AUPR} \approx 1.0$) can be achieved even with basic sampling strategies and at sampling fractions as low as 20\%, leading to a substantial reduction in computational cost. In contrast, in scenarios characterised by subtle structural differences, induction-based sampling strategies become necessary to retain sufficient discriminative power. Overall, this work provides practical guidelines for selecting appropriate sampling techniques, showing that large-scale network comparison can be made computationally tractable without compromising analytical rigour.

Il confronto tra reti complesse rappresenta un problema fondamentale in numerosi ambiti scientifici e tecnologici, ma pone rilevanti sfide computazionali quando applicato a grafi di grandi dimensioni. Questa tesi analizza il compromesso tra efficienza computazionale e fedeltà topologica, investigando l’impatto delle tecniche di campionamento di rete su misure di confronto alignment-free. L’analisi si concentra su reti statiche e non pesate e valuta le prestazioni di diverse strategie di campionamento, che spaziano da approcci casuali, come il Node Sampling e l’Edge Sampling con Induzione, a tecniche di esplorazione basate su Random Walk con Induzione, con l’obiettivo di preservare le proprietà strutturali locali catturate dal framework Egodist. Dal punto di vista metodologico, lo studio mostra che la distanza euclidea tra distribuzioni cumulative discretizzate fornisce una misura di similarità strutturale più robusta rispetto alla statistica di Kolmogorov–Smirnov, risultando meno sensibile a disallineamenti. Un’ampia analisi sperimentale su reti sintetiche generate mediante modelli di Erdős–Rényi, Barabási–Albert e grafi geometrici casuali evidenzia che, sebbene il Random Walk con Induzione garantisca la maggiore fedeltà nella preservazione della topologia locale, anche strategie di campionamento meno sofisticate possono risultare sufficienti per affrontare compiti di classificazione a livello macroscopico. I risultati mostrano che, in scenari caratterizzati da classi di rete nettamente distinguibili, è possibile ottenere elevate prestazioni di classificazione anche con frazioni di campionamento ridotte, con una conseguente significativa riduzione del costo computazionale. Al contrario, in contesti più complessi, caratterizzati da differenze strutturali sottili tra le classi, diventa necessario ricorrere a strategie di campionamento con induzione per mantenere un adeguato potere discriminante. Nel complesso, questo lavoro fornisce indicazioni pratiche per la selezione di tecniche di campionamento appropriate, dimostrando che il confronto tra reti su larga scala può essere reso computazionalmente sostenibile senza compromettere il rigore analitico.