Borassi, Michele (2016) Algorithms for metric properties of large real-world networks from theory to practice and back. Advisor: Crescenzi, Prof. Pierluigi. Coadvisor: De Nicola, Prof. Rocco . pp. 262. [IMT PhD Thesis]
|
Text
Borassi_phdthesis.pdf - Published Version Available under License Creative Commons Attribution No Derivatives. Download (2MB) | Preview |
Abstract
Motivated by complex networks analysis, we study algorithms that compute metric properties of real-world graphs. In the worst-case, we prove that, under reasonable assumptions, the trivial algorithms based on computing the distance between all pairs of nodes are almost optimal. Then, we try to overcome these bottlenecks by designing new algorithms that work surprisingly well in practice, even if they are not efficient in the worst-case. We propose new algorithms for the computation of the diameter, the radius, the closeness centrality, the betweenness centrality, and and the hyperbolicity: these algorithms are much faster than the textbook algorithms, when tested on real-world complex networks, and they also outperform similar approaches that were published in the literature. For example, to solve several problems, our algorithms are thousands, and even billions of times faster than the textbook algorithm, on standard inputs. However, the experimental results are not completely satisfactory from a theoretical point of view. In order to fill this gap, we develop an axiomatic framework where these algorithms can be evaluated and compared: we define some axioms, we show that real-world networks satisfy these axioms, and we prove that our algorithms are efficient if the input satisfies these axioms. This way, we obtain results that do not depend on the specific dataset used, and we highlight the main properties of the input that are exploited. A further confirmation of the validity of this approach is that the results obtained mirror very well the empirical results. Finally, we prove that the axioms are verified on realistic models of random graphs, such as the Configuration Model, the Chung-Lu model, and the Norros-Reittu model. This way, our axiomatic analyses can be turned into average-case analyses on these models, with no modification. This modular approach to average-case complexity has two advantages: we can prove results in several models with a single worst-case analysis, and we can validate the choice of the model by showing that the axioms used are verified in practice
| Item Type: | IMT PhD Thesis |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| PhD Course: | Computer Decision and System Science |
| Identification Number: | https://doi.org/10.6092/imtlucca/e-theses/198 |
| NBN Number: | urn:nbn:it:imtlucca-27226 |
| Date Deposited: | 21 Mar 2017 14:11 |
| URI: | http://e-theses.imtlucca.it/id/eprint/198 |
Actions (login required, only for staff repository)
 |
View Item |
