Blondel和k-核分解混合算法相结合的网络空间点群要素多尺度模型构建

doi:10.12082/dqxxkx.2021.210397

摘要/Abstract

摘要：

随着人们对网络空间的依赖性不断增强,互联网技术与网络基础设施规模迅速发展。很难直接用数字或表格的形式对网络空间进行全局的规划与管理,并且不容易发现隐藏在网络空间中的一些关键信息。网络空间点群要素的多尺度模型构建对网络空间数据的多尺度分析和可视化具有非常重要的意义。本文以网络空间的特征为依据,在借鉴基于社团划分的网络空间分层算法和基于节点重要性的网络空间分层算法特点的基础上,提出了Blondel算法和k-核分解的混合算法相结合的网络空间点群要素多尺度模型构建算法。本算法通过自动社团划分,用同一社团内的节点合并构建新的网络,有效解决了基于节点重要性的网络空间分层算法自动化程度低的弊端。利用核心节点来代替整个社团结构,显著保留了网络空间中节点的属性。实验表明使用该算法可以使各个层次网络空间点群要素的综合比例降至30%以下,较好的实现了网络空间点群要素的聚类与分层,若将网络空间点群要素的多尺度模型应用于地理空间中,则可实现网络空间地图的多尺度绘制。

关键词: 多尺度模型, 多尺度模型, 网络空间, 网络空间, 社团划分, 社团划分, 节点的重要性, 节点的重要性, Blondel算法, Blondel算法, k-核分解, 点群要素, 网络空间地图, k-核分解, 点群要素, 网络空间地图

Abstract:

In the 21st century, with the increasing dependence of people on cyberspace, Internet technology and network infrastructure develop rapidly. The elements that make up the cyberspace are complex and the data of nodes are large. It is difficult to directly use the form of numbers or tables for the overall planning and management of cyberspace, and it is not easy to find some key information hidden in cyberspace. So it is very important to construct a multi-scale model of point group elements in cyberspace for multi-scale analysis and visualization of data in cyberspace. If the nodes and topological relations in the cyberspace are directly visualized, a large number of points overlap and lines cross, resulting in the confusion of the information in the cyberspace. In this paper, based on the community and hierarchical characteristics of cyberspace, and referring to the characteristics of cyberspace stratification algorithm based on community division and cyberspace stratification algorithm based on node importance, a multi-scale model building algorithm of point group elements in cyberspace is proposed, which combines Blondel algorithm and K-shell decomposition hybrid algorithm. By automatic community division and combining nodes in the same community to build a new network, this algorithm effectively solves the problem of low automation degree of cyberspace stratification algorithm based on node importance. Core nodes in the cyberspace are extracted by k-shell decomposition hybrid algorithm. Core nodes are used to replace the whole community structure, which significantly retains the attributes of nodes in the cyberspace. For example, basic attributes such as the number, importance, and geographical location of nodes in the cyberspace. Experiments show that this algorithm can make the comprehensive proportion of each level of network space point group elements less than 30%, and achieve the clustering and stratification of network space point group elements. Compared with Blondel's algorithm, it is found that the proposed algorithm can preserve the hierarchy of network space with a high degree of importance. The multi-scale model of cyberspace point group elements is applied to geographic space which reduces the consumption of system resource, and the map of network space is realized. The multi-scale model of cyberspace can provide a data synthesis method for generating multi-scale cyberspace map. The different levels divided by this algorithm have different node numbers and edge numbers. The multi-scale model of point group elements can also provide node data with different levels of detail, which provides the basis for multi-scale analysis of network space.

Key words: multi-scale model, cyberspace, community division, importance of nodes, blondel algorithm, k-shell decomposition, point group element, map of cyberspace, multi-scale model, cyberspace, community division, importance of nodes, blondel algorithm, k-shell decomposition, point group element, map of cyberspace

王续盘, 张衡, 周杨, 胡校飞, 彭杨钊, 齐凯. 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

图/表 12

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

参考文献 35

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