2013 , Vol. 33 >Issue 2: 143 - 149

• 戴技才 , 1 ,
• 宗会明 , 2

• 1.重庆师范大学地理与旅游学院 重庆 400047
• 2.西南大学地理科学学院,重庆400715

要求修回日期: 2012-04-09

网络出版日期: 2013-02-20

Model of Locating Optimal Sites Based on Complex Network Clustering

• DAI Ji-cai , 1 ,
• ZONG Hui-ming , 2
Expand
• 1.College of Geographical Sciences, Chongqing Normal University, Chongqing 400047, China
• 2.School of Geographical Sciences, Southwest University, Chongqing 400715, China

Received date: 2012-01-09

Request revised date: 2012-04-09

Online published: 2013-02-20

Copyright

### Abstract

The best location for site selection is very important for social and economical systems. Traditional clustering analysis cannot reach the optimal location allocation center based on the Euclidian, Manhattan, Chebyshev, Fu or Tanimoto distance,which does not depend on the shortest path distance as the clustering condition. Complex network clustering model based on the shortest path is proposed to explore site selection in this paper. The approximate optimal results are obtained using the iterative technology. The searching range of optimal site allocation is approached by half dividing the neighborhood. And the best location is captured applying the descend strategy. Experiments indicate that the proposed model can improve the calculating speed by at least 23 times with the same precision to approach the optimal resolution compared to the greedy Dijkstra algorithm. This model is inferred from the complex network clustering. It provides new theory and method to cluster complex network and locate sitting facilities.

### 1 模 型

#### 1.1 获取近似最优解

Pi是已知的网络节点(xi,yi) (i= 0,1,2,…n)。
P为待求的最优救灾物质储备库的选址点 (x,y),即本案例的最优解。
ci是网络节点Pi处的人数。
b是某救灾物质的人均需求量。

$d i = b ⋅ c i ⋅ ( x - x i ) 2 + ( y - y i ) 2$ (1)
di也可认为是最优位置点PPi处的网络流量。

$D = ∑ i = 1 n d i = ∑ i = 1 n b ⋅ c i ⋅ ( x - x i ) 2 + ( y - y i ) 2$ (2)
D其实就是整个网络流量,定义为目标函数。当目标函数D取最小值时对应的(x,y),即为本案例的最佳选址点。目标函数D是一个二元函数。根据二元函数连续的定义可知,D是连续函数。函数D的定义域为 $x ∈ ∈ ( - ∞ , + ∞ )$ , $y ∈ ∈ ( - ∞ , + ∞ )$ 。对应实际问题,定义域为有界闭区域。在有界闭区域上,连续函数D有界,且能取得它的最小值。D的最小值的几何意义是：网络中存在某个点,该点至网络上其它各点的加权距离之和最小,如图2所示。求函数D的最小值和最佳选址点(x,y)的方法有如下两种。

$∂ D ∂ x = ∑ i = 1 n b ⋅ c i ⋅ ( x - x i ) ( x - x i ) 2 + ( y - y i ) 2 = 0 ∂ D ∂ y = ∑ i = 1 n b ⋅ c i ⋅ ( y - y i ) ( x - x i ) 2 + ( y - y i ) 2 = 0$ (3)

F(x,y) = 0 (4)
F(x,y)的雅可比(Jacobi)矩阵及其逆矩阵。
$F ' ( x , y ) = ∂ 2 D ∂ x 2 ∂ 2 D ∂ x ∂ y ∂ 2 D ∂ y 2 ∂ 2 D ∂ x ∂ y$ (5)

$( x , y ) k + 1 = ( x , y ) k - F ' ( ( x , y ) k ) - 1 F ( ( x , y ) k )$ (6)

$∂ 2 D ∂ x 2 = ∑ i = 1 n b ⋅ c i ( x - x i ) 2 + ( y - y i ) 2 - b ⋅ c i ⋅ ( x - x i ) 2 ( x - x i ) 2 + ( y - y i ) 2 3$
$= b ⋅ c i ⋅ ( y - y i ) 2 ( x - x i ) 2 + ( y - y i ) 2 3$ (7)
$∂ 2 D ∂ y 2 = ∑ i = 1 n b ⋅ c i ( x - x i ) 2 + ( y - y i ) 2 - b ⋅ c i ⋅ ( y - y i ) 2 ( x - x i ) 2 + ( y - y i ) 2 3$
$= b ⋅ c i ⋅ ( x - x i ) 2 ( x - x i ) 2 + ( y - y i ) 2 3$ (8)
$∂ 2 D ∂ x ∂ y = - ∑ i = 1 n b ⋅ c i ⋅ ( x - x i ) ( y - y i ) ( x - x i ) 2 + ( y - y i ) 2 3$ (9)
$( x i , y i ) i = 1,2 ⋯ n$ 已知的前提下,牛顿迭代法求解是一种快捷方法。对于本类问题,初值选定义域内的任一点都不敏感,且牛顿法的根以平方收敛。但是牛顿迭代法的公式相对较复杂,需要求二阶偏导数,还要求矩阵的逆。

$x = ∑ i = 1 n b ⋅ c i ⋅ x i ( x - x i ) 2 + ( y - y i ) 2 ∑ i = 1 n b ⋅ c i ( x - x i ) 2 + ( y - y i ) 2 y = ∑ i = 1 n b ⋅ c i ⋅ y i ( x - x i ) 2 + ( y - y i ) 2 ∑ i = 1 n b ⋅ c i ( x - x i ) 2 + ( y - y i ) 2$ (10)

$x = ∑ i = 1 n b ⋅ c i ⋅ x i ∑ i = 1 n b ⋅ c i y = ∑ i = 1 n b ⋅ c i ⋅ y i ∑ i = 1 n b ⋅ c i$ (11)

#### 1.2 逼近最优解

##### Fig. 5 Principle of searching for the results based on the descend approach in the neighborhood

$D 1 = | | p 3 - p 1 | | × D 1 3 + | | p 4 - p 1 | | × D 1 4 + | | p 5 - p 1 | × D 1 5 + | | p 6 - p 1 | | × D 1 6$ (12)
$| p 3 - p 1 |$ 是网络节点P1至网络节点P3的网络路径距离, $D 1 3$ 表示经P3点进入P1点的网络汇流量。不妨设 $D 1 6 ≥ D 1 5 ≥ D 1 3 ≥ D 1 4$ 。若不等式(13)成立,则P6点是比P1点更优的解,下降路径为 $P 1 → P 6$ 。若P1的四个相邻节点都不满足相应的形如(13)方程,则应用Dijkstra算法逐个求取D3 D4 D5 D6,再与D1比较,得出下降路径,或停止该路径的搜索。
$| p 6 - p 1 | | × ( D 1 - D 1 6 ) + D 1 6 ≤ D 1$ (13)

（个）

（个）

(h)

### 3 结 论

The authors have declared that no competing interests exist.

### 参考文献

 [1] Jain A K, Murty M N,Flynn P J.Data clustering: A review[J]. Acm Comput Surv, 1999, 31:264-323.
 [2] Wu X, Kumar V, Quinlan J R, et al.Top 10 algorithms in data mining[J]. Knowl Inf Syst, 2008, 14:1-37.
 [3] King B.Step-wise clustering procedures[J]. J Am Stat Assoc, 1967, 69:86-101.
 [4] Murtagh F.A survey of recent advances in hierarchical clustering algorithms which use cluster centers[J]. Comput J,1984, 26:354-359.
 [5] Lloyd S P.Least squares quantization in pcm[J]. IEEE T Inform Theory, 1982, 28(2):129-137.
 [6] Lloyd S P.Least squares quantization in pcm[C]. Bell Telephone Laboratories Paper, 1957.
 [7] Gray R M, Neuhoff D L.Quantization[J]. IEEE T Inform Theory, 1998, 44(6):2325-2384.
 [8] Ball G H, Hall D J.Isodata, a novel method of data analysis and classification[M]. Technical report republished by Stanford University, Stanford, CA, 1965.
 [9] Ruspini E H.A new approach to clustering[J]. Inf Control, 1969, 15:22-32.
 [10] Zadeh L A.Fuzzy sets[J]. Inf Control, 1965, 8:338-353.
 [11] Hart P.The condensed nearest neighbor rule[J]. IEEE T Inform Theory, 1968, 14:515-516.
 [12] Bezdek J C, Chuah S, Leep D.Generalized k-nearest neighbor rules[J]. Fuzzy Set Syst, 1986, 18(3):237-256.
 [13] Dempster A P, Laird N M, Rubin D B.Maximum likelihood from incomplete data via the EM algorithm[J]. J R Stat Soc B, 1977, 39:1-38.
 [14] Zahn C T.Graph-theoretical methods for detecting and describing gestalt clusters[J]. IEEE T Comput C, 1971, 20:68-86.
 [15] Guimera R, Sales-Pardo M, Amaral L A N. Modularity from fluctuations in random graphs and complex networks[J]. Phys Rev E, 2004, 70:025101.
 [16] Pujol J M, Bejar J, Delgado J.Clustering algorithm for determining community structure in large networks[J]. Phys Rev E, 2006, 74:016107.
 [17] Palla G, Derenyi I, Farkas I, et al.Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435:814-818.
 [18] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433:895-900.
 [19] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Phys Rev E, 2004, 69(6):066133.
 [20] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Phys Rev E, 2004, 69:026113.
 [21] Duch J, Arenas A.Community detection in complex networks using extremal optimization[J]. Phys Rev E, 2005, 72:027104.
 [22] Jain A K.Algorithms for clustering data[M]. Prentice-Hall advanced reference series Prentice-Hall, Inc, Upper Saddle River, NJ, 1988.
 [23] Hagen L, Kahng A B.New spectral methods for ratio cut partitioning and clustering[J]. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 1992,1992, 11:1074-1085.
Options

/

 〈 〉