地球信息科学学报 ›› 2021, Vol. 23 ›› Issue (12): 2128-2138.doi: 10.12082/dqxxkx.2021.210397
王续盘(), 张衡*(
), 周杨, 胡校飞, 彭杨钊, 齐凯
收稿日期:
2021-07-15
修回日期:
2021-11-02
出版日期:
2021-12-25
发布日期:
2022-02-25
通讯作者:
*张 衡(1976— ),男,河南郑州,博士,副教授,主要从事摄影测量与遥感方向研究。 E-mail: 13783651715@163.com作者简介:
王续盘(1997— ),男,甘肃白银人,硕士生,主要从事摄影测量与遥感方向的研究。E-mail: 1848125421@qq.com
基金资助:
WANG Xupan(), ZHANG Heng*(
), ZHOU Yang, HU Xiaofei, PENG Yangzhao, QI kai
Received:
2021-07-15
Revised:
2021-11-02
Online:
2021-12-25
Published:
2022-02-25
Supported by:
摘要:
随着人们对网络空间的依赖性不断增强,互联网技术与网络基础设施规模迅速发展。很难直接用数字或表格的形式对网络空间进行全局的规划与管理,并且不容易发现隐藏在网络空间中的一些关键信息。网络空间点群要素的多尺度模型构建对网络空间数据的多尺度分析和可视化具有非常重要的意义。本文以网络空间的特征为依据,在借鉴基于社团划分的网络空间分层算法和基于节点重要性的网络空间分层算法特点的基础上,提出了Blondel算法和k-核分解的混合算法相结合的网络空间点群要素多尺度模型构建算法。本算法通过自动社团划分,用同一社团内的节点合并构建新的网络,有效解决了基于节点重要性的网络空间分层算法自动化程度低的弊端。利用核心节点来代替整个社团结构,显著保留了网络空间中节点的属性。实验表明使用该算法可以使各个层次网络空间点群要素的综合比例降至30%以下,较好的实现了网络空间点群要素的聚类与分层,若将网络空间点群要素的多尺度模型应用于地理空间中,则可实现网络空间地图的多尺度绘制。
王续盘, 张衡, 周杨, 胡校飞, 彭杨钊, 齐凯. Blondel和k-核分解混合算法相结合的网络空间点群要素多尺度模型构建[J]. 地球信息科学学报, 2021, 23(12): 2128-2138.DOI:10.12082/dqxxkx.2021.210397
WANG Xupan, ZHANG Heng, ZHOU Yang, HU Xiaofei, PENG Yangzhao, QI kai. Multi-scale Model of Point Group Elements in Network Space Combined with Blondel and k-shell Decomposition Hybrid Algorithm[J]. Journal of Geo-information Science, 2021, 23(12): 2128-2138.DOI:10.12082/dqxxkx.2021.210397
[1] |
郭启全. 基于“人-地-网”关系的网络空间要素层次体系建设[J]. 地理研究, 2021, 40(1):109-118.
doi: 10.11821/dlyj020200867 |
[ Guo Qiquan. Construction of factors hierarchy system of cyberspace based on "human-earth-network" relationship[J]. Geographical Research, 2021, 40(1):109-118. ] | |
[2] | 祝振凱. 网络地图层次化表示方式[D]. 武汉:武汉大学, 2017. |
[ Zhu Z K. Hierarchical representation of network map[D]. Wuhan: Wuhan University, 2017. ] | |
[3] | 王永. 全球网络空间测绘地图研究综述[J]. 信息技术与网络安全, 2019, 38(5):1-6. |
[ Wang Yong. A review of global cyberspace mapping research[J]. Information Technology and Network Security, 2019, 38(5):1-6. ] | |
[4] | 胡三国. 一种基于网络空间测绘思想的网络管理策略[J]. 通讯世界, 2017(18):56-57. |
[ Hu S G. A network management strategy based on the concept of cyberspace surveying and mapping[J]. Communications World, 2017(18):56-57. ] | |
[5] |
Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.
pmid: 12060727 |
[6] | Tyler J, Wilkinson D, Huberman B. Email as spectroscopy:automated discovery of community structure with in organizations[A]. International Conference on Communities and Technologies[C]. 2003.81-96. |
[7] |
Radicchi F, Castellano C, Cecconi F. Defining and identifying community in networks[J]. Proc Natl Acad Sci, 2004, 101(9):2658-2663.
doi: 10.1073/pnas.0400054101 |
[8] |
Fortunato S, Latora V, Marchiori M. A method to find community structures based on information centrality[J]. Phys Rev E, 2004, 70(5):056104.
doi: 10.1103/PhysRevE.70.056104 |
[9] |
Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):066133.
doi: 10.1103/PhysRevE.69.066133 |
[10] |
Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6):066111.
doi: 10.1103/PhysRevE.70.066111 |
[11] | Noack A, Rotta R. Multi-level algorithms for modularity clustering[C]. Proceedings of the 8th International Symposium on Experimental Algorithms,Dortmund,Germany, 2009. 5526:257-268. |
[12] |
Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10):P10008.
doi: 10.1088/1742-5468/2008/10/P10008 |
[13] | 谈煜. 一种基于层次化社团结构的网络可视化方法[D]. 上海:上海交通大学, 2012. |
[ Tan Y. A network visualization method based on hierarchical community structure[D]. Shanghai: Shanghai Jiao Tong University, 2012. ] | |
[14] | 梁润鹏. 基于社团检测的大型网络可视化研究[D]. 上海:上海交通大学, 2012. |
[ Liang R P. Research on large network visualization based on community detection[D]. Shanghai: Shanghai Jiao Tong University, 2012. ] | |
[15] | Rotta R, Noack A. Multilevel local search algorithms for Modularity Clustering[J]. Journal of Experimental Algorithmics, 2011, 16(2). |
[16] |
Waltman L, Jan Van Eck N J. A smart local moving algorithm for Large-scale Modularity-based community detection[J]. The European Physical Journal B, 2013, 86(11):471.
doi: 10.1140/epjb/e2013-40829-0 |
[17] | 吴祖峰. 改进的Louvain社团划分算法[J]. 电子科技大学学报, 2013, 42(1):105-108. |
[ Wu Z F. Improved Louvain community partitioning algorithm[J]. Journal of UEST of China, 2013, 42(1):105-108. ] | |
[18] | 薛青. 改进的Louvain社团发现算法的研究及应用[D]. 太原:山西大学, 2020. |
[ Xue Q. Research and application of improved Louvain community discovery algorithm[D]. Taiyuan: Shanxi University, 2020. ] | |
[19] | Carmi S, Havlin S, KirkpatrickI S, et al. A model of Internet topology using K-shell decomposition[J]. Pro-ceedings of the National Academy of Sciences, 2007, 104(27),11150-11154. |
[20] | Svante Janson, Malwina J. Luczak. Asymptotic normality of the k-core in random graphs[J]. The Annals of Applied Probability, 2008, 18(3):1085-1137. |
[21] | 张龙. 网络资源测绘数据表达与分析技术研究[D]. 郑州:信息工程大学, 2018. |
[ Zhang L. Research on representation and analysis technology of network resource surveying data[D]. Zhengzhou: Information Engineering University, 2018. ] | |
[22] | 李政廉, 吉立新, 黄瑞阳, 等. 基于非重要节点拆分融合的网络层次压缩算法[J]. 计算机辅助设计与图形学学报, 2018, 30(2):244-253. |
[ Li Z L, Ji L X, Huang R Y, et al. Hierarchical network compression algorithm based on non-important node splitting and fusion[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(2):244-253. ] | |
[23] | 王映雪. 面向特征的网络空间点群要素自动综合方法[J]. 武汉大学学报·信息科学版, 2021, 46(3):427-433. |
[ WANG Yingxue. Feature oriented automatic synjournal method of network space point group elements[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3):427-433. ] | |
[24] | 李健霖. 地理信息约束的网络拓扑可视化方法研究与系统实现[D]. 成都:电子科技大学, 2016. |
[ Li J L. Research and system implementation of network topology visualization method with geographical information constraints[D]. Chengdu: University of Electronic Science and Technology of China, 2016. ] | |
[25] | 张倬. 基于地理位置信息约束的网络拓扑可视化方法研究[D]. 成都:电子科技大学, 2015. |
[ Zhang Z. Research on network topology visualization method based on geographic location information constraints[D]. Chengdu: University of Electronic Science and Technology of China, 2015. ] | |
[26] |
Namtirtha A, Dutta A, Dutta B. Identifying influential spreaders in complex networks based on K-shell hybrid method[J]. Physica A: Statistical Mechanics and its Applications, 2018, 499:310-324.
doi: 10.1016/j.physa.2018.02.016 |
[27] | 周杨. 网络空间测绘的概念及其技术体系的研究[J]. 计算机科学, 2018, 45(5):1-7. |
[ Zhou Y. Research on the concept and technical system of cyberspace surveying and mapping[J]. Computer Science, 2018, 45(5):1-7. ] | |
[28] | 王继龙. 网络空间信息系统模型与应用[J]. 通信学报, 2020, 41(2):74-83. |
[ Wang J L. Model and application of cyberspace information system[J]. Journal of Communications, 2020, 41(2):74-83. ] | |
[29] | 王映雪. 面向网络空间表达的数据模型设计及处理方法[J]. 测绘科学技术学报, 2019, 36(6):648-653. |
[ Wang Y X. Design and processing method of data model for representation of cyberspace[J]. Journal of Surveying and Mapping Science and Technology, 2019, 36(6):648-653. ] | |
[30] | 汪小帆, 刘亚冰. 复杂网络中的社团结构算法综述[J]. 电子科技大学学报, 2009, 38(05):537-543. |
[ Wang X F, Liu Y B. Review of community structure algorithms in complex networks[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(5):537-543. ] | |
[31] | 许慧. 社会网络中节点重要性度量方法研究[D]. 哈尔滨:哈尔滨工程大学, 2020. |
[ Xu H. Research on the measure method of node importance in social networks[D]. Harbin: Harbin Engineering University, 2020. ] | |
[32] | 任晓龙. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13):1175-1197. |
[ Ren X L. Review of ranking nodes in complex networks. Scientific Bulletin, 2014, 59(13):1175-1197. ] | |
[33] | 张君. Internet路由级拓扑结构之k-核解析及其建模[D]. 沈阳:东北大学, 2009. |
[ Zhang J. K-shell parsing and modeling of internet routing level topology[D]. Shenyang: Northeastern University, 2009. ] | |
[34] |
Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2):026113.
doi: 10.1103/PhysRevE.69.026113 |
[35] | 陈仲毅. 网络聚类及可视化在线平台[D]. 北京:北京林业大学, 2019. |
[ Chen Z Y. Network clustering and visualization online platform[D]. Beijing: Beijing Forestry University, 2019. ] |
[1] | 曾璇, 崔海山, 刘毅华. 基于网络空间点模式的餐饮店空间格局分析[J]. 地球信息科学学报, 2018, 20(6): 837-843. |
[2] | 张恒才, 陆锋, 陈洁. 网络空间移动对象模型的应用与发展[J]. 地球信息科学学报, 2013, 15(3): 328-337. |
[3] | 董志良, 白翠玲. 河北省互联网发展的地理特征分析[J]. 地球信息科学学报, 2007, 9(4): 44-50. |
[4] | 蔡少华. 网络空间物流信息系统的分析与探讨[J]. 地球信息科学学报, 2002, 4(1): 104-107. |
[5] | 路紫, 白翠玲. 旅游网站的性能及其发展态势[J]. 地球信息科学学报, 2001, 3(1): 63-66. |
|