CSIS Discussion Paper #51

UNIFROM NETWORK TRANSFORMARION
FOR SPATIAL ANALYSISON A HETEROGENEOUS NETWORK

Atsuyuki Okabe
atsu@ua.t.u-tokyo.ac.jp
September 2002

Center for Spatial Information Science, University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan

2002/10/03

Abstract

This paper proposes a general method for analyzing the distribution of points on a‘heterogeneous’ network. First, the paper formulates a method that transforms a heterogeneous
network (i.e. a network in which a probability of a point being placed in a unit line segment on
the network varies according to the location of the unit line segment) into a homogeneous
network (i.e. a network in which a probability of a point being placed in a unit line segment on
the network is the same regardless of the location of the unit line segment). Second, the paper
proves that this transformed network can be geometrically realized on a two-dimensional space(plane). These results have very useful implications. First, a heterogeneous network can beeasily treated through transforming it into a homogeneous network. This contrasts to the factthat there is no method for transforming a heterogeneous plane into a homogeneous plane.
Second, any methods assuming a homogeneous network can be applied to the analysis on aheterogeneous network through the uniform network transformation. Hence, it is not necessary
to develop special methods for a heterogeneous network.

i2002/10/03

1. Introduction
We notice in the related literature (for example, King, 1969; Getis and Boots, 1976; Lewis,
1977; Bailey and Gatrell, 1995) that almost all quantitative methods for spatial analysis assume
that:i) space, S , is represented by two-dimensional space, i.e. a plane (Figure 1a),ii) distance in S is measured with Euclidean distance (the arrowed line in Figure 1a),iii) space S is homogeneous, i.e. the characteristics of a unit area in S are the same
regardless of the location of the unit area in S (the squares indicated by the broken lines
in Figure 1a); in terms of stochastic point processes, the probability of a point being placedin a unit area in S is the same regardless of the location of the unit area in S .

(a)

(b)

Figure 1: Convenience stores in Shibuya, Tokyo (a) on a plane with Euclidean distance and (b)on a street-network with the shortest-path distance.

When we analyze spatial phenomena in terms of the distribution of points, these assumptions
are not always acceptable. In particular, when we analyze spatial phenomena in a small urban
area, these assumptions are hard to accept (Berry, 2002).

For instance, consider the marketing

analysis of convenience stores in a downtown area (Figure 1b). Consumers go to stores on foot1

2002/10/03

or by car through streets (the arrowed line in Figure 1b), and convenience stores (the points in
Figure 1b) are located along streets. Consequently, it is more natural to assume that:i’) space S is represented by a network,ii’) distance in S is measured with the shortest-path distance.

Yet, almost all quantitative methods for spatial analysis assume i) and ii). There are two reasonsfor adopting these assumptions. First, mathematical treatment on a plane is simpler and more
tractable than that on a network. Second, most researchers seem to expect that a network spacewith the shortest-path distance can be approximated by a plane with Euclidean distance. This
expectation, however, is doubtful. An instructive example is shown in Figure 2a. Having seen
this distribution, probably nobody believes that the points are uniformly and randomly
distributed. But, this is true. Actually, as is seen in Figure 2b, the points (which are the same as
those in Figure 2a) are generated according to the uniformly random point process (the binomial
point process) on a network. In addition, an empirical study by Yamada and Thill (2002) showthat the conclusion obtained from the K-function method assuming a plane with Euclidean
distance is significantly different from that obtained from the K-function method assuming a
network with the shortest-path distance.

Figure 2: A distribution of points (a) on a plane and (b) on a network (the points are generated
by the binomial point process on a network).

2

2002/10/03

To overcome the limitations resulting from Assumptions i) and ii), several methods have beendeveloped under Assumptions i’) and ii’). For example, Okabe et al. (1995) formulate thenearest distance method on a network; Okabe and Yamada (2001) and Yamada and Thill (2002)
formulate the K-function and cross K-functions methods on a network; Miller (1994, 1996),
Okabe and Kitamura (1996), Morita et al. (2001) and Okabe and Okunuki (2001) formulate the
Huff model on a network.

In addition to Assumptions i) and ii), the last assumption, Assumption iii), is also problematic inpractice. Needless to say, the actual geographical plane is heterogeneous. For example, consider
the point process of convenience stores in a downtown. This process may be well examined byconsidering heterogeneity produced by uneven consumer (population) density. Thus Assumptioniii) is hardly acceptable when we examine the actual distribution of convenience stores in a
downtown. To overcome this limitation, a few theoretical methods are proposed in the related
literature, such as heterogeneous point processes (Diggle, 1983). However, these methods arestill hard to deal with actual geographical phenomena.

Fortunately, we have noticed that the above limitations can be overcome if a plane with the
Euclidean distance (Assumptions i) and ii) ) is replaced with a network with the shortest-path
distance (Assumptions i’) and ii’)). The objective of this paper is to show an easy method for
dealing with the distribution of points on a ‘heterogeneous network’. Roughly speaking, thismethod treats a ‘heterogeneous network’ by transforming it into a ‘homogeneous network’.
Once this transformation is done, we can apply any methods for spatial analysis on ahomogeneous network to spatial analysis on a heterogeneous network. We do not have todevelop special methods for a heterogeneous network.

2. The transformation from a heterogeneous network into a homogeneous network3

2002/10/03

The key concepts are, as often referred to in the above, a ‘homogeneous network’ anda‘heterogeneous network’ . To define them explicitly, let us consider a network, N , consistingof a set, L , of line segments (which may be curved) and a set, P , of nodes, satisfying that theline segments in L are connected (or crossed) only at the nodes in P , and that the end pointsof the line segments in L are the nodes in P .

For a network N , we define a homogeneous network as a network in which the characteristics
of a unit line segment in N are the same regardless of the location of the unit line segment in

N ; in terms of stochastic point processes, the probability of a point being placed in a unit line
segment in N is the same regardless of the location of the unit line segment in N . A
heterogeneous network is defined as a network that is not a homogenous network. Stated more
explicitly, a heterogeneous network is defined as a network in which the characteristics of a unit
line segment in N vary according to the location of the unit line segment in N ; in terms ofstochastic point processes, the probability of a point being placed in a unit line segment in N
varies according to the location of the unit line segment in N . The homogeneity or
heterogeneity is represented by a density function defined on N . The homogeneous network
has the uniform density function, and the heterogeneous network has a non-uniform density
function.

In actual analysis, we have to estimate a density function that represents a heterogeneous
network. Let us consider how to obtain this density function. Suppose that we want to analyze
the distribution of convenience stores in relation to the distribution of households. Owing torecent progress in GIS, we can easily obtain a digital map where stores and houses are
represented by polygons, and streets are represented by line segments (Bailey and Gatrell, 1995).
First, we obtain a representative point of a house by the center of the polygon representing thehouse (the white points in Figure 3). Second, we assign the representative point on the nearest
point on a network (the black points in Figure 3). We assume this point as the gate of a house4

2002/10/03

facing a street. Third, we count the number of assigned points for each link. Last, we obtain thehouse (household) density from the number of assigned points on a link divided by the length ofthe link. This procedure is carried out with the software developed by Okabe et al. (2002). Notethat in the above method, the density of households may differ from link to link, but it isconstant within each link. Alternatively, we may use a variable density within a link. Thisdensity function can be estimated by a non-parametric density estimation method using thepoints on a link obtained in the above procedure (Silverman, 1986).

Figure 3: Assignment of houses to the nearest points on a network.

To define a density function for a heterogeneous network mathematically, let Li (i = 1, K , n)be a link in L , and t be the length from an end node of Li to a point on Li along Li .
Then the density of an attribute (say, household density) is represented by the function

0 ≤ t ≤ ti , i = 1, K , n,f i (t ),where t i is the length of Li . Note that the density may be constant over Li as in the above
example (but different from link to link), or it may vary continuously over Li . We assume thatfor all i ,ti∫ f (t )dt ≥ a > 0,0i52002/10/03

where a is a positive constant. A clue to a method that transforms a heterogeneous network
into a homogeneous network is given by a transformation that is often used for generating
random variables in statistics (Freund, 1971). To state the transformation explicitly, let x be an
arbitrary random variable whose probability density has the value of f (x) . We transform thevariable x into y asx

y = ∫ f ( x)dx = F ( x).
−∞This transformation is called the probability integral transformation (Figure 4). Let g ( y ) be
the density function of the random variable y . Since the equation

dy dF ( x)== f ( x)dx
dx
holds, we haveg ( y ) = 1, 0 < y < 1,which is the uniform probability density function with the interval 0 < y < 1 . This derivationshows that any non-uniform probability density function is transformed into the uniform
probability density function through the probability integral transformation y = F (x). This fact
implies that random variables, x1 ,K, xn , that follow the non-uniform probability density
function f (x) (the black points on the horizontal axis in Figure 4) are equivalent totransformed random variables,

y1 = F ( x1 ), K , yn = F ( x n ) , that follow the uniform

probability density function g ( y ) (the black points on the vertical axis in Figure 4). Conversely,
random variables, y1 ,K, y n ,that follow the uniform probability density function g ( y ) areequivalent to transformed random variables, x1 = F −1 ( y1 ), K , xn = F −1 ( yn ) , that follow the62002/10/03

non-uniform probability density function f (x) , where x = F −1 ( y ) is the inverse function ofy = F (x) . Using this property, we can obtain random variables, x1 ,K, xn , that follow a
non-uniform probability density function f (x) by generating random variables y1 ,K, y nthat follow the uniform probability density function g ( y ) and transforming these randomvariables through x1 = F −1 ( y1 ), K , xn = F −1 ( yn ) .
y

y=F(x

f(x
x

Figure 4: The probability integral transformation.

We can utilize the idea of the probability integral transformation for transforming aheterogeneous network into a homogeneous network. To be explicit, for each link Li , wedefine the transformations = ∫ f i (t )dt = Fi (t ), i = 1, K , n.
t0

We consider a line L*i (that will correspond to Li ), and let s be the length from an end nodeof L*i to a point on L*i along L*i (Figure 5). We correspond Li to L*i in such a mannerthat a point at t on Li corresponds to the point s = F (t ) on L*i . As a result, the origin
node of Li (t = 0) corresponds to the origin node of L*i ( s = F (0) = 0) , and the other end
node of Li (t = t i ) corresponds to the other end node of L*i ( si = F (t i )) .

7

2002/10/03

Li*

Li
t

s=Fi(t)Figure 5: Transforming Li into L*i .

Let L* be the set of the resulting links L*1 ,K, L*n ,and P * be the set of nodes generated by

the end nodes of the links in L* (Figure 6b). Then the network N * consisting of the link set

L* and the node set P * is the uniform network in the sense that the density of a unit line
segment on the network is constant regardless of the location of the unit line segment on L*(Figure 6b). We call the transformation from the network N into the network N * theuniform network transformation.

L1G=1

L1*=

L 1=

L1*=1

L3=

(a)
Figure 6: Part of (a) N ,

L2G=

L2*=

L 2=

L3G=2

(b)

(c)

(b) N * and (c) N G (the numbers indicate the length of thelinks).

We make two important remarks. First, the geometrical forms of the links in L* are arbitrary.
Any form is acceptable as far as they are constructed through the above procedure. Second, thelocation of a point on a link L*i is uniquely determined with the parameter s regardless of theform of L*i . In this sense, the form is not essential in the network N * .

82002/10/03

Summing up, we can transform any heterogeneous network into a homogeneous network
through the uniform network transformation.

3. Geometrical Realizability of the transformed network
Having found the above nice transformation, we question whether or not the transformed
network N * can be geometrically realized on a plane. The original network N is given on aplane (Figure 6a), but the length of each link in the transformed network N * changes (Figure6b), and hence it is questionable that the transformed network N * is geometrically realized ona two-dimensional space (plane). For example, in Figure 6b, the transformed links might crossthe other links. In this section, we examine this question. Note that such a problem never occurs
in the probability integral transformation, because the correspondence is between only two lines(the x-axis and y-axis as in Figure 4).

Let us first define what a ‘geometrically realized planar network’ of N * is. Let N G be a
network consisting of a set, LG , of links and a set of nodes, P G . For N , N * and N G(Figure 6), we consider the following conditions:i) there exists on-to-one correspondence between links in L* (or L ) and those in LG ,ii) there exits one-to-one correspondence between nodes in P * (or P ) and those in P G ,iii) the graph of the network N G is isomorphic to the planar geometric graph of the networkN,iv) the length of a link LGi in LG is proportional to the length of the corresponding link L*i
in L* (the proportion rate is the same for all links i = 1, K , n ).
When the network N G satisfies all these conditions, we say that the network is a geometricallyrealized planar network of the transformed network N * . Fortunately, we can find ageometrically realized planar network N G of the transformed network N * through thefollowing procedure.

9

2002/10/03

First, we assume that the configuration of nodes in P G is the same as that of nodes in P of agiven network N (hence (i) is satisfied) (the configuration of the nodes in Figure 6a is thesame as that in Figure 6c).

Second, we stretch the length of each link in L* proportionally until the length of a link in L*
is greater than or equal to the length of corresponding link in L for all links (the property (iv)
is kept) (the numbers on the links in Figure 6b are all doubled in Figure 6c to satisfy Li ≤ LGi
for all i ).

Third, we obtain a set of polygons A1 ,K, An that satisfies: the polygon Ai contains the link

Li in L and the polygons do not overlap each other except at end nodes of links in L . An
example is shown in Figure 7. Such a set of polygons can be computationally obtained using thedecomposed line Voronoi diagram generated by the line segments of L (Okabe et al., 2000).

L

A

Figure 7: An example of A1 ,K, An

Fourth, for each polygon Ai , we draw a polygonal line LGi1

consisting of points

pi1 , pi 2 , pi 3 , pi 4 , pi 5 whose length is equal to the stretched link of L*i ((i) is satisfied) (Figure8a). If the line LGi1 is included in the polygon Ai , let LGi be LGi1 , and we stop. If not, we go

102002/10/03

to the next. Note that for ease of explanation, Li is assumed to be a straight-line segment, but
the following proof can be applied to the case of a polygonal line with slight modifications.
pi

Li1

Li3

A

Li2

L
pi

pi

pi

(a)

pi

(b)

(c)

Figure 8: The procedure for obtaining a geometrically realized planar network

Fifth, we bend the triangle pi 2 pi 3 pi 4 in such a way that the vertex pi 3 is on the link Li (seeFigure 8b). The length of the bended line, LGi2 , is the same as that of the link L*i . If this bended
line is included in the polygon Ai , let LGi be LGi2 , and we stop. If not, we go to the next.

Sixth, we bend the two triangles in the same manner as in Figure 8c. The length of the bended
line, LGi3 , is the same as that of the link L*i . If this bended line is included in the polygon Ai ,let LGi be LGi3 , and we stop. If not, we go to the next.

In this manner, we continue a similar procedure until the bended line, LGim , is included in thepolygon Ai . This procedure always terminates in a finite number, m , of steps. Let LGi be

LGim .

When the above procedure terminates, we construct a network N G with the set of links

LG = {L1Gm ,K, LGnm } and the set of nodes P G = P . Now our problem is to examine whether or
not the network N G satisfies the conditions (i)-(iv). Since P G = P , the condition (i) is

112002/10/03

satisfied. Since there is one-to-one correspondence between L and L* , and there is
one-to-one corresponding between L* and LG , the conditions (i) is satisfied. Since the lengthof a link in LG is stretched in proportion to the length of the corresponding link in L* ,thecondition (iv) is satisfied. Since the graph of the network N is a planar graph and since thelink LGim fits to the corresponding link Li by continuous deformation without crossing theother links (the polygons A1 ,K, An do not overlap each other except at nodes), the condition(iii) is satisfied. Therefore the network N G is a geometrically realized planar network of theuniform network N * that is transformed from a given heterogeneous network N . This provesthat any uniform network that is transformed from a heterogeneous network through theuniform transformation can be geometrically realized on a plane.

4. Conclusions
The major conclusions of this paper are summarized as follows.
i) Any heterogeneous network can be transformed into the uniform (homogeneous) network
through the uniform network transformation.
ii) The obtained uniform network can be geometrically realized on a plane.

The implications of these conclusions are very useful. First, we can easily deal with aheterogeneous network. This is a great advantage of spatial analysis on a network, because there
exists no transformation from a heterogeneous plane to a homogeneous plane and so spatial
analysis on a heterogeneous plane is very hard. Second, any methods for spatial analysis on ahomogeneous network can be applied to spatial analysis on a heterogeneous network. Third, we
do not have to develop special methods for spatial analysis on a heterogeneous network. We
only concentrate on developing methods for spatial analysis on a homogeneous network.

As shown in this paper, spatial analysis on a network has great advantages, but no methods are
perfect, and spatial analysis on a network has also some limitations. In practice, computation on

12

2002/10/03

a network is usually more time-consuming than that on a plane. This limitation has been greatly
diminished by recent progress in computer hardware and processing, but computation on a
network still takes much time. Second, in spatial analysis on a network, all geographicalfeatures are supposed to be mapped on a network. However, there are some geographicalfeatures that cannot be mapped on a network. For example, a large park that is represented by apolygon is difficult to map on a network. Thus spatial analysis on a network is effective only
when geographical features can be meaningfully mapped on a network.

References
Bailey, T.C. and Gatrell, A.C. (1995) Interactive Spatial Data Analysis, Harlow: Longman.
Berry, J. (2002) “Use travel time to connect with customers”, Geoworld, Vol.15, No.6, 24-25.
Diggle, P. (1983)

Statistical Analysis of Spatial Point Patterns, London: Academic Press

Freund, J.E. (1971) Mathematical Statistics, 2nd edition, Englewood Cliff: Prentice-Hall.
Getis, A. and Boots, B. (1978)

Models of Spatial Processes, Cambridge: Cambridge

University Press.
King, L.J. (1969)

Statistical Analysis in Geography, Englewood: Prentice-Hall.

Lewis, P. (1977) Maps and Statistics, London: Methuen.
Morita, M., Okunuki, K. and Okabe, A. (2001), "A Market Area Analysis on a Network Using
GIS: A Case Study of Retail Stores in Nisshin City", Papers and Proceedings ofGeographic Information Systems Association,Vol.10,pp.45-50 (in Japanese).
Miller, H.J. (1994)“Market Area Delimination within Networks using Geographic

Information Systems”,
Miller, H.J. (1999)

Geographical Systems, Vol.1, No.2, pp.157-173.

“Measuring Space-time Accessibility Benefits within Transportation

Networks: Basic Theory and Computational Methods”, Geographical Analysis, Vol.31,
pp.187-212.
Okabe, A. (1998)“Toward a Toolbox for Analyzing Spatial Relations”, Workshop on Status13

2002/10/03

and Trends in Spatial Analysis, Santa Barbara, California: December 10-12, 1998
Okabe, A. (2000) "Spatial Analysis on a Network with GIS" presented at the International
Conference on Geographic Information Science October 28-31, 2000, Savannah, Georgia,
USA.
Okabe, A., Boots, B., Sugihara, K. and Chiu, S. N. (2000) Spatial Tessellations: Concepts andApplications of Voronoi Diagrams, (2nd edition), Chichester: John Wiley.
Okabe, A. and Kitamura, M., (1996) "A Computational Method for Market Area Analysis on a
Network", Geographical Analysis, Vol.28, No.4, pp.330-349.
Okabe, A. and Miki, F. (1984) "A Conditional Nearest-Neighbor Spatial Association Measurefor the Analysis of Conditional Locational Interdependence", Environment and Planning A,
Vol.16, pp.163-171.
Okabe, A., Boots, B., Sugihara, K. and Chiu, S.N. (2000) Spatial Tessellations: Concepts andApplications of Voronoi Diagrams, Chichester: John Weily.
Okabe, A. and Okunuki, K. (2001) "A computational method for estimating the demand of retailstores on a street network and its implementation in GIS", Transactions in GIS, Vol.5, No.3,
pp.209-220.
Okabe, A. and Yamada, I.(2001) "The K-function method on a network and its computational
implementation" Geographical Analysis, Vol.33, No.3, pp.271-290.
Okabe, A., Yomono, H. and Kitamura, M., (1995) "Statistical Analysis of the Distribution of
Points on a Network", Geographical Analysis, Vol.27, No. 2, pp.152-175.
Okabe, A., Okunuki, K., Funamoto, S., Okano, K. and Itoh, F. (2002) “Software for spatial
analysis on a network”, Proceedings of Specialist Meeting on Spatial Data Analysis

Software Tools, Santa Barbara, May 10-11, 2002 (CD).

Silverman, B.W. (1986) Density Estimation for Statistics and Data Analysis, London: Chapman
and Hall.
Yamada, I. and Thill, J-C. (2002) An Empirical Comparison of Planar and Network K-function
Analyses, AAG Annual Meeting, Los Angeles, CA.

14

2002/10/03

Acknowledgements
An earlier version of this paper was presented at a session in GIScinece2000 held at Savanna,
2000. We are thankful for valuable comments from the floor. In particular, the proof in Section 3
was motivated by a question raised from the floor. This study is partly supported by Grant-in-aid
No. 10202201, Japanese Ministry of Education and Science.

15