Top

previous chapter Extracting Causal Rules from Spatio-Temporal Data

next chapter Strong Spatial Cognition

Hint

Swipe to navigate through the chapters of this book

2015 | OriginalPaper | Chapter

Modelling Spatial Structures

Read first chapter

Authors: Franz-Benjamin Mocnik, Andrew U. Frank

Publisher: Springer International Publishing

Published in: Spatial Information Theory

» Get access to the full-text

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.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Time has a similar effect on data, because it can be modelled by one-dimensional Euclidean vector spaces.

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.

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.

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.

The data is publicly accessible in the General Transit Feed Specification (GTFS) format [ 44].

A uniform distribution is a distribution where a point is placed at each location in space with the same probability.

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.

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.

The notation of density of a graph should not be confused with the notation of density of elements distributed in space.

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.

Note that the estimate by density can slightly differ for each computation because it depends on the random choice of subgraphs.

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.

Aldous, D.J., Shun, J.: Connected spatial networks over random points and a route-length statistic. Stat. Sci. 25(3), 275–288 (2010) CrossRefMathSciNetMATH

Archdeacon, D., Bonnington, C.P., Little, C.H.C.: An algebraic characterization of planar graphs. J. Graph Theor. 19(2), 237–250 (1995) CrossRefMathSciNetMATH

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

Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999) CrossRefMathSciNetMATH

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

Barabási, A.L., Ravasz, E., Vicsek, T.: Deterministic scale-free networks. Phys. A 299(3–4), 559–564 (2001) CrossRefMATH

Barthélemy, M.: Crossover from scale-free to spatial networks. Europhys. Lett. 63(6), 915–921 (2003) CrossRef

Barthélemy, M.: Spatial networks. Phys. Rep. 499(1–3), 1–101 (2011) CrossRefMathSciNet

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.

Gilbert, E.N.: Random graphs. Ann. Math. Stat. 30(4), 1141–1144 (1959) CrossRefMATH

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.

McDiarmid, C.: Random graphs on surfaces. J. Comb. Theor. Ser. B 98(4), 778–797 (2008) CrossRefMathSciNetMATH

37.

McDiarmid, C., Steger, A., Welsh, D.J.A.: Random planar graphs. J. Comb. Theor. Ser. B 93(2), 187–205 (2005) CrossRefMathSciNetMATH

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.

Schnyder, W.: Planar graphs and poset dimension. Order 5(4), 323–343 (1989) CrossRefMathSciNetMATH

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.

Trafiklab: GTFS Sverige. https://www.trafiklab.se. Accessed 28 April 2013 (2013)

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.

Wagner, K.: Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114(1), 570–590 (1937) CrossRefMathSciNetMATH

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

Title

Modelling Spatial Structures

Book

Spatial Information Theory

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

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

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

DOI

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

Authors:

Franz-Benjamin Mocnik
Andrew U. Frank

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits