A scale-invariant spatial graph model

Abstract

Information wird räumlich genannt, wenn sie Referenzen zum Raum beinhaltet. Die vorliegende Dissertation zielt darauf ab, die Charakterisierung räumlicher Information auf ein strukturelles Level zu heben. Toblers erstes Gesetz der Geographie und die Skaleninvarianz werden weithin zur Charakterisierung räumlicher Information verwendet. Ihre formale Beschreibung basiert jedoch auf expliziten Referenzen zum Raum, was einer Verwendung für die strukturelle Charakterisierung räumlicher Information entgegensteht. Der Autor führt daher ein Graphenmodell ein, welches im Falle einer Einbettung des Graphen in einen Raum typische Eigenschaften räumlicher Information aufweist, d.h. unter anderem Toblers Gesetz befolgt und skaleninvariant ist. Das Graphenmodell weist die Auswirkungen dieser typischen Eigenschaften auf seine Struktur auch dann auf, wenn es als abstrakter Graph interpretiert wird. Daher ist es zur Diskussion dieser typischen Eigenschaften auf einem strukturellen Level geeignet. Ein Vergleich des Modells mit verschiedenen räumlichen und nicht-räumlichen Datensätzen in der vorliegenden Dissertation legt nahe, dass räumliche Datensätze durch eine gemeinsame Struktur gekennzeichnet sind, weil die betrachteten räumlichen Datensätze im Gegensatz zu den nicht-räumlichen Gemeinsamkeiten mit dem Modell aufweisen. Dies lässt das Konzept einer räumlichen Struktur sinnvoll erscheinen. Das eingeführte Modell ist ein Modell dieser räumlichen Struktur. Die Dimension des Raumes wirkt sich auf räumliche Information und somit auch auf die räumliche Struktur aus. Die Dissertation untersucht, wie die Eigenschaften des Modells, insbesondere im Falle einer Gleichverteilung der Knoten im Raum, von der Dimension des Raumes abhängen und zeigt, wie eine Schätzung der Dimension aus der räumlichen Struktur eines Datensatzes gefolgert werden kann. Die Ergebnisse der Dissertation, insbesondere das Konzept einer räumlichen Struktur und das Graphenmodell, stellen einen grundlegenden Beitrag für die Diskussion räumlicher Information auf einem strukturellen Level dar: Auf räumlichen Daten operierende Algorithmen können unter Berücksichtigung der räumlichen Struktur verbessert werden; eine statistische Evaluation von Überlegungen zu räumlichen Daten wird möglich, da das Graphenmodell beliebig viele Testdatensätze mit kontrollierbaren Eigenschaften generieren kann; und das Erkennen von räumlichen Strukturen sowie die Schätzung der Dimension und weiterer Parameter kann zum langfristigen Ziel beitragen, Daten mit unvollständiger oder fehlender Semantik zu verwenden.

Information is called spatial if it contains references to space. The thesis aims at lifting the characterization of spatial information to a structural level. Tobler's first law of geography and scale invariance are widely used to characterize spatial information, but their formal description is based on explicit references to space, which prevents them from being used in the structural characterization of spatial information. To overcome this problem, the author proposes a graph model that exposes, when embedded in space, typical properties of spatial information, amongst others Tobler's law and scale invariance. The graph model, considered as an abstract graph, still exposes the effect of these typical properties on the structure of the graph and can thus be used for the discussion of these typical properties at a structural level. A comparison of the proposed model to several spatial and non-spatial data sets in this thesis suggests that spatial data sets can be characterized by a common structure, because the considered spatial data sets expose structural similarities to the proposed model but the non-spatial data sets do not. This proves the concept of a spatial structure to be meaningful, and the proposed model to be a model of spatial structure. The dimension of space has an impact on spatial information, and thus also on the spatial structure. The thesis examines how the properties of the proposed graph model, in particular in case of a uniform distribution of nodes in space, depend on the dimension of space and shows how to estimate the dimension from the structure of a data set. The results of the thesis, in particular the concept of a spatial structure and the proposed graph model, are a fundamental contribution to the discussion of spatial information at a structural level: algorithms that operate on spatial data can be improved by paying attention to the spatial structure; a statistical evaluation of considerations about spatial data is rendered possible, because the graph model can generate arbitrarily many test data sets with controlled properties; and the detection of spatial structures as well as the estimation of the dimension and other parameters can contribute to the long-term goal of using data with incomplete or missing semantics.