Title: Algorithms for metric properties of large real-world networks from theory to practice and back
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
Publication Year: 2016
Publication Date: 2016-12-01
Language: en
Type: dissertation
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot