Proefschrift

Algorithms for analyzing and mining real-world graphs

Promotor: Prof.dr. J.N. Kok, Co-Promotor: W.A. Kosters

Auteur

F.W. Takes

Datum

19 november 2014

Links

Thesis in Leiden Repository

This thesis is about algorithms for analyzing large real-world graphs (or networks). Examples include (online) social networks, webgraphs, information networks, biological networks and scientific collaboration and citation networks. Although these graphs differ in terms of what kind of information the objects and relationships represent, it turns out that the structure of each these networks is surprisingly similar. For computer scientists, there is an obvious challenge to design efficient algorithms that allow large graphs to be processed and analyzed in a practical setting, facing the challenges of processing millions of nodes and billions of edges. Specifically, there is an opportunity to exploit the non-random structure of real-world graphs to efficiently compute or approximate various properties and measures that would be too hard to compute using traditional graph algorithms. Examples include computation of node-to-node distances and extreme distance measures such as the exact diameter and radius of a graph.

• algorithms
• diameter
• distance
• graphs
• networks
• shortest paths
• social networks