Algorithms for analyzing and mining real-world graphs

Leiden Repository

Algorithms for analyzing and mining real-world graphs

Title: Algorithms for analyzing and mining real-world graphs
Author: Takes, Frank Willem
Publisher: Leiden Institute of Advanced Computer Science (LIACS), Faculty of Science, Leiden University
Issue Date: 2014-11-19
Keywords: Graphs
Algorithms
Networks
Social networks
Diameter
Distance
Shortest paths
Abstract: 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.
Description: Promotor: J.N. Kok, Co-Promotor: W.A. Kosters
With Summary in Dutch
Faculty: Faculteit der Wiskunde en Natuurwetenschappen
Citation: Takes, F.W., 2014, Doctoral Thesis, Leiden University
Series/Report no.: IPA Dissertation Series;2014-16
ISBN: 9789053359570
Sponsor: NWO
Handle: http://hdl.handle.net/1887/29764
 

Files in this item

Description Size View
application/pdf Full Text 4.778Mb View/Open
text/html Links to published articles Chapters 2, 5 and 8 25.93Kb View/Open
application/pdf Cover 336.3Kb View/Open
application/pdf Title Pages_Contents 310.0Kb View/Open
application/pdf Chapter 1 1.513Mb View/Open
application/pdf Part I: Chapter 2 542.4Kb View/Open
application/pdf Part I: Chapter 3 423.4Kb View/Open Full text at publisher site
application/pdf Part I: Chapter 4 226.2Kb View/Open
application/pdf Part I: Chapter 5 1.269Mb View/Open
application/pdf Part I: Chapter 6 274.9Kb View/Open
application/pdf Part II: Chapter 7 478.6Kb View/Open
application/pdf Part II: Chapter 8 233.1Kb View/Open
application/pdf Bibliography 154.0Kb View/Open
application/pdf Summary in Dutch 100.0Kb View/Open
application/pdf Curriculum Vitae_Publications_IPA Dissertations 147.8Kb View/Open
application/pdf Propositions 104.4Kb View/Open

This item appears in the following Collection(s)