Logo eprints

Algorithms for metric properties of large real-world networks from theory to practice and back

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]

Borassi_phdthesis.pdf - Published Version
Available under License Creative Commons Attribution No Derivatives.

Download (2MB) | Preview


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: 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 View Item