Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25420
Titel: Algorithmic building blocks for relationship analysis over large graphs
Sonstige Titel: Algorithmische Bausteine zur Analyse von Beziehungen in großen Graphen
Verfasser: Seufert, Stephan
Sprache: Englisch
Erscheinungsjahr: 2015
SWD-Schlagwörter: Graph
Graphentheorie
Soziales Netzwerk
Pfad <Graphentheorie>
Kürzester-Weg-Problem
Freie Schlagwörter: graphs
graph algorithm
shortest-path problem
social networks
graph analysis
knowledge graph
DDC-Sachgruppe: 004 Informatik
Dokumentart : Dissertation
Kurzfassung: Over the last decade, large-scale graph datasets with millions of vertices and edges have emerged in many diverse problem domains. Notable examples include online social networks, the Web graph, or knowledge graphs connecting semantically typed entities. An important problem in this setting lies in the analysis of the relationships between the contained vertices, in order to gain insights into the structure and dynamics of the modeled interactions. In this work, we develop efficient and scalable algorithms for three important problems in relationship analysis and make the following contributions: - We present the FERRARI index structure to quickly probe a graph for the existence of an (indirect) relationship between two designated query vertices, based on an adaptive compression of the transitive closure of the graph. - In order to quickly assess the relationship strength for a given pair of vertices as well as computing the corresponding paths, we present the PathSketch index structure for the fast approximation of shortest paths in large graphs. Our work extends a previously proposed prototype in several ways, including efficient index construction, compact index size, and faster query processing. - We present the ESPRESSO algorithm for characterizing the relationship between two sets of entities in a knowledge graph. This algorithm is based on the identification of important events from the interaction history of the entities of interest. These events are subsequently expanded into coherent subgraphs, corresponding to characteristic topics describing the relationship. We provide extensive experimental evaluations for each of the methods, demonstrating the efficiency of the individual algorithms as well as their usefulness for facilitating effective analysis of relationships in large graphs.
Im Laufe des letzten Jahrzehnts hat die Modellierung von direkt sowie indirekt verknüpften Entitäten in Form von Graphen – wie z. B. von Personen in sozialen Netzwerken oder semantisch annotierten Konzepten in Wissensbasen – eine wichtige Rolle in vielen Geschäfts- und Forschungsfragestellungen eingenommen. Der Umfang der in dieser Form modellierten Daten liegt in vielen Fällen in der Größenordnung von Millionen von Entitäten und Verknüpfungen. Ein wichtiges und vielversprechendes Problemfeld in diesem Bereich ist die effiziente und effektive Analyse der (indirekten) Beziehungen zwischen benutzerspezifizierten Entitäten, um Erkenntnisse über die Struktur und Dynamik der modellierten Interaktionen zu erhalten. In dieser Arbeit betrachten wir drei fundamentale Fragestellungen in der Analyse von Beziehungen in graphstrukturierten Daten und stellen die folgenden Beiträge vor: • Erreichbarkeitsanalyse befasst sich mit der effizienten (d. h. in Echtzeit ausführbaren) Überprüfung des Graphen auf die Existenz einer möglichen Beziehung zwischen zwei Entitäten. In dieser Arbeit stellen wir den Ferrari-Algorithmus zur schnellen Verarbeitung dieser Analysevariante vor, basierend auf einer adaptiven Form der Kompression der transitiven Hülle des Graphen. • Wir stellen die PathSketch Indexstruktur vor, ein System zur schnellen Approximation der Stärke einer Beziehung zwischen zwei Entitäten, sowie der Identifikation eines oder mehrerer zugehörigen Pfade. Das in dieser Arbeit vorgestellte System erweitert einen vorausgehend publizierten Prototyp hinsichtlich effizienter Durchführung des Indexaufbaus, Repräsentation der Indexeinträge sowie schnellerer Anfragebearbeitung. • Für die semantisch tiefergreifende Analyse von graphstrukturierten Wissensbasen stellen wir den Espresso-Algorithmus zur Charakterisierung der Beziehungen zwischen zwei Mengen von Entitäten vor. Espresso basiert auf der Identifikation wichtiger Ereignisse, welche anschliessend zu dem Lösungskonzept der dichten Teilgraphen erweitert werden. Diese Strukturen entspre- chen maßgeblichen Themenbereichen, die zur Beschreibung der wechselseitigen Beziehungen dienen. Die Effizienz und der praktische Nutzen der genannten Algorithmen und Ansätze werden in umfangreichen Experimenten evaluiert.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-61833
hdl:20.500.11880/25476
http://dx.doi.org/10.22028/D291-25420
Erstgutachter: Weikum, Gerhard
Tag der mündlichen Prüfung: 20-Apr-2015
SciDok-Publikation: 7-Jul-2015
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - Max-Planck-Institut für Informatik
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
thesis_final.pdf5,58 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.