留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

面向特征的网络空间点群要素自动综合方法

王映雪 李少梅 任丽秋 张鑫禄 张崇涛 张付兵

王映雪, 李少梅, 任丽秋, 张鑫禄, 张崇涛, 张付兵. 面向特征的网络空间点群要素自动综合方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(3): 427-433. doi: 10.13203/j.whugis20200002
引用本文: 王映雪, 李少梅, 任丽秋, 张鑫禄, 张崇涛, 张付兵. 面向特征的网络空间点群要素自动综合方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(3): 427-433. doi: 10.13203/j.whugis20200002
WANG Yingxue, LI Shaomei, REN Liqiu, ZHANG Xinlu, ZHANG Chongtao, ZHANG Fubing. Automatic Generalization Methods of Cyberspace Point Cluster Features Considering Characteristics[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3): 427-433. doi: 10.13203/j.whugis20200002
Citation: WANG Yingxue, LI Shaomei, REN Liqiu, ZHANG Xinlu, ZHANG Chongtao, ZHANG Fubing. Automatic Generalization Methods of Cyberspace Point Cluster Features Considering Characteristics[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3): 427-433. doi: 10.13203/j.whugis20200002

面向特征的网络空间点群要素自动综合方法

doi: 10.13203/j.whugis20200002
基金项目: 

国家自然科学基金 41771487

国家自然科学基金 41571399

河南省中原学者项目 202101510001

详细信息
    作者简介:

    王映雪,硕士,主要从事网络空间信息可视化方法的研究。wangyingxue26@163.com

    通讯作者: 李少梅,博士,教授。 lsalsm@163.com
  • 中图分类号: P283

Automatic Generalization Methods of Cyberspace Point Cluster Features Considering Characteristics

Funds: 

The National Natural Science Foundation of China 41771487

The National Natural Science Foundation of China 41571399

the Fund Project of Zhongyuan Scholar of Henan Province 202101510001

More Information
    Author Bio:

    WANG Yingxue, master, specializes in cyberspace information visualization. E-mail: wangyingxue26@163.com

    Corresponding author: LI Shaomei, PhD, professor. E-mail: lsalsm@163.com
  • 摘要: 网络空间信息可视化对揭示网络空域规律、促进网络空间认知具有重要意义。将网络空间节点与拓扑关系直接可视化的视图中存在大量的点重合和线交叉,目前已有的网络节点布局算法、集束边技术、骨干网提取和网络路由拓扑多尺度表达等方法能够优化视图效果,但在网络的微观结构上,对保持网络空间点群要素的特征信息关注不够。通过分析并量化网络空间点群要素的各类特征信息,提出了一种基于层次聚类的要素聚合方法和一种基于节点重要性度量的要素选取方法,以自动综合的方式对网络空间点群要素进行综合。实验结果表明,该方法能够保持网络空间点群要素的空间特征,为定量表达网络空间特征、加速生成视觉效果良好的网络空间地图提供基础数据综合方法。
  • 图  1  层次树结构

    Figure  1.  Structure of Hierarchical Tree

    图  2  模拟数据集可视化效果

    Figure  2.  Visualization Effect of Simulative Data Set

    图  3  自动综合结果

    Figure  3.  Automatic Generalization Results

    图  4  不同综合粒度下综合结果比较

    Figure  4.  Comparison of Generalization Results of Various Granularity

    表  1  点群特征信息含义及其定量描述因子

    Table  1.   Definitions and Quantitative Description Factors of Characteristic Information Combined in Point Clusters

    特征信息类型 含义 定量描述因子
    统计信息 $ V=\left\{{v}_{1}, {v}_{2}, {v}_{3}\dots \right\} $ 网络节点数
    度量信息 $ \mathit{A}=({a}_{ij}{)}_{n\times n} $ 各级社团所含节点的距离关系
    拓扑信息 $ E=\left\{{e}_{1}, {e}_{2}, {e}_{3}\dots \right\} $ 边两端的节点
    专题信息 $ P=v({p}_{1}, {p}_{2}, {p}_{3}\dots ) $ 节点属性及其管控范围
    下载: 导出CSV

    表  2  综合中保持各类特征信息的方式

    Table  2.   Methods for Maintaining Various Characteristic Information in Generalization

    类型 聚合算子 选取算子
    统计信息 将待综合点群划分为不大于地图描绘粒度的点簇,用各点簇聚类中心代表整个点簇 由待综合的节点总数与地图描绘点群要素的空间粒度的比值确定选取节点的数目
    度量信息 通过距离量算将聚合中心选取在各点簇内的度量中心 通过距离量算赋予节点介数中心性,作为评价节点结构重要性的参数之一
    拓扑信息 删除点簇内部拓扑关系,点簇内节点与外部所有拓扑关系转移至聚合中心节点 选取遵循基于结构重要性的"重要的点先被选取"以及"不同时删除互为拓扑节点的两个节点"的原则
    专题信息 聚合中心节点的专题信息为点簇内部节点专题信息的总和 选取遵循基于专题重要性的"重要的点先被选取"的原则
    下载: 导出CSV
  • [1] 李健霖. 地理信息约束的网络拓扑可视化方法研究与系统实现[D]. 成都: 电子科技大学, 2016

    Li Jianlin. Research on Visualization of Network Topology Under the Constraints of Geographic Location Information[D]. Chengdu: University of Electronic Science and Technology of China, 2016
    [2] Battista G D, Eades P, Tamassia R, et al. Algorithms for Drawing Graph: An Annotate Bibliography[J]. Computational Geometry: Theory and Applications, 1994, 4(5): 235-252 doi:  10.1016/0925-7721(94)00014-X
    [3] Selassie D, Heller B, Heer J. Divided Edge Bundling for Directional Network Data[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(12): 2 354-2 363 doi:  10.1109/TVCG.2011.190
    [4] 孙扬, 蒋远翔, 赵翔, 等. 网络可视化研究综述[J]. 计算机科学, 2010, 37(2): 12-18 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201002007.htm

    Sun Yang, Jiang Yuanxiang, Zhao Xiang, et al. Survey on the Research of Network Visualization[J]. Computer Science, 2010, 37(2): 12-18 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201002007.htm
    [5] 孙扬. 多变元网络数据可视化方法研究[D]. 长沙: 国防科学技术大学, 2010

    Sun Yang. Research on Multivariate Network Data Visualization[D]. Changsha: National University of Defense Technology, 2010
    [6] 常晓猛, 乐阳, 李清泉, 等. 利用位置的虚拟社交网络地理骨干网提取[J]. 武汉大学学报·信息科学版, 2014, 39(6): 82-86 doi:  10.13203/j.whugis20140105

    Chang Xiaomeng, Yue Yang, Li Qingquan, et al. Extracting the Geographic Backbone of Location-Based Social Network[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6): 82-86 doi:  10.13203/j.whugis20140105
    [7] 张龙. 网络资源测绘数据表达与分析技术研究[D]. 郑州: 信息工程大学, 2018

    Zhang Long. Research on the Technologies of Expression and Analysis for the Cyberspace Surveying and Mapping[D]. Zhengzhou: University of Information Engineering, 2018
    [8] 张倬. 基于地理位置信息约束的网络拓扑可视化方法研究[D]. 成都: 电子科技大学, 2015

    Zhang Zhao. Research on Visualization of Network Topology Under the Constraints of Geographic Location Information[D]. Chengdu: University of Electronic Science and Technology of China, 2015
    [9] 艾廷华. 适宜空间认知结果表达的地图形式[J]. 遥感学报, 2008, 12(2): 347-354 https://www.cnki.com.cn/Article/CJFDTOTAL-YGXB200802022.htm

    Ai Tinghua. Maps Adaptable to Represent Spatial Cognition[J]. Journal of Remote Sensing, 2008, 12(2): 347-354 https://www.cnki.com.cn/Article/CJFDTOTAL-YGXB200802022.htm
    [10] 闫浩文, 王邦松. 地图点群综合的加权Voronoi算法[J]. 武汉大学学报·信息科学版, 2013, 38(9): 1 088-1 091 http://ch.whu.edu.cn/article/id/2740

    Yan Haowen, Wang Bangsong. A MWVD-Based Algorithm for Point Cluster Generalization[J]. Geomatics and Information Science of Wuhan University, 2013, 38(9): 1 088-1 091 http://ch.whu.edu.cn/article/id/2740
    [11] 王兵. 复杂网络的节点重要性度量算法研究[D]. 南京: 南京邮电大学, 2015

    Wang Bing. The Research of Important Nodes Measuring Algorithm for Complicated Networks[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2015
    [12] 赵凤花, 杨波. 复杂网络节点重要性的综合评价方法[J]. 武汉理工大学学报(信息与管理工程版), 2015, 37(4): 461-464 https://www.cnki.com.cn/Article/CJFDTOTAL-WHQC201504017.htm

    Zhao Fenghua, Yang Bo. Comprehensive Evaluation on Identifying Key Nodes in Complex Networks[J]. Journal of Wuhan University of Technology (Information and Management Engineering), 2015, 37(4): 461-464 https://www.cnki.com.cn/Article/CJFDTOTAL-WHQC201504017.htm
    [13] Macqueen J. Some Methods for Classification and Analysis of Multivariate Observation[C]. The Fifth Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, California, USA, 1967
    [14] 黄继超. k_means算法若干改进和应用[D]. 长沙: 中南大学, 2013

    Huang Jichao. Improvement and Application of k_means Algorithm[D]. Changsha: Central South University, 2013
    [15] 任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014, 59(13): 15-37 https://www.cnki.com.cn/Article/CJFDTOTAL-KXTB201413004.htm

    Ren Xiaolong, Lü Linyuan. Review of Ranking Nodes in Complex Networks[J]. Chinese Science Bulletin, 2014, 59(13): 15-37 https://www.cnki.com.cn/Article/CJFDTOTAL-KXTB201413004.htm
    [16] 卜振兴. 复杂网络社团检测方法研究[D]. 北京: 中国人民公安大学, 2019

    Bu Zhenxing. Research on Community Detection Method of Complex Network[D]. Beijing: People's Public Security University of China, 2019
    [17] Rousseeuw P J. Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis[J]. Journal of Computational and Applied Mathematics, 1987, 20: 53-65
    [18] 龚江涛. 复杂网络节点重要性度量模型研究[D]. 武汉: 武汉理工大学, 2016

    Gong Jiangtao. The Research of Measurement Model About Complex Networks Node Importance[D]. Wuhan: Wuhan University of Technology, 2016
  • [1] 卢剑, 张学东, 张健钦, 郭小刚, 张悦颖.  利用卷积神经网络识别交通指数时间序列模式 . 武汉大学学报 ● 信息科学版, 2020, 45(12): 1981-1988. doi: 10.13203/j.whugis20200035
    [2] 程绵绵, 孙群, 李少梅, 徐立.  顾及密度对比的多层次聚类点群选取方法 . 武汉大学学报 ● 信息科学版, 2019, 44(8): 1131-1137. doi: 10.13203/j.whugis20180043
    [3] 鲍蕊, 薛朝辉, 张像源, 苏红军, 杜培军.  综合聚类和上下文特征的高光谱影像分类 . 武汉大学学报 ● 信息科学版, 2017, 42(7): 890-896. doi: 10.13203/j.whugis20150043
    [4] 梁栋, 王红平, 刘修国, 沈永林.  基于平面基元组的建筑物场景点云自动配准方法 . 武汉大学学报 ● 信息科学版, 2016, 41(12): 1613-1618. doi: 10.13203/j.whugis20140682
    [5] 田晶, 何青松, 颜芬.  道路网stroke生成问题的形式化表达与新算法 . 武汉大学学报 ● 信息科学版, 2014, 39(5): 556-560. doi: 10.13203/j.whugis20120127
    [6] 邓敏, 彭东亮, 刘启亮, 石岩.  一种基于场论的层次空间聚类算法 . 武汉大学学报 ● 信息科学版, 2011, 36(7): 847-852.
    [7] 翟仁健, 武芳, 朱丽, 王鹏波.  利用地理特征约束进行曲线化简 . 武汉大学学报 ● 信息科学版, 2009, 34(9): 1021-1024.
    [8] 焦利民, 刘耀林, 任周桥.  基于自组织神经网络的空间点群聚类及其应用分析 . 武汉大学学报 ● 信息科学版, 2008, 33(2): 168-171.
    [9] 蔡永香, 郭庆胜.  基于Kohonen网络的点群综合研究 . 武汉大学学报 ● 信息科学版, 2007, 32(7): 626-629.
    [10] 宋鹰, 何宗宜, 粟卫民.  基于Rough集的居民地属性知识约简与结构化选取 . 武汉大学学报 ● 信息科学版, 2005, 30(4): 329-332.
    [11] 刘志刚, 李德仁, 秦前清, 史文中.  基于特征空间中类间可分性的层次型多类支撑向量机 . 武汉大学学报 ● 信息科学版, 2004, 29(4): 324-328.
    [12] 吴凡, 祝国瑞.  基于小波分析的地貌多尺度表达与自动综合 . 武汉大学学报 ● 信息科学版, 2001, 26(2): 170-176.
    [13] 毋河海.  GIS环境下城市平面图形的自动综合问题 . 武汉大学学报 ● 信息科学版, 2000, 25(3): 196-202.
    [14] 毋河海.  地图信息自动综合基本问题研究 . 武汉大学学报 ● 信息科学版, 2000, 25(5): 377-386.
    [15] 邓德祥, 李玉林, 钟诚东.  组合逻辑自动综合的超前试探法 . 武汉大学学报 ● 信息科学版, 1997, 22(2): 160-162.
    [16] 郭庆胜, 颜辉武.  地形图综合对数字化的需求 . 武汉大学学报 ● 信息科学版, 1993, 18(S1): 23-26.
    [17] 费立凡, 郭庆胜.  地形图智能综合系统的设计 . 武汉大学学报 ● 信息科学版, 1993, 18(S1): 1-5.
    [18] 郭仁忠, 毋河海.  地形图上城镇居民地自动综合试验 . 武汉大学学报 ● 信息科学版, 1993, 18(2): 15-22.
    [19] 郭庆胜.  点状要素与线状、面状要素的关系处理 . 武汉大学学报 ● 信息科学版, 1993, 18(S1): 68-71.
    [20] 艾自兴.  河流自动综合方法 . 武汉大学学报 ● 信息科学版, 1993, 18(S1): 27-31.
  • 加载中
图(4) / 表(2)
计量
  • 文章访问数:  46
  • HTML全文浏览量:  10
  • PDF下载量:  13
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-04-14
  • 刊出日期:  2021-03-05

面向特征的网络空间点群要素自动综合方法

doi: 10.13203/j.whugis20200002
    基金项目:

    国家自然科学基金 41771487

    国家自然科学基金 41571399

    河南省中原学者项目 202101510001

    作者简介:

    王映雪,硕士,主要从事网络空间信息可视化方法的研究。wangyingxue26@163.com

    通讯作者: 李少梅,博士,教授。 lsalsm@163.com
  • 中图分类号: P283

摘要: 网络空间信息可视化对揭示网络空域规律、促进网络空间认知具有重要意义。将网络空间节点与拓扑关系直接可视化的视图中存在大量的点重合和线交叉,目前已有的网络节点布局算法、集束边技术、骨干网提取和网络路由拓扑多尺度表达等方法能够优化视图效果,但在网络的微观结构上,对保持网络空间点群要素的特征信息关注不够。通过分析并量化网络空间点群要素的各类特征信息,提出了一种基于层次聚类的要素聚合方法和一种基于节点重要性度量的要素选取方法,以自动综合的方式对网络空间点群要素进行综合。实验结果表明,该方法能够保持网络空间点群要素的空间特征,为定量表达网络空间特征、加速生成视觉效果良好的网络空间地图提供基础数据综合方法。

English Abstract

王映雪, 李少梅, 任丽秋, 张鑫禄, 张崇涛, 张付兵. 面向特征的网络空间点群要素自动综合方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(3): 427-433. doi: 10.13203/j.whugis20200002
引用本文: 王映雪, 李少梅, 任丽秋, 张鑫禄, 张崇涛, 张付兵. 面向特征的网络空间点群要素自动综合方法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(3): 427-433. doi: 10.13203/j.whugis20200002
WANG Yingxue, LI Shaomei, REN Liqiu, ZHANG Xinlu, ZHANG Chongtao, ZHANG Fubing. Automatic Generalization Methods of Cyberspace Point Cluster Features Considering Characteristics[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3): 427-433. doi: 10.13203/j.whugis20200002
Citation: WANG Yingxue, LI Shaomei, REN Liqiu, ZHANG Xinlu, ZHANG Chongtao, ZHANG Fubing. Automatic Generalization Methods of Cyberspace Point Cluster Features Considering Characteristics[J]. Geomatics and Information Science of Wuhan University, 2021, 46(3): 427-433. doi: 10.13203/j.whugis20200002
  • 网络空间地图使用形象化的视觉语言描绘网络空间信息,对揭示网络空域规律,促进网络空间认知具有重要意义。由于网络空间节点及节点间拓扑关系固有的层级性和社团特征[1],直接可视化的结果中往往存在大量的点重合和线交叉,造成严重的视觉混淆,降低图面利用率和信息传递效率。

    目前,解决点重合和线交叉问题的方法和技术有网络节点布局算法[2]、集束边技术[3]和边融合及路由技术[4-5]等,通过这些方法可以得到符合美学要求的网络节点及拓扑关系的可视化视图,但忽略了网络的空间特征。常晓猛等[6]基于融合重力模型和信息熵技术对个体间、城市间的社交关系进行聚合和提取,以获取虚拟网络的骨干网;张龙[7]基于自适应R-TREE索引与调度方法和k -核的地理约束实现了网络路由拓扑多尺度表达。以上方法关注空间特征,但地理单元的约束使网络空间自身特征难以充分表达,对网络的微观结构(网络节点的特征信息)关注不够。李健霖[1]、张倬[8]基于现有网络可视化技术,面向全球互联网拓扑布局提出了基于地理信息约束的改进力导引拓扑布局算法,表达网络结构特征的同时,顾及与地理空间的联系,但在单一尺度下图面要素过多,影响了特征信息的传递效率。从认知的角度出发,由于网络空间的虚拟性和不可量算性,网络空间地图常被视为一种定性的可视化表达技术[9]。为了最终能够基于实时更新的网络空间数据,快速生成经过可视化处理、符合地图设计规律、具有交互分析功能的网络空间地图,需要对网络空间要素进行定量的自动综合处理。本文将地理信息科学和网络科学中的相关概念与研究方法拓展到网络空间,赋予网络空间可量算性,以此为基础,研究网络空间点群要素的自动综合方法。

    • 网络空间由依附于真实地理世界的网络基础设施和存在于虚拟网络世界的信息资源组成,可划分为终端设备、交换设备、传输介质、虚拟主体和信息数据5类要素,并依照要素空间特征抽象为实体点要素、实体线要素、虚拟线要素、虚拟点要素和多维无形态要素。其中,实体点要素(终端设备和交换设备)和虚拟点要素(虚拟主体)是网络空间的点状要素,要素间具有较强的分级拓扑关系,整体上符合点群要素的空间分布模式,具有微观上的层级性和宏观上的社团性,反映了不同尺度下点状要素的空间特征。将网络空间点群要素描绘在网络空间地图上,需要进行要素的综合处理。为保证综合前后不同尺度下网络空间特征信息的传播,本文借鉴地理空间要素特征信息的划分方法[10],将网络空间点群要素的空间特征信息划分为统计信息、度量信息、拓扑信息和专题信息,以便定量研究点群要素空间特征的尺度依赖性。

    • 明确网络空间特征信息的含义是选择定量描述因子的前提,本文引入网络科学中的相关概念,将地理空间特征信息的内涵延伸到网络空间。

      网络拓扑图记为$ G\left(V, E\right) $,其中,$ V=\left\{{v}_{1}, {v}_{2}, {v}_{3}\dots \right\} $为网络节点集合,$ E=\left\{{e}_{1}, {e}_{2}, {e}_{3}\dots \right\} $为边的集合[10]。统计信息的含义同地理空间要素类似,描述网络空间点群要素的数量特征,即节点集合$ V $的体积。由于网络空间作为非欧氏空间不存在类似于地理空间中的距离和方向的概念,因此,需要重新定义度量信息和拓扑信息的含义。不同于地理空间要素间基于确定空间位置的欧氏距离,网络空间的度量信息描述的是要素在网络中的距离,即节点间最短路径包含的边数[11]与网络结构密切相关。以任意两节点为端点构成的边$ e\left({v}_{i}, {v}_{j}\right) $作为网络空间的一条拓扑关系,边的集合$ E $即为网络空间的全部拓扑信息。专题信息除涵盖节点本身属性信息外,主要包括网络赋予的职责属性,即管控范围。各类特征信息的含义及定量描述因子如表 1所示。

      表 1  点群特征信息含义及其定量描述因子

      Table 1.  Definitions and Quantitative Description Factors of Characteristic Information Combined in Point Clusters

      特征信息类型 含义 定量描述因子
      统计信息 $ V=\left\{{v}_{1}, {v}_{2}, {v}_{3}\dots \right\} $ 网络节点数
      度量信息 $ \mathit{A}=({a}_{ij}{)}_{n\times n} $ 各级社团所含节点的距离关系
      拓扑信息 $ E=\left\{{e}_{1}, {e}_{2}, {e}_{3}\dots \right\} $ 边两端的节点
      专题信息 $ P=v({p}_{1}, {p}_{2}, {p}_{3}\dots ) $ 节点属性及其管控范围
    • 综合算子是最小综合功能的抽象描述,对要素的某个单独方面以不可再分的方式形成影响,进而不同程度保持各类特征信息。借鉴地理空间点群要素的综合方法[12],本文将聚合算子和选取算子用于网络空间点群要素的综合,如表 2所示。它们通过以下方式保持统计信息、度量信息、拓扑信息和专题信息在不同尺度下的传递。由于点群要素的聚合应基于网络的各级社团结构,在此基础上的选取有助于保持网络的真实结构,因而,本文按照先聚合再选取的顺序研究算子实现方法并进行相关实验。

      表 2  综合中保持各类特征信息的方式

      Table 2.  Methods for Maintaining Various Characteristic Information in Generalization

      类型 聚合算子 选取算子
      统计信息 将待综合点群划分为不大于地图描绘粒度的点簇,用各点簇聚类中心代表整个点簇 由待综合的节点总数与地图描绘点群要素的空间粒度的比值确定选取节点的数目
      度量信息 通过距离量算将聚合中心选取在各点簇内的度量中心 通过距离量算赋予节点介数中心性,作为评价节点结构重要性的参数之一
      拓扑信息 删除点簇内部拓扑关系,点簇内节点与外部所有拓扑关系转移至聚合中心节点 选取遵循基于结构重要性的"重要的点先被选取"以及"不同时删除互为拓扑节点的两个节点"的原则
      专题信息 聚合中心节点的专题信息为点簇内部节点专题信息的总和 选取遵循基于专题重要性的"重要的点先被选取"的原则
    • 网络空间点群要素具有明显的社团性和层级性,当要素过多无法全部表示在网络空间地图上时,需要进行综合面向空间特征表达。点群要素聚合的主要思路为:首先,基于距离度量节点的相似性并通过层次聚类将网络空间点群要素聚集为体积适宜的点簇;然后,使用各聚类中心点代表点簇集合,将点群要素聚合为点簇中心一点。使聚合结果既能保持点群要素的度量特征,又能迅速降低图面的要素过多造成的视觉混淆。以下通过设计自适应层次模型,选择合适的聚类方法,研究一种基于层次聚类的网络空间点群要素聚合方法。

    • 基于自适应层次模型的聚类能够以上层聚类得到的类簇为新的待聚类点集,逐层细化地划分网络空间点群并提取聚类中心点。模型的层次树结构如图 1所示。

      图  1  层次树结构

      Figure 1.  Structure of Hierarchical Tree

      每次向下聚类相当于将父节点代表的点簇划分为若干子点簇,直到所有子点簇体积小于预设阈值则停止继续向下聚类,阈值的设定主要参考地图描绘点群要素的空间粒度。该模型能够在不改变外观算法的前提下,通过阈值的调整,控制最终聚类结果中类簇的体积,进而使聚合的结果反映网络空间要素不同详细程度的细节信息。

    • 在构建自适应层次模型的基础上,需要选取适用于各级点簇的点群要素聚类算法。K-means聚类[13]作为一种原理简单、运算迅速的无监督分类算法,对处理大量数据具有较好的可伸缩性[14],是一种常用的社团发现算法。该算法有两个使用前提:(1)任意两点距离可求且具有交换性;(2)点群均值中心可求。本文仅研究构成无向连通网络的点群要素的综合,网络节点的相似度可使用节点间最短路径长度作为度量依据。因此,网络拓扑图的距离矩阵对称,具有可交换性。计算位于复杂网络中心位置的节点,可以利用节点的接近中心性[11-12, 15],该指标定义为节点到网络中其他所有节点的距离倒数之和,节点$ i $的接近中心性$ {C}_{i} $为:

      $$ {C}_{i}=\sum _{j=1}^{N}\frac{1}{{d}_{ij}} $$ (1)

      式中,$ {d}_{ij} $表示节点对$ \left(i, j\right) $最短距离;$ {C}_{i} $越大,表示节点$ i $越居于复杂网络的中心位置。综合以上分析,该算法可用于网络空间点群要素的聚类。

    • K-means聚类算法的基本过程为:(1)确定点簇的个数K并为各点簇指定初始中心点;(2)将待聚类的所有节点划分到距离最近的中心点代表的点簇中,并重新计算各点簇的中心点;(3)重复执行步骤(2), 直到各点簇的中心点不再有显著变动则完成聚类。

      聚类时,初始中心点的选取和K值的确定对聚类结果有很大的影响[16]。由于网络空间点群要素具有明显的金字塔形分级结构,上下级节点的责任关系明确,并且点集体积呈指数级增长,为避免误选离群点作为初始中心点,影响聚类结果中各点簇体积的平衡,本文基于节点的接近中心性,选取位于整个网络上层的K个中心节点作为聚类的初始中心点,同时,使用轮廓系数[17]作为评价聚类结果的指标以确定最佳K值。节点$ i $的轮廓系数$ S\left(i\right) $表示为:

      $$ S\left(i\right)=\frac{b\left(i\right)-a\left(i\right)}{\mathrm{m}\mathrm{a}\mathrm{x}\left(a\left(i\right), b\left(i\right)\right)} $$ (2)

      式中,$ a\left(i\right) $是节点$ i $和其所在点簇内的所有其他节点距离的平均值,用于量化簇内凝聚度;$ b\left(i\right) $是节点$ i $和与其距离最近的点簇中所有节点的平均距离,用于量化簇间离散度,所有待聚合节点轮廓系数的平均值即为聚类结果的整体轮廓系数。聚类由$ K=2 $开始,每次增加1,直到整体轮廓系数第一次减小,将$ K-1 $作为最佳聚类点簇数,对应的点簇集合为最佳聚类结果。

    • 度量复杂网络中节点的重要性有助于从微观角度分析复杂系统的结构与功能。网络空间作为一种典型的复杂网络,当其中的点群要素经聚合处理生成的较小点集仍无法全部表达在地图上时,可按照"越重要的点,越容易被保留"的原则进行选取。

    • 网络节点重要性分为稳定结构和区域管控两个方面。本文基于复杂网络节点重要性评价指标和节点负责的地理区域范围分别量化网络节点的结构重要性和管控重要性。

    • 度中心性和基于距离度量的介数中心性是评估复杂网络节点结构重要程度的两个重要指标,分别反映节点在网络中的局部属性和全局属性[12, 18]。在节点数目为$ N $的网络中,节点$ i $的度中心性$ {D}_{i} $是节点度数$ {d}_{i} $与节点可能连接的最大边数的比率,计算公式为:

      $$ {D}_{i}={d}_{i}/(N-1) $$ (3)

      $ {D}_{i} $数值越大,表示节点在局部网络中越重要。节点$ i $的介数中心性$ {B}_{i} $定义为:网络中所有节点对间的最短路径中经过节点$ i $的路径数目占最短路径总数的比例之和。$ {B}_{i} $计算公式为:

      $$ {B}_{i}=\frac{\sum _{j\ne i\ne k}^{}\left({f}_{\left(m, n\right)}\right(i)/{n}_{(j, k)})}{N(N-1)/2} $$ (4)

      式中,$ {n}_{(j, k)} $表示节点对$ (j, k) $间存在的最短路径数目,经过节点$ i $的最短路径数目为$ {f}_{\left(m, n\right)}\left(i\right) $。式(4)为节点介数中心性的标准化表示,$ {B}_{i} $占比越大,表示该节点在网络中的影响力越大。度中心性和介数中心性均满足$ {D}_{i}\mathrm{、}{B}_{i}\in \left[\mathrm{0, 1}\right] $。

      度中心性和介数中心性分别从不同的角度量化了节点的重要程度。为了同时发挥两个单一指标在描述网络空间节点结构重要性时具备的特点和优势,将两个指标综合,定义了评估节点结构重要性的指标(结构指数$ I $)。节点$ i $的结构指数$ {I}_{i} $为:

      $$ {I}_{i}=({{D}_{i}}^{2}+{{B}_{i}}^{2}{)}^{\frac{1}{2}} $$ (5)
    • 管控范围是网络节点的主要专题属性。由于网络空间节点的管控重要性与其依附的地理空间密切相关,Voronoi图常用于衡量点要素的图面几何重要性[10],故基于网络点群要素的空间位置进行三角剖分并生成各节点的Voronoi多边形,可代表该节点影响的地理空间区域,如各级路由负责转发的地区范围或无线信号的覆盖范围等。定义管控指数$ R $作为量化节点管控重要性的评估指标,节点数目为$ N $的网络中节点$ i $管控指数$ {R}_{i} $表示为:

      $$ {R}_{i}=\frac{{S}_{i}}{\sum _{i=1}^{N}{S}_{i}} $$ (6)

      式中$ , {S}_{i} $是节点$ i $的Voronoi多边形面积。

    • 本文将构成拓扑关系的两个节点互称为拓扑节点,选取网络节点的同时必然关联着拓扑关系的选取,为保持要素的拓扑特征信息,在选取过程中尽量遵循"不同时删除互为拓扑节点的两个节点"的原则。以节点数目为$ N $的网络为例,选取$ {N}_{S} $个节点的过程如下:

      1) 基于网络节点重要性度量结果,计算待综合节点的选取概率。由$ T $个节点聚合而成的新节点$ j $的选取概率$ {P}_{j} $表示为:

      $$ {P}_{j}=\sum _{i=1}^{T}({\alpha }_{1}{R}_{i}+{\alpha }_{2}{F}_{i}) $$ (7)

      式中$ , {\alpha }_{1} $和$ {\alpha }_{2} $分别表示结构指数$ {I}_{i}\left(1\le i\le T\right) $和管控指数$ {R}_{i} $在评估节点综合重要性时的权重。

      2) 使用状态标记的方法辅助节点选取[12],将待选取节点的初始状态标记为"自由"。

      3) 从选取概率最小的自由节点开始遍历,若其所有拓扑节点都是"自由"的,则将此节点状态标记为"删除",并"固定"其拓扑节点。每标记一次"删除",当前删除节点数目$ {N}_{d} $增加1,若$ {N}_{d}=N-{N}_{S} $,则停止遍历,直接进入步骤5);否则,继续遍历,直到待选取节点中没有自由节点时,结束本轮选取。

      4) 将状态为"固定"的节点更新为"自由"状态,返回步骤3)。

      5) 选取状态为"自由"和"固定"的所有节点,重新构建选取节点的拓扑关系。

    • 本文基于CAIDA(Center for Applied Internet Data Analysis)提供的IP(internet protocol)定位数据和互联网拓扑数据,依据网络空间结构特征将其补充完善为完整性和精度均满足实验需求的网络空间数据,并用于模拟实验。

    • 模拟数据集包含的节点数目nv为942,边的数目nE为1 016,实验前依据需要确定地图描绘点群的空间粒度,将其设置为聚类阈值$ T $,并计算综合后地图上保留的要素点数$ {N}_{S} $为:

      $$ {N}_{S}=\left[\frac{nV}{T}\right]+1 $$ (8)

      实验按照先聚合、后选取的顺序主要分为以下4个步骤:(1)基于自适应层次模型对网络空间点群要素进行最优K-means聚类;(2)将聚类得到的点簇进行聚合处理,并重新构建拓扑关系,得到新的待综合点群;(3)依据数据实际情况设置结构重要性和管控重要性的权重,评价节点综合重要性,经实验,在评价本数据中节点综合重要性时,结构重要性和管控重要性的权重相等;(4)基于节点的综合重要性,并顾及点群的拓扑信息,进行选取处理。模拟数据集可视化效果如图 2所示。在不同空间粒度下进行多组聚合和选取实验,结果如图 3所示。

      图  2  模拟数据集可视化效果

      Figure 2.  Visualization Effect of Simulative Data Set

      图  3  自动综合结果

      Figure 3.  Automatic Generalization Results

    • 不同空间粒度(聚类粒度)下的聚合和选取结果图 4所示。

      图  4  不同综合粒度下综合结果比较

      Figure 4.  Comparison of Generalization Results of Various Granularity

      聚合点比例为聚合后节点数与实际节点总数的比值。从图 4可以看出,聚合处理可以大幅综合原始点群要素,整体上聚类粒度越大,聚合效率越高。当空间粒度为90时,达到最高聚合效率98.0%。选取点比例为依据式(8)确定的选取点数目占聚合后节点数目的比例。

      图 4可以看出,聚合后进一步选取的比例最低仅为35.2%。虽然基于阈值T的聚类结果进行聚合处理已大幅综合了原始点群要素,但聚合后节点数目相较预设空间粒度下计划保留的节点数目仍然较多。当空间粒度为50、100时,聚合后保留的节点数目甚至超越了较小聚类粒度时的聚合点数。主要原因是基于自适应层次模型的最佳K-means聚类无法将点群要素均匀划分为体积大小相当的点簇,这与各级网络本身的统计特征相关。

      本文将聚合与选取结果同实验数据集进行对比,可以总结出以下几种情况下的节点在综合后更容易被保留:(1)位于各级网络社团的中心;(2)位于网络结构的较高层次;(3)构成关键的网络拓扑路径;(4)位于节点稀疏区,负责较大的管控区域。整体上,综合结果能够较好地保持网络空间点群要素的各类空间特征。

    • 本文借鉴网络科学和地理信息科学的概念与方法,从微观角度对其网络空间点群要素的各类特征信息进行分析并量化,提出了一种基于层次聚类的要素聚合方法和一种基于节点重要性度量的要素选取方法,并通过构建模拟数据进行了实验。实验结果表明,本文提出的综合方法能够保持网络空间点群要素的空间特征,为加速从获取网络空间数据到生成可视化视图的过程,优化可视化视图视觉效果,定量表达网络空间特征,提供了基础数据处理方法。

参考文献 (18)

目录

    /

    返回文章
    返回