Borassi, Michele (2016) Algorithms for metric properties of large realworld 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 realworld graphs. In the worstcase, 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 worstcase. 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 realworld 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 realworld 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 ChungLu model, and the NorrosReittu model. This way, our axiomatic analyses can be turned into averagecase analyses on these models, with no modification. This modular approach to averagecase complexity has two advantages: we can prove results in several models with a single worstcase 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/etheses/198 
Date Deposited:  21 Mar 2017 14:11 
URI:  http://etheses.imtlucca.it/id/eprint/198 
Actions (login required)
View Item 