Skip to main content
Top

Hint

Swipe to navigate through the chapters of this book

2015 | OriginalPaper | Chapter

Modelling Spatial Structures

Authors : Franz-Benjamin Mocnik, Andrew U. Frank

Published in: Spatial Information Theory

Publisher: Springer International Publishing

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.
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 (pq) 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.
go back to reference Aldous, D.J., Shun, J.: Connected spatial networks over random points and a route-length statistic. Stat. Sci. 25(3), 275–288 (2010) CrossRefMathSciNetMATH 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.
go back to reference Archdeacon, D., Bonnington, C.P., Little, C.H.C.: An algebraic characterization of planar graphs. J. Graph Theor. 19(2), 237–250 (1995) 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
3.
go back to reference 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., 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
5.
go back to reference 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., 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.
go back to reference Barabási, A.L., Ravasz, E., Vicsek, T.: Deterministic scale-free networks. Phys. A 299(3–4), 559–564 (2001) CrossRefMATH Barabási, A.L., Ravasz, E., Vicsek, T.: Deterministic scale-free networks. Phys. A 299(3–4), 559–564 (2001) CrossRefMATH
7.
go back to reference Barthélemy, M.: Crossover from scale-free to spatial networks. Europhys. Lett. 63(6), 915–921 (2003) CrossRef Barthélemy, M.: Crossover from scale-free to spatial networks. Europhys. Lett. 63(6), 915–921 (2003) CrossRef
9.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86, 243–266 (1991) CrossRefMathSciNetMATH Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86, 243–266 (1991) CrossRefMathSciNetMATH
12.
go back to reference 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 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.
go back to reference Colizza, V., Pastor-Satorras, R., Vespignani, A.: Reaction-diffusion processes and metapopulation models in heterogeneous networks. Nature 3, 276–282 (2007) Colizza, V., Pastor-Satorras, R., Vespignani, A.: Reaction-diffusion processes and metapopulation models in heterogeneous networks. Nature 3, 276–282 (2007)
14.
go back to reference Denise, A., Vasconcellos, M., Welsh, D.J.A.: The random planar graph. Congressus Numerantium 113, 61–79 (1996) MathSciNetMATH Denise, A., Vasconcellos, M., Welsh, D.J.A.: The random planar graph. Congressus Numerantium 113, 61–79 (1996) MathSciNetMATH
15.
go back to reference Erdős, P., Rényi, A.: On random graphs I. Publicationes Math. Debrecen 6, 290–297 (1959) MATH Erdős, P., Rényi, A.: On random graphs I. Publicationes Math. Debrecen 6, 290–297 (1959) MATH
16.
go back to reference 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) 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.
go back to reference Franklin, C.: An introduction to geographic information systems: linking maps to databases. Database 15(2), 12–21 (1992) MathSciNet Franklin, C.: An introduction to geographic information systems: linking maps to databases. Database 15(2), 12–21 (1992) MathSciNet
18.
go back to reference de Fraysseix, H., Rosenstiehl, P.: A depth-first-search characterization of planarity. Ann. Discret. Math. 13, 75–80 (1982) MATHMathSciNet de Fraysseix, H., Rosenstiehl, P.: A depth-first-search characterization of planarity. Ann. Discret. Math. 13, 75–80 (1982) MATHMathSciNet
20.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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 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.
go back to reference Holland, P.W., Leinhardt, S.: An exponential family of probability distributions for directed graphs. J. Am. Stat. Assoc. 76(373), 33–50 (1981) CrossRefMathSciNetMATH 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.
go back to reference 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 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.
go back to reference 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) 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.
go back to reference 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 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.
go back to reference Jespersen, S.N., Blumen, A.: Small-world networks: links with long-tailed distributions. Phys. Rev. E 62(5), 6270–6274 (2000) CrossRef Jespersen, S.N., Blumen, A.: Small-world networks: links with long-tailed distributions. Phys. Rev. E 62(5), 6270–6274 (2000) CrossRef
28.
go back to reference Kalapala, V., Sanwalani, V., Clauset, A., Moore, C.: Scale invariance in road networks. Phys. Rev. E 73, 026130 (2006) CrossRef Kalapala, V., Sanwalani, V., Clauset, A., Moore, C.: Scale invariance in road networks. Phys. Rev. E 73, 026130 (2006) CrossRef
29.
go back to reference Kuhn, W.: Core concepts of spatial information for transdisciplinary research. Int. J. Geogr. Inf. Sci. 26(12), 2267–2276 (2012) CrossRef Kuhn, W.: Core concepts of spatial information for transdisciplinary research. Int. J. Geogr. Inf. Sci. 26(12), 2267–2276 (2012) CrossRef
30.
go back to reference Kuratowski, C.: Sur le problème des courbes gauches en Topologie. Fundamenta Math. 15(1), 271–283 (1930) MathSciNetMATH Kuratowski, C.: Sur le problème des courbes gauches en Topologie. Fundamenta Math. 15(1), 271–283 (1930) MathSciNetMATH
31.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference 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) 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.
go back to reference Louf, R., Roth, C., Barthelemy, M.: Scaling in transportation networks. PLoS ONE 9(7), e102007 (2014) CrossRef Louf, R., Roth, C., Barthelemy, M.: Scaling in transportation networks. PLoS ONE 9(7), e102007 (2014) CrossRef
35.
go back to reference MacLane, S.: A combinatorial condition for planar graphs. Fundamenta Math. 28(1), 22–31 (1937) MATH MacLane, S.: A combinatorial condition for planar graphs. Fundamenta Math. 28(1), 22–31 (1937) MATH
38.
go back to reference Mocnik, F.-B.: Modelling spatial information. In: Proceedings of the 1st Vienna Young Scientists Symposium (VSS) (2015) Mocnik, F.-B.: Modelling spatial information. In: Proceedings of the 1st Vienna Young Scientists Symposium (VSS) (2015)
39.
go back to reference 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 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.
go back to reference 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) 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)
42.
go back to reference 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 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.
go back to reference Tobler, W.R.: A computer movie simulating urban growth in the detroit region. Econ. Geogr. 46, 234–240 (1970) CrossRef Tobler, W.R.: A computer movie simulating urban growth in the detroit region. Econ. Geogr. 46, 234–240 (1970) CrossRef
45.
go back to reference 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 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
47.
go back to reference 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 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.
go back to reference Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393, 440–442 (1998) CrossRef Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393, 440–442 (1998) CrossRef
49.
go back to reference Waxman, B.M.: Routing of multipoint connections. IEEE J. Sel. Areas Commun. 6(9), 1617–1622 (1988) CrossRef Waxman, B.M.: Routing of multipoint connections. IEEE J. Sel. Areas Commun. 6(9), 1617–1622 (1988) CrossRef
50.
go back to reference Whitney, H.: Non-separable and planar graphs. Proc. Nat. Acad. Sci. U.S.A. 17(2), 125–127 (1931) CrossRefMATH Whitney, H.: Non-separable and planar graphs. Proc. Nat. Acad. Sci. U.S.A. 17(2), 125–127 (1931) CrossRefMATH
51.
go back to reference Xulvi-Brunet, R., Sokolov, I.M.: Evolving networks with disadvantaged long-range connections. Phys. Rev. E 66, 026118 (2002) CrossRef Xulvi-Brunet, R., Sokolov, I.M.: Evolving networks with disadvantaged long-range connections. Phys. Rev. E 66, 026118 (2002) CrossRef
52.
go back to reference 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 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
DOI
https://doi.org/10.1007/978-3-319-23374-1_3

Premium Partner