Skip to main content
Register
Springer Professional
SEARCH
Menu 1 2 3 4
Top

Hint

Swipe to navigate through the chapters of this book

Published in:
Outline of a Formal Theory of Processes and Events, and Why GIScience Needs One Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Modelling Spatial Structures

Authors : Franz-Benjamin Mocnik, Andrew U. Frank

Published in: Spatial Information Theory

Publisher: Springer International Publishing

Login to get access
share
SHARE

Abstract

Data is spatial if it contains references to space. We can easily detect explicit references, for example coordinates, but we cannot detect whether data implicitly contains references to space, and whether it has properties of spatial data, if additional semantic information is missing. In this paper, we propose a graph model that meets typical properties of spatial data. We can, by the comparison of a graph representation of a data set to the graph model, decide whether the data set (implicitly or explicitly) has these typical properties of spatial data.
previous chapter Extracting Causal Rules from Spatio-Temporal Data
next chapter Strong Spatial Cognition
Footnotes
1
Time has a similar effect on data, because it can be modelled by one-dimensional Euclidean vector spaces.
 
2
The concept of scale invariance of a graph embedded in space should not be confused with the concept of scale-freeness of a graph, which is characterized by a power law distribution of the nodes’ edge degrees and hence by the invariance of the distribution’s shape under rescaling of the total number of edges.
 
3
This choice is made because it enables us to analytically compute some properties of the model. A variant of the model which introduces edges only with a certain probability is left to future work. As long as this effect is less dominant than other ones, we expect the properties of the proposed model and its variant to be similar.
 
4
A graph is called abstract if its nodes and edges contain no additional semantics. An abstract graph is, in particular, not embedded in space, and the nodes have no location.
 
5
The data is publicly accessible in the General Transit Feed Specification (GTFS) format [44].
 
6
A uniform distribution is a distribution where a point is placed at each location in space with the same probability.
 
7
Analytical results are much easier to derive when the number of nodes approaches infinity and hence only inner regions of the graphs have to be considered. The results can, however, be expected to approximately hold for finite graphs as well, when the number of nodes is sufficiently high.
 
8
There cannot exist any way to conclude whether a certain interpretation of a data set is spatial without knowledge of the interpretation, because there can exist spatial and non-spatial interpretations of the same data set.
 
9
The notation of density of a graph should not be confused with the notation of density of elements distributed in space.
 
10
A subgraph H of a graph G is called induced if every edge (p, q) of G with p and q nodes in H is also an edge of H.
 
11
Note that the estimate by density can slightly differ for each computation because it depends on the random choice of subgraphs.
 
12
The factor of 1 / 2 is chosen to visually illustrate how near data sets are depicted to the diagonal in Fig. 2. This choice is arbitrary and has no relevance for the fact that some data sets are depicted much nearer to the diagonal than others.
 
Literature
1.
Aldous, D.J., Shun, J.: Connected spatial networks over random points and a route-length statistic. Stat. Sci. 25(3), 275–288 (2010) CrossRefMathSciNetMATH
2.
Archdeacon, D., Bonnington, C.P., Little, C.H.C.: An algebraic characterization of planar graphs. J. Graph Theor. 19(2), 237–250 (1995) CrossRefMathSciNetMATH
3.
Barabási, A.L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., Vicsek, T.: Evolution of the social network of scientific collaborations. Phys. A 311, 590–614 (2002) CrossRefMathSciNetMATH
4.
5.
Barabási, A.L., Albert, R., Jeon, H.: Scale-free characteristics of random networks: the topology of the world-wide web. Phys. A 281(1–4), 69–77 (2000) CrossRef
6.
Barabási, A.L., Ravasz, E., Vicsek, T.: Deterministic scale-free networks. Phys. A 299(3–4), 559–564 (2001) CrossRefMATH
7.
Barthélemy, M.: Crossover from scale-free to spatial networks. Europhys. Lett. 63(6), 915–921 (2003) CrossRef
8.
9.
Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 322–331 (1990)
10.
Christaller, W.: Die zentralen Orte in Süddeutschland: Eine ökonomisch-geographische Untersuchung über die Gesetzmässigkeit der Verbreitung und Entwicklung der Siedlungen mit städtischen Funktionen. Fischer, Jena (1933)
11.
Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86, 243–266 (1991) CrossRefMathSciNetMATH
12.
Coleman, T.F., Moré, J.J.: Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal. 20(1), 187–209 (1983) CrossRefMathSciNetMATH
13.
Colizza, V., Pastor-Satorras, R., Vespignani, A.: Reaction-diffusion processes and metapopulation models in heterogeneous networks. Nature 3, 276–282 (2007)
14.
Denise, A., Vasconcellos, M., Welsh, D.J.A.: The random planar graph. Congressus Numerantium 113, 61–79 (1996) MathSciNetMATH
15.
Erdős, P., Rényi, A.: On random graphs I. Publicationes Math. Debrecen 6, 290–297 (1959) MATH
16.
European Commission: Commission Regulation (EU) No 97/2010 of 4 February 2010 entering a name in the register of traditional specialities guaranteed [Pizza Napoletana (TSG)]. Official J. Eur. Union 53(L34), 7–16 (2010)
17.
Franklin, C.: An introduction to geographic information systems: linking maps to databases. Database 15(2), 12–21 (1992) MathSciNet
18.
de Fraysseix, H., Rosenstiehl, P.: A depth-first-search characterization of planarity. Ann. Discret. Math. 13, 75–80 (1982) MATHMathSciNet
19.
20.
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 47–57 (1984)
21.
Hahmann, S., Burghardt, D., Weber, B.: 80% of all information is geospatially referenced? Towards a research framework: using the semantic web for (in)validating this famous geo assertion. In: Proceedings of the 14th AGILE Conference on Geographic Information Science (2011)
22.
Hecht, B., Moxley, E.: Terabytes of Tobler: evaluating the first law in a massive, domain-neutral representation of world knowledge. In: Hornsby, K.S., Claramunt, C., Denis, M., Ligozat, G. (eds.) COSIT 2009. LNCS, vol. 5756, pp. 88–105. Springer, Heidelberg (2009) CrossRef
23.
Holland, P.W., Leinhardt, S.: An exponential family of probability distributions for directed graphs. J. Am. Stat. Assoc. 76(373), 33–50 (1981) CrossRefMathSciNetMATH
24.
Hunter, D.R., Goodreau, S.M., Handcock, M.S.: Goodness of fit of social network models. J. Am. Stat. Assoc. 103(481), 248–258 (2008) CrossRefMathSciNetMATH
25.
Huson, M.L., Sen, A.: Broadcast scheduling algorithms for radio networks. In: Proceedings of the Military Communications Conference (MILCOM), vol. 2, pp. 647–651 (1995)
26.
Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., Barabási, A.L.: The large-scale organization of metabolic networks. Nature 407, 651–654 (2000) CrossRef
27.
Jespersen, S.N., Blumen, A.: Small-world networks: links with long-tailed distributions. Phys. Rev. E 62(5), 6270–6274 (2000) CrossRef
28.
Kalapala, V., Sanwalani, V., Clauset, A., Moore, C.: Scale invariance in road networks. Phys. Rev. E 73, 026130 (2006) CrossRef
29.
Kuhn, W.: Core concepts of spatial information for transdisciplinary research. Int. J. Geogr. Inf. Sci. 26(12), 2267–2276 (2012) CrossRef
30.
Kuratowski, C.: Sur le problème des courbes gauches en Topologie. Fundamenta Math. 15(1), 271–283 (1930) MathSciNetMATH
31.
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Predicting positive and negative links in online social networks. In: Proceedings of the 19th International Conference on World Wide Web (WWW), pp. 641–650 (2010)
32.
Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: Proceedings of the 28th Conference on Human Factors in Computing Systems (CHI), pp. 1361–1370 (2010)
33.
Lippai, I.: Water system design by optimization: Colorado Springs utilities case studies. In: Proceedings of the ASCE Pipeline Division Specialty Conference (Pipelines), pp. 1058–1070 (2005)
34.
Louf, R., Roth, C., Barthelemy, M.: Scaling in transportation networks. PLoS ONE 9(7), e102007 (2014) CrossRef
35.
MacLane, S.: A combinatorial condition for planar graphs. Fundamenta Math. 28(1), 22–31 (1937) MATH
36.
37.
38.
Mocnik, F.-B.: Modelling spatial information. In: Proceedings of the 1st Vienna Young Scientists Symposium (VSS) (2015)
39.
Ripeanu, M., Foster, I., Iamnitchi, A.: Mapping the Gnutella network: properties of large-scale peer-to-peer systems and implications for system design. IEEE Internet Comput. 6(1), 50–57 (2002) CrossRef
40.
Sala, A., Cao, L., Wilson, C., Zablit, R., Zheng, H., Zhao, B.Y.: Measurement-calibrated graph models for social network experiments. In: Proceedings of the 19th International World Wide Web Conference (WWW), pp. 861–870 (2010)
41.
42.
Soon-Hyung, Y., Jeong, H., Barabási, A.L.: Modeling the internet’s large-scale topology. Proc. Natl. Acad. Sci. U.S.A. 99(21), 13382–13386 (2002) CrossRef
43.
Tobler, W.R.: A computer movie simulating urban growth in the detroit region. Econ. Geogr. 46, 234–240 (1970) CrossRef
44.
45.
de Verdière, Y.C.: Sur un nouvel invariant des graphes et un critère de planarité. J. Comb. Theor. Ser. B 50(1), 11–21 (1990) CrossRefMATH
46.
47.
Walski, T.M., Brill, E.D., Gessler, J., Goulter, I.C.: Battle of the network models: epilogue. J. Water Resour. Plann. Manag. 113(2), 191–203 (1987) CrossRef
48.
Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393, 440–442 (1998) CrossRef
49.
Waxman, B.M.: Routing of multipoint connections. IEEE J. Sel. Areas Commun. 6(9), 1617–1622 (1988) CrossRef
50.
Whitney, H.: Non-separable and planar graphs. Proc. Nat. Acad. Sci. U.S.A. 17(2), 125–127 (1931) CrossRefMATH
51.
Xulvi-Brunet, R., Sokolov, I.M.: Evolving networks with disadvantaged long-range connections. Phys. Rev. E 66, 026118 (2002) CrossRef
52.
Zipf, G.K.: The hypothesis of the minimum equation as a unifying social principle: with attempted synthesis. Am. Sociol. Rev. 12(6), 627–650 (1947) CrossRef
Metadata
Title
Modelling Spatial Structures
Authors
Franz-Benjamin Mocnik
Andrew U. Frank
Copyright Year
2015
Book
Spatial Information Theory

Print ISBN: 978-3-319-23373-4

Electronic ISBN: 978-3-319-23374-1

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-23374-1_3

Premium Partner

Neuer Inhalt
    Image Credits