Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914671204761600 |
|---|---|
| author | Bläsius, Thomas Cohen, Sarel Fischbeck, Philipp Friedrich, Tobias Krejca, Martin S. |
| author_facet | Bläsius, Thomas Cohen, Sarel Fischbeck, Philipp Friedrich, Tobias Krejca, Martin S. |
| contents | Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive.
We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erdős-Rényi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_05534 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation Bläsius, Thomas Cohen, Sarel Fischbeck, Philipp Friedrich, Tobias Krejca, Martin S. Social and Information Networks Data Structures and Algorithms Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive. We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erdős-Rényi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations. |
| title | Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation |
| topic | Social and Information Networks Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.05534 |