DEIM Forum 2017 G6-2

Characterizing Areas of Spatial Networks Based on Mixing Patterns
Arief MAULANA† , Kazumi SAITO† , Tetsuo IKEDA† , and Hiroaki YUZE†† Graduate School of Management and Information of Inovation, University of Shizuoka
52–1 Yada, Suruga-ku, Shizuoka 422–8526 Japan
E-mail: †{j15501,k-saito,t-ikeda,yuze}@u-shizuoka-ken.ac.jp
Abstract In this paper, we propose a new method for classifying a road network automatically into some areas andcharacterizing them based on the tri-mixing patterns of node degrees and the K-medoids clustering algorithm. Inour experiments, using the three road networks of three cities in Shizuoka prefecture collected from OpenStreetMap(OSM), we show that our method can produce some promising results.
Key words spatial network, degree mixing pattern, area classification and characterization.

1. Introduction
Studies of the structure and functions of large complex networks have attracted a great deal of attention in many different fields such as sociology, biology, physics and computerscience [1]. As a particular class, we focus on spatial net-as its characteristics. In our experiments, using the threeroad networks of three cities in Shizuoka prefecture collectedfrom OpenStreetMap (OSM), we show that our method canproduce some promising results.

2. Proposed Method

works embedded in the real space, like road networks, whose

Let G = (V, E) be a given spatial network, where V =nodes occupy precise positions in two or three-dimensional{u, v, w, · · ·} and E = {(u, v), · · ·} mean sets of nodes andEuclidean space, and whose links are real physical connec-links, respectively. In this paper, we only consider undi-tions [2].

rected networks such that (u, v) ∈ E implies (v, u) ∈ E,

In this paper, we address the problem of classifying andbut we can straightforwardly extend our approach to deal

characterizing spatial networks in terms of local connection

with directional networks. For each node u ∈ V, we de-patterns of node degrees [3], by especially focusing on thenote its degree by r(u). Now, we consider connected triple

property that the maximum node degrees of these networks

nodes, just like network motifs analyses based on triad pat-are restricted to relatively small numbers. Such characteris-terns [4]. Let F be the set of the connected triples defined bytic connection patterns that appear frequently in some net-

F = {(u, v, w) | (u, v) ∈ E, (v, w) ∈ E}. Then, for each node

works can be regarded as their main building blocks, just likes ∈ V, we can define the egocentric connected triples of thenetwork motifs in [4]. For such spatial networks, we explore

node s by Fs = {(u, v, w) ∈ F | s ∈ {u, v, w}}, and consider atechniques for extracting areas with some coherent charac-

three-dimensional array Cs whose i-j-kth element cs (i, j, k)teristics. Although this task is somehow relating to com-is calculated by cs (i, j, k) = |{(u, v, w) ∈ Fs | r(u) = i, r(v) =munity extraction ones widely studied in complex network
analysis [5], unlike these general techniques only using net-j, r(w) = k}|. Thus, for each node s ∈ V, by arranging thesethree-dimensional array elements such that i <= k and j >= 2,work structure, we focus on exploiting the local connection

we can construct a feature vector of the node s expressed

patterns of node degrees.

as xs = (cs (1, 2, 1), cs (1, 2, 2), · · ·)T , where xTs means theIn this paper, we propose a new method for classifying

transposed vector of xs . Table 1 shows our arrangementa road network automatically into some areas and charac-of tri-mixing patterns in case that the maximum degree isterizing them based on the tri-mixing patterns of node de-5, maxv∈V r(v) = 5. Hereafter, each tri-mixing patter is also

grees [3] and the K-medoids clustering algorithm. The pro-referred to as its associated ID.

posed method first computes a feature vector for each node,

Let X = {xu , xv , · · ·} be the set of feature vectors com-consisting of the normalized frequency of the ego-centric tri-

puted by the above procedure. Then, we consider classifying

mixing patterns, then classifies these vectors into some areas

V into K areas, V1 , · · · , VK , by the K-medoids algorithm.

by the use of the greedy K-medoids clustering algorithm,

More specifically, we select the set of medoids (representa-and finally provide each of the classified areas with the nor-tive vectors) R ⊂ X whose number of elements is K, i.e.,

malized frequency curve of the corresponding medoid vector|R| = K, so as to maximize the following objective function

Table 1 List of tri-mixing patternsin Tab. 1. Table 2 shows the basic statistics of the networks

ID Pattern ID Pattern ID Pattern ID Patternfor the three cities.

1

1-2-1

16

1-3-1

31

1-4-1

46

1-5-1

2

1-2-2

17

1-3-2

32

1-4-2

47

1-5-2

3

1-2-3

18

1-3-3

33

1-4-3

48

1-5-3

Table 2 Basic statistic as network
NoCity
|V |
|E|

4

1-2-4

19

1-3-4

34

1-4-4

49

1-5-4

1

Hamamatsu 323,457 346,294

1-5-5

2

Numazu44,9803

Shizuoka

195,786 208,329

5

1-2-5

20

1-3-5

35

1-4-5

50

48,550

6

2-2-2

21

2-3-2

36

2-4-2

51

2-5-2

72-2-3

22

2-3-3

37

2-4-3

52

2-5-382-2-4

23

2-3-4

38

2-4-4

53

2-5-4

92-2-5

24

2-3-5

39

2-4-5

54

2-5-5

10

3-2-3

25

3-3-3

40

3-4-3

55

3-5-3

11

3-2-4

26

3-3-4

41

3-4-4

56

3-5-4

12

3-2-5

27

3-3-5

42

3-4-5

57

3-5-5

i.e., K = 5.

13

4-2-4

28

4-3-4

43

4-4-4

58

4-5-4

tal results for the three cities, Hamamatsu, Numazu, and

14

4-2-5

29

4-3-5

44

4-4-5

59

4-5-5

Shizuoka, where Figs. 1(a), 2(a), and 3(a) show the num-

15

5-2-530

5-3-5

45

5-4-5

60

5-5-5

bers of nodes in the classified areas, V1 , V2 , V3 , V4 , and V5 ,3. 2 Results
We applied our proposed method to road networks of threecities by setting the number of the classifying areas to five,Figures 1, 2, and3 show our experimen-and Figs. 1(b), 2(b), and 3(b) show the normalized frequency
curves for these areas. From these figures, we can observebased on the cosine similarity:f (R) =∑{maxr∈Rx∈XxT r√√xT x rT r}

the following three similar characteristics. First, as for the.

V1 areas colored in green in all the three cities, they contains
the largest numbers of nodes as shown in Figs. 1(a), 2(a),Then, the greedy K-medoids algorithm can be summarized

and 3(a), and their normalized frequency curves have only

as follows: after initializing k ← 1 and R ← ∅, we repeatedly

one peak at the 2-2-2 pattern (pattern ID 6) as shown inselect and add each medoid byFigs. 1(b), 2(b), and 3(b), Second, as for the the V2 area col-rk ← max {f (R ∪ {x}) − f (R)} , R ← R ∪ {rk },x∈X \Rduring |R| <= K together with increment k ← k + 1. From
the obtained set of the K medoids, R = {r1 , · · · , rK }, wecan compute each classified area as
Vk ={}v ∈ V; rk = max {ρ(xv , r)} .
r∈RFinally, we provide each classified area Vk with the normalized frequency curve of the corresponding medoid vector
rk /√rTk rk as its characteristics.

3. Experiments

ored in blue in Hamamatsu, the V4 area colored in magenta
in Numazu, and the V5 area colored in cyan in Shizuoka,
they contains the second largest numbers of nodes, and theirnormalized frequency curves have the only one largest peakat the 2-3-2 pattern (pattern ID 21), Third, as for the V3 areas colored in red in all the three cities, although their orders
in terms of the numbers of nodes in these areas are diﬀerent,
their normalized frequency curves are clearly characterizedby containing many peaks in comparison to the other areas.
Figure 4, 5, and 6 show the visualization results by plotting each node at its position with a color of its classified area
as shown in Figs. 1, 2, and 3 for Hamamatsu, Numazu, andShizuoka, respectively, We consider that these visualization

In this section, we first explain the datasets used in ourresults are reasonably interpretable in the sense that several

experiments, and then show the results obtained by our pro-areas such as urban, mountainous and intermediate regions

posed methods.

were clearly classified by using diﬀerent colors. Below we3. 1 Datasets

explain three examples for clarifying characteristics of theWe used OSM data of three cities, Hamamatsu, Numazu

classified areas. First, as for the V1 areas colored in green

and Shizuoka, in Shizuoka prefecture, We extracted all high-in all the three cities, which were characterized by both theways and all nodes appearing in them, and constructedlargest numbers of nodes and the only one peak at the 2-2-2

each spatial network by mapping the ends, intersections andpattern as described above, we can see that each of thesecurve-fitting-points of streets into nodes, and the streets be-areas spread all over the city as shown in Figs. 4, 5, andtween the nodes into links, where the largest connected com-

6. Thus, we can naturally interpret characteristics of theseponent of each spatial network was used as our road network.

areas as containing a large numbers of curve-fitting-points,

Here we regarded the degree of each node whose degree iswhich typically appear in mountainous regions. Second, as

greater than 5 simply as 5 because the number of such nodes

for the the V2 area colored in blue in Hamamatsu, the V4

was quite small, Namely, we used feature vectors as shown

(b) Normalized frequency curves(a) Numbers of nodes in classified areas
Figure 1 Hamamatsu City(a) Numbers of nodes in classified areas(b) Normalized frequency curves
Figure 2 Numazu City(a) Numbers of nodes in classified areas(b) Normalized frequency curves
Figure 3 Shizuoka Cityarea colored in magenta in Numazu, and the V5 area col-eas containing wide variety of junctions as local connection

ored in cyan in Shizuoka, which were characterized by bothpatterns. which typically appear in urban regions. In short,the second largest numbers of nodes and the only one largest

from these experimental results, we can confirm that our pro-peak at the 2-3-2 pattern, we can see that each of these areas

posed method can be a vital and useful tool for reasonably

also spread all over the city. Thus, we can naturally interpretmeasuring the characteristics of cities.

characteristics of these areas as containing a large numbersof crossroads like T-junctions. which typically appear in in-4. Conclusion

termediate regions. Third, as for the V3 areas colored in red

In this paper, we propose a new method for classifying a

in all the three cities, which were characterized only by theroad network automatically into some areas and character-many peaks in comparison to the other areas, we can see thatizing them based on the tri-mixing patterns of node degrees

each of these areas spread relatively small regions of the city.

and the K-medoids clustering algorithm. In our experiments

Thus, we can naturally interpret characteristics of these ar-using the three road networks of three cities in Shizuoka pre-(a) V1(b) V2(c) V3(d) V4(e) V5(d) V4(e) V5(d) V4(e) V5

Figure 4 Cluster distribution in Hamamatsu(a) V1(b) V2(c) V3
Figure 5 Cluster distribution in Numazu(a) V1(b) V2(c) V3
Figure 6 Cluster distribution in Shizuoka

fecture collected from OpenStreetMap (OSM), we showedthat our method can be a vital tool for producing promising results. In future, we plan to evaluate our method using
various road networks.
Acknowledgements
This work was supported by Grants-in-Aid for Scientific Research (No.15K00311).
References[1] Newman, M. E. J.: The structure and function of complexnetworks, SIAM Review, Vol. 45, pp. 167–256 (2003).
[2] Crucitti, P., Latora, V. and Porta, S.: Centrality measuresin spatial networks of urban streets, Physical Review E,

Vol. 73, No. 3, pp. 036125+ (2006).
[3] Maulana, A., Saito, K., Ikeda, T., Yuze, N., Watanabe, T.,Okubo, S. and Muto, N.: Analyzing Similarity Structureof Spatial Networks Based on Degree Mixing Patterns, Advanced Information Networking and Applications, Vol. 30,
pp. 1–8 (2016).
[4] Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N.,
Chklovskii, D. and Alon, U.: Network motifs: simple
building blocks of complex networks., Science (New York,N.Y.), Vol. 298, No. 5594, pp. 824–827 (online), 10.1126/science.298.5594.824 (2002).
[5] Newman, M. E. J. and Girvan, M.: Finding and evaluating community structure in networks, Physical Review E,
Vol. 69, p. 026113 (2004).