Models and algorithms for systematic network randomization

Stamm, Felix Ihno; Hoefer, Martin; Schaub, Michael Thomas

doi:44669

Models and algorithms for systematic network randomization

Stamm, Felix Ihno^RWTH*

2025

Verantwortlichkeitsangabevorgelegt von Felix Ihno Stamm, Master of Science

ImpressumAachen : RWTH Aachen University 2025

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2025

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Schaub, Michael Thomas (Thesis advisor)^RWTH* ; Hoefer, Martin (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2025-04-29

Online
DOI: 10.18154/RWTH-2025-05201
URL: https://publications.rwth-aachen.de/record/1012833/files/1012833.pdf

Einrichtungen

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Etablierte Darstellungsformen von Systemen, bei denen das paarweise Zusammenspiel von Komponenten bedeutsam ist, sind Netzwerke oder Graphen. Um die Robustheit von Analysen solcher Netzwerkdaten abzuschätzen, wäre es nützlich mehrfache Beobachtungen desselben Netzwerkes zu haben. In der Praxis stehen diese leider selten zur Verfügung und die Originaldaten werden zufällig verändert ("randomisiert'') um zusätzliche synthetische Beobachtungen zu erhalten. Solche systematischen Randomisierungsmethoden werden als Zufallsgraphen ("random graphs'') oder Zufallsgraphmodelle bezeichnet. Zu Beginn dieser Arbeit werden Zufallsgraphen verwendet, um die Verlässlichkeit der Ergebnisse von Netzwerkanalysen zu bewerten. Diese Zufallsgraphen dienen der Erzeugung systematischer Fehler. Simulationen solcher Fehler zeigen, dass Netzwerkanalysen relativ stark durch systematische Fehler beeinträchtigt werden können. Im weiteren Verlauf beschäftigt sich diese Arbeit mit Überlegungen zu Zufallsgraphen, die ein gegebenes Netzwerk auf verschiedenen Stufen imitieren können. Solche Modelle eignen sich besonders gut, um die Robustheit von Analysen abschätzen zu können, ohne dass konkrete Annahmen über die spezifisch zu erwartenden Abweichungen getroffen werden müssen. Die etablierten Zufallsgraphmodelle erweisen sich dafür eher ungeeignet, da sie vorhandene Strukturen in Netzwerken nur unzureichend wiedergeben oder sich ihre Anwendung in praktischen Simulationsstudien problematisch gestaltet. Vor diesem Hintergrund präsentiert diese Arbeit mit dem sogenannten "NeSt'' Modell ein Zufallsgraphenmodell, das die Netzwerkstruktur zuverlässig abbilden kann. Die Netzwerkstruktur wird dabei durch den "Color Refinement'' Algorithmus gemessen. Über einen Parameter d dieses Modells kann dann die Menge an Struktur, die erhalten bleiben soll, eingestellt werden. Simulationen und theoretische Betrachtungen zeigen, dass die Ähnlichkeit von Netzwerken, die mit dem ``NeSt'' Modell randomisiert wurden, zu einem Originalnetzwerk gut eingestellt werden kann. Während viele Prozesse sich gut durch statische Netzwerke beschreiben lassen, ist es für Prozesse wie z. B. die Ausbreitung von Krankheiten essentiell die temporal-kausale Abfolge zu beachten. Temporale Netzwerke ermöglichen eine solche Betrachtungsweise. Daher führt diese Arbeit eine Generalisierung des NeSt Modells für temporale Netzwerke ein. Es kann gezeigt werden, dass dieses "temporal NeSt'' relevante Strukturen von temporalen Netzwerken besser repliziert als andere verbreitete Randomisierungsmethoden. Randomisierung wird in der Regel für die Einschätzung der Robustheit von Analysen verwendet. Weiterhin kann Randomisierung auch dazu dienen, um genaue Rückschlüsse auf Originaldaten zu erschweren oder unmöglich zu gestalten. Dies ist besonders bedeutend, wenn Daten geteilt werden sollen, ohne dass dabei sensible personenbezogene Daten an die Öffentlichkeit gelangen. Ein mögliches Konzept, um die Privatsphäre beim Teilen von Netzwerkdaten zu wahren, ist "k-degree anonymity''. Um Netzwerkdaten auf diese Weise zu schützen sind mehre Teilschritte nötig. Ein Teilschritt hiervon ist bekannt als ``Univariate Microaggregation‘‘ und besteht darin zu einer Originalmenge eine ähnliche, anonymisierte Menge zu finden. Diese Arbeit präsentiert abschließend Algorithmen, die die nötige Laufzeit zur exakten Lösung des "Univariate Microaggregation'' Problems verringern.

Networks are an established tool to model data about entities and their pairwise relationships. For many applications, such as robustness assessment, it would be desirable to have multiple observations on the same network. Frequently though, only one measurement of a network is available and multiple synthetic observations are obtained by randomization. Systematic randomizations that replicate relevant structure of an observed network, are usually referred to as random graph models. Initially, this thesis considers network randomization as a means to assess the reliability of network analyses, in particular in the presence of systematic biases. Simulations on synthetic and real world data show that conclusions drawn from network analyses can be affected significantly if systematic biases are unaccounted for. When randomized networks should closely resemble a given network, established network models are of limited use. They are either rudimentary in their ability to preserve the rich structure of the network to be randomized or their use in simulation studies is limited as they are difficult to fit and sample. This thesis provides a network model that is well capable to replicate the meso-scale structure of a given graph and is easy to fit and sample. This NeSt model achieves this by preserving the d-hop neighborhood structure as measured by the color refinement procedure. The main parameter of the NeSt model, the depth d, allows to assert control over the amount of structure that is preserved. Simulations show that the samples from the NeSt model are similar as measured by many popular centrality measures. While many processes are well modeled using static networks, for processes such as spreading of pathogens the time order of events is essential. Temporal networks assign a timestamp to each interaction which allow them to model processes which rely on the time order of interactions ("causality structure''). This thesis proposes the temporal NeSt model that preserves the d-hop causality structure of a temporal network. Simulations show that the temporal NeSt model preserves essential properties of temporal networks better than other established temporal network randomization schemes. Instead of assessing robustness, randomization may also be used to intentionally decrease sensitivity of subsequent analyses. When (social) network data is shared, it is important to ensure that subsequent analyses cannot obtain sensitive information on contained individuals. This thesis considers two mechanisms to protect such information. First, a randomization based approach, so called (edge) differential privacy, is considered. It is shown, that differentially private network data is unlikely to be useful for subsequent consumers which questions previous results. For an alternative privacy concept, so called k-degree anonymity, it is essential to find an anonymous degree sequence. This task of minimizing the distance (the "cost'') of an alternative anonymized set of 1D points to an original set, under a minimum group / cluster size constraint, is known as univariate microaggregation (UM). This thesis discusses different requirements on the cost functions such that UM may be solved efficiently. Overall this thesis expands the toolbox of systematic network randomization by offering new versatile network models and investigating the use of randomization in two relevant applications.

OpenAccess:
PDF
(additional files)