地理科学 ›› 2013, Vol. 33 ›› Issue (2): 143-149.doi: 10.13249/j.cnki.sgs.2013.02.143
收稿日期:
2012-01-09
修回日期:
2012-04-09
出版日期:
2013-02-20
发布日期:
2013-02-20
作者简介:
作者简介:戴技才(1974-),男,湖南益阳人,博士,讲师,主要从事地理信息系统模型,复杂系统研究。E-mail:
基金资助:
Ji-cai DAI1(), Hui-ming ZONG2(
)
Received:
2012-01-09
Revised:
2012-04-09
Online:
2013-02-20
Published:
2013-02-20
摘要:
最优选址在社会经济活动中非常重要。传统的网络聚类分析以空间两点之间的直线度量距离,而不是以空间最短网络路径作为聚类条件,无法找到复杂网络的最优选址中心。基于最短路径的复杂网络聚类模型,探索复杂道路网络中的最优选址。模型通过迭代法获取近似最优解,二分邻域分割法逼近最优解分布区,应用邻域下降法达到最优选址点。实验结果表明:本模型与穷举-Dijkstra算法相比,计算精度相当,计算速度提高了约23倍以上。模型以复杂网络聚类为基础推导,为复杂网络选址、聚类提供了一种新的理论与方法。
中图分类号:
戴技才, 宗会明. 基于复杂网络聚类的最优选址模型[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.
表1
网络聚类法与穷举-Dijkstra算法的实验对比结果"
国家或地区 | 节点数 (个) | 弧段数 (个) | 穷举-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 | 是 |
[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. |
[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. |
|