基于社团结构的网络空间复杂网络多尺度构建算法.pdf
《基于社团结构的网络空间复杂网络多尺度构建算法.pdf》由会员分享,可在线阅读,更多相关《基于社团结构的网络空间复杂网络多尺度构建算法.pdf(6页珍藏版)》请在咨信网上搜索。
1、收稿日期:修回日期:基金项目:国家自然科学基金青年科学基金资助项目()作者简介:胡 涛()男硕士生主要研究方向为时空大数据分析与可视化:/基于社团结构的网络空间复杂网络多尺度构建算法胡 涛 李 响 王丽娜 芦鹏飞(.信息工程大学河南 郑州 .郑州轻工业大学河南 郑州)摘要:网络空间要素及要素间关系构成的复杂网络进行可视化对感知网络结构和发现网络空间规律具有重要意义 针对网络空间复杂网络可视化时出现的大量节点和连边相互压盖造成的视觉混乱问题和基于层次聚类思想的社团划分算法构建的多尺度网络只能得到有限的尺度问题提出一种基于社团结构的网络空间复杂网络多尺度构建方法 该方法基于改进的 社团发现算法结合
2、节点综合重要性进行社团核心节点的选取和依据社团间连边数量设定阈值建立重要节点不同层次连边通过调整参数实现网络空间复杂网络多尺度构建 实验结果表明该方法在构建多尺度网络过程中能够保留网络空间中的重要节点相较于基于层次聚类思想的 社团发现算法能够发现更多尺度的网络结构且具有较好的连续性关键词:网络空间社团结构 社团发现算法节点重要性多尺度构建中图分类号:.文献标识码:文章编号:().第 卷第 期 年 月信 息 工 程 大 学 学 报 .引言网络空间中包含着海量的网络基础设施等实体要素及软件系统、账号、数据等虚拟要素各网络要素节点之间交错相连由此形成了网络空间中的复杂网络 地理空间作为网络空间实体资
3、源与实体角色的载体使得网络空间中的复杂网络不仅具有一般复杂网络的社团特性和层次结构还赋予其明显的地理特征即网络节点具有对应的地理位置 在对网络空间复杂网络可视化时由于屏幕尺寸限制会出现大量网络节点和高密度连边相互压盖造成视觉混乱问题从而难以识别和感知网络的整体结构、发现网络空间规律当前主要通过节点布局算法、边捆版算法、构建多尺度网络等方法解决大量节点和连边相互压盖造成的视觉混乱问题 布局算法主要是从美学原则出发通过调整节点位置缓解节点相互压盖问题 尽管张政等提出了空间位置耦合的网络布局算法但仍不可避免需要改变大量的节点位置而网络空间节点对应具体的网络设备及相应的地理位置节点位置的改变可能造成认
4、知偏差 边捆版算法主要是将方向、位置、尺度相似的连边划归到同一聚类簇从而减少视觉混乱尽管各种边捆版算法保持了网络节点位置不同程度上减少了视觉混乱但单一尺度的连边优化较难完全发现网络空间规律 构建多尺度网络方法通过将网络空间拓扑网络压缩化简为不同尺度网络展现不同尺度下的网络结构挖掘网络空间规律祝振凯依据网络资源设备重要性建立不同尺度路由器网络张龙提出基于 核的地理约束下的网络路由器拓扑多尺度表达但划分的尺度较为粗糙 王续盘等提出基于 和 核分解混合算法的多尺度表达模型但基于层次聚类思想的 社团划分算法只能得到有限的划分层次从而只能观察到有限尺度的网络结构对网络尺度挖掘仍有不足伴随着网络空间测绘技
5、术快速发展网络设备的定位精度不断提高使得在地图上绘制网络空间中的复杂网络成为了可能 在以往基于地图的网络空间可视化研究中多数将行政区划级别与不同层次网络相对应绘制了国家、省、市等地理尺度下的拓扑网络 文献尝试将构建的多尺度拓扑网络与地图层级对应后将多尺度拓扑网络映射在地图上但受限于算法只能获取有限尺度的拓扑网络对基于地图的多尺度网络可视化仍需进一步探索针对上述问题本文提出基于改进的 社团发现算法将复杂网络划分为多层次社团后利用节点综合重要性选取社团中的核心节点并依据社团间的连边数量设置阈值建立核心节点间不同层次连边从而建立一种基于社团结构的复杂网络多尺度构建算法 网络空间复杂网络多尺度构建算法
6、.社团发现算法 社团发现算法是基于适应度函数局部最优化的思想实现网络社团划分能够同时发现网络的社团结构和层次结构其适应度函数定义为()()式中:和 分别代表社团内部度与外部度表示社团 内部节点的节点度之和是与社团内部节点有连接的外部节点个数 是控制发现社团大小的超参数一般取值为.到.之间 越大发现的社团越小 越小发现的社团越大算法分为种子节点的选取和扩展两部分首先随机选取种子节点作为初始社团然后计算该社团节点所有邻居节点的适应度增量将适应度最大且大于零的节点添加到社团实现社团的扩展 适应度增量表示为 ()式中:表示添加节点 前后的适应度增量表示添加节点之后的社团的适应度表示未添加节点 社团 的
7、适应度 社团发现算法存在两处不足及改进:)算法中随机选取种子节点造成了社团划分结果存在不稳定问题 由于节点度值衡量节点重要性存在简单直观、方便计算等优点本文选择节点度值最大的节点作为种子节点从而消除了 算法不稳定的问题得到稳定的社团划分结果)社团发现算法每扩展添加一个节点后会重新遍历该社团所有节点适应度增量导致计算量剧增使得产生效率偏低问题 本文提出“先扩展再检验”的思路先在节点迭代扩展中将每一次适应度增量最大且大于 的节点添加到社团后再统一进行社团适应度检验统一删除适应度增量小于 的节点避免了社团扩展中每添加一个节点就遍历一次社团所有节点所带来的计算量剧增导致的效率偏低问题改进后的 算法如图
8、 所示 第 期胡 涛等:基于社团结构的网络空间复杂网络多尺度构建算法图 改进的 社团发现算法流程.基于节点综合重要性的社团核心节点选取.网络节点结构重要性度量方法节点度值是网络空间节点局部重要性度量方法之一表示与节点 相连接的节点个数具体公式为()()式中表示网络节点间的连接关系当两个节点之间有连接时表示为 否则表示为()为 节 点 介 数 中 心 性()定义为网络中所有节点对间的最短路径中经过节点 的路径数占最短路径总数的比例之和常用来表示节点在全局网络的影响能力公式为()()()式中:表示节点 到节点 之间最短的路径数表示节点 和节点 之间经过节点 之间的最短路径数 为节点个数.网络节点位
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 社团 结构 网络 空间 复杂 尺度 构建 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。