Graph generation with preserved properties

Abstract

The increasing size of real-world networks and the lack of publicly available datasets due to security and user privacy concerns has increased the demand for graph generators. Developing graph generators could facilitate researchers in analysing network's properties and underlying structure. More accurately, a request towards designing synthetic generator applicable to arbitrary graphs, which also scales up to massive datasets, is made. Such model could eventually be further extended to produce graphs of multiple size aiming to predict how those will conceivably evolve in the future. Having acquired synthetic networks, we could then measure multiple metrics in order to understand a graph's structure and properties. However, current graph generators are only capable of matching a fraction of real-world graph properties, are not suitable for different types of networks, do not scale up for large datasets or a mixture of the preceding. The main goal of this thesis is to take a deeper look in how well state-of-the-art graph generators preserve real-world graphs and their properties. Answers to the following questions are to be investigated: How well can a generation model capture a certain property? Is the model reliable in generating real-world networks from different domains? Can any similarities be found between the properties of synthetically generated and real-world graphs? Can a generator potentially produce graphs with adaptable properties, e.g. multiple times larger graph? Detailed analyses of existing graph generators and approach to try to combine or extend them to be able to generate graphs with similar to real-world networks properties are the head focus of this work. After investigating several generation models, we focused our attention on Darwini. Because to the best of our knowledge, it is only the second approach making an effort to concomitantly match the explicitly provided degree and clustering properties. In addition, no work aiming at questioning the model's ability has been found motivating us to thoroughly analyse the algorithm. Besides assessments we contributed to this topic by extending the algorithm with two methods aiming to predict how the structure of a certain network would look like in the future. Darwini along with our proposed extensions have been implemented in the GAME framework to analyse and compare the properties of arbitrary graphs. As we have shown in the results, Darwini lacks the ability of reproducing graphs with notable degree difference of neighbour elements in the distribution series and missing vital links connecting multiple components with one another. However, distributing vertices across several groups could address the issue and particularly improve the overall results.

Die zunehmende Größe realer Netzwerke und der Mangel an öffentlich zugänglichen Datensätzen aufgrund von Sicherheits- und Datenschutzbedenken der Benutzer hat die Nachfrage nach Graphgeneratoren erhöht. Die Entwicklung von Graphgeneratoren könnte Forschern die Analyse der Eigenschaften und der zugrunde liegenden Struktur von Netzwerken erleichtern. Genauer gesagt, wird eine Forderung nach dem Entwurf eines synthetischen Generators gestellt, der auf beliebige Graphen anwendbar ist und auch auf große Datensätze skaliert. Ein solches Modell könnte schließlich erweitert werden, um Graphen unterschiedlicher Größe zu erzeugen, mit dem Ziel vorherzusagen, wie sich diese in Zukunft entwickeln werden. Nach der Erfassung synthetischer Netzwerke könnten wir dann mehrere Metriken messen, um die Struktur und die Eigenschaften eines Graphen zu verstehen. Aktuelle Graphgeneratoren sind jedoch nur in der Lage, einen Bruchteil der realen Grapheigenschaften abzubilden, sind nicht für verschiedene Arten von Netzwerken geeignet, skalieren nicht für große Datensätze oder eine Mischung aus den Vorangegangenen. Das Hauptziel dieser Arbeit ist es, einen tieferen Blick darauf zu werfen, wie gut moderne Graphgeneratoren reale Graphen und deren Eigenschaften erhalten. Es sollen Antworten auf die folgenden Fragen untersucht werden: Wie gut kann ein Generierungsmodell eine bestimmte Eigenschaft erfassen? Ist das Modell zuverlässig bei der Generierung realer Netzwerke aus verschiedenen Domänen? Lassen sich Ähnlichkeiten zwischen den Eigenschaften von synthetisch erzeugten und realen Graphen feststellen? Kann ein Generator potentiell Graphen mit anpassbaren Eigenschaften erzeugen, z.B. mehrfach größere Graphen? Detaillierte Analysen bestehender Graphgeneratoren und der Versuch, diese zu kombinieren oder zu erweitern, um Graphen mit ähnlichen Eigenschaften wie in realen Netzwerken erzeugen zu können, sind der Hauptfokus dieser Arbeit. Nach der Untersuchung mehrerer Generierungsmodelle haben wir unsere Aufmerksamkeit auf Darwini gerichtet. Denn unseres Wissens nach ist es erst der zweite Ansatz, der sich bemüht, die explizit angegebenen Grad- und Clustereigenschaften gleichzeitig zu erfüllen. Außerdem wurde keine Arbeit gefunden, die darauf abzielt, die Fähigkeit des Modells zu hinterfragen, was uns dazu motivierte, den Algorithmus gründlich zu analysieren. Neben Einschätzungen haben wir zu diesem Thema beigetragen, indem wir den Algorithmus um zwei Methoden erweitert haben, die darauf abzielen, vorherzusagen, wie die Struktur eines bestimmten Netzwerks in der Zukunft aussehen würde. Darwini wurde zusammen mit den von uns vorgeschlagenen Erweiterungen in das GAME- Framework implementiert, um die Eigenschaften beliebiger Graphen zu analysieren und zu vergleichen. Wie wir in den Ergebnissen gezeigt haben, fehlt Darwini die Fähigkeit, Graphen mit nennenswerten Gradunterschieden von Nachbarelementen in der Verteilungsreihe und fehlenden wichtige Verbindungen, die mehrere Komponenten miteinander verbinden, zu reproduzieren. Die Verteilung von Knoten auf mehrere Gruppen könnte dieses Problem jedoch beheben und insbesondere die Gesamtergebnisse verbessern.