基于复杂网络聚类的最优选址模型

doi:10.13249/j.cnki.sgs.2013.02.143

地理科学 ›› 2013, Vol. 33 ›› Issue (2): 143-149.doi: 10.13249/j.cnki.sgs.2013.02.143

基于复杂网络聚类的最优选址模型

戴技才¹(), 宗会明²()

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

收稿日期:2012-01-09 修回日期:2012-04-09 出版日期:2013-02-20 发布日期:2013-02-20
作者简介:
作者简介:戴技才(1974-),男,湖南益阳人,博士,讲师,主要从事地理信息系统模型,复杂系统研究。E-mail:daijicai@cqnu.edu.cn
基金资助:
教育部人文社会科学研究青年基金(批准号: 11YJCZH023);国家自然科学基金项目（41271411,41001102）资助

Model of Locating Optimal Sites Based on Complex Network Clustering

Ji-cai DAI¹(), Hui-ming ZONG²()

1.College of Geographical Sciences, Chongqing Normal University, Chongqing 400047, China
2.School of Geographical Sciences, Southwest University, Chongqing 400715, China

Received:2012-01-09 Revised:2012-04-09 Online:2013-02-20 Published:2013-02-20

摘要/Abstract

摘要：

最优选址在社会经济活动中非常重要。传统的网络聚类分析以空间两点之间的直线度量距离,而不是以空间最短网络路径作为聚类条件,无法找到复杂网络的最优选址中心。基于最短路径的复杂网络聚类模型,探索复杂道路网络中的最优选址。模型通过迭代法获取近似最优解,二分邻域分割法逼近最优解分布区,应用邻域下降法达到最优选址点。实验结果表明：本模型与穷举-Dijkstra算法相比,计算精度相当,计算速度提高了约23倍以上。模型以复杂网络聚类为基础推导,为复杂网络选址、聚类提供了一种新的理论与方法。

关键词: 选址, 网络聚类, 复杂网络, 最短路径, Dijkstra算法

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.

Key words: location allocation, network clustering, complex network, shortest path, Dijkstra algorithm

中图分类号:

K903

戴技才, 宗会明. 基于复杂网络聚类的最优选址模型[J]. 地理科学, 2013, 33(2): 143-149.

Ji-cai DAI, Hui-ming ZONG. Model of Locating Optimal Sites Based on Complex Network Clustering[J]. SCIENTIA GEOGRAPHICA SINICA, 2013, 33(2): 143-149.

图/表 8

图1

图2

图3

图4

图5

图6

图7

表1

参考文献 23

[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.

国家或地区	节点数（个）	弧段数（个）	穷举-Dijkstra法用时(h)	网络聚类法用时 (h)	网络聚类法是否找到了最优解
中国大陆	21986	27256	49.47	1.83	是
英国	3774	5295	0.23	0.01	是
德国	3799	5343	0.24	0.01	是
法国	5314	7056	0.63	0.01	是
意大利	2563	3469	0.07	0.003	是
印度	15941	21674	17.09	0.31	是
日本	6706	8983	1.27	0.05	是
俄罗斯	37705	43908	258.49	9.32	是
美国本土	28602	46358	112.26	3.74	是

基于复杂网络聚类的最优选址模型

Model of Locating Optimal Sites Based on Complex Network Clustering

RichHTML

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 23

相关文章 7

Metrics

本文评价

推荐阅读 10

[1]	王列辉, 郑渊博, 叶斐. 航运企业重组与集装箱航运网络整合效应研究——以中国远洋海运集团有限公司为例[J]. 地理科学, 2019, 39(4): 560-567.
[2]	陈艳华, 韦素琼, 陈松林. 大陆台资跨界生产网络的空间组织模式及其复杂性研究——基于大陆台商千大企业数据[J]. 地理科学, 2017, 37(10): 1517-1526.
[3]	夏既胜, 何文通, 李虹霖. 区域物质流通虚拟网络研究——以金沙江流域中段为例[J]. 地理科学, 2012, 32(7): 816-821.
[4]	刘承良, 余瑞林, 曾菊新, 王家琦. 武汉城市圈城乡道路网的空间结构复杂性[J]. 地理科学, 2012, 32(4): 426-433.
[5]	程淑佳, 王肇钧. 复杂网络理论下世界原油贸易空间格局演进研究[J]. 地理科学, 2011, 31(11): 1342-1348.
[6]	王肇钧, 程淑佳, 于国政. 基于复杂网络理论的中美原油进口空间格局演进比较[J]. 地理科学, 2010, 30(5): 667-672.
[7]	伍少坤, 黎夏, 刘小平, 龚友夫. 基于城市扩张的动态选址模型——以深圳垃圾转运站选址为例[J]. 地理科学, 2008, 28(3): 314-319.