基于互联网拓扑特征的多粒度社团发现算法及其可视化

来源 :东北大学 | 被引量 : 2次 | 上传用户:keliok
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,复杂网络的社团研究相对比较成熟,可针对以Internet拓扑结构为基础的社团特征研究至目前为止还是相对不足,并且没有文献从Internet特有的结构特征研究入手。系统的社团结构与其功能息息相关,对于Internet社团结构特征的深刻理解,可以帮助人们发现互联网新的功能单元、理解其复杂的网络特征结构、化简网络结构、寻找防治互联网病毒传播新策略、进行网络控制等。针对互联网特有的结构特征,如Internet网络边缘树状结构特征、Internet的链状特征(网络专线、BGP外部路由线路)、网络中局部区域高核数节点相互聚类特征、中心节点特征等,本文在互联网社团研究的过程中,通过对比传统的复杂网络的社团发现算法,总体上运用了分而划之、合而聚之的思想,分别设计了层次折叠收缩算法、链状探测算法、高核节点聚类特征探测算法、中心节点算法,通过这些算法,大致可以找出Internet基本的较小的功能组织结构,比如,层次折叠收缩算法可以探测到Internet网络边缘树状结构特征组织,链状探测算法可以探测到Internet网络专线、BGP外部路由线路等链状的结构特征组织,高核节点聚类探测算法可以探测到网络中局部区域高核数节点相互聚类特征组织,中心节点算法可以探测到Internet中心节点特征组织。通过这些探测算法,网络中的大部分节点都会被归类到相应的组织结构中去,可是还有一些少部分节点可能不在上述的几种特征组织内,上面的几种有针对性的探测算法就无法把它归类到相应的组织结构内,所以就把这些没有被探测到的每一个节点归为单独的组织结构(便于后续处理)。经过前面几步的处理,一个完整网络拓扑的大大小小的组织结构就呈现出来,下一步就需要把这些大大小的网络组织结构合并成为一个个具有高内聚低耦合特征的社团,这就是合而聚之。可是要使合并后的网络的社团模块度达到最优化是一个NP难题,在时间复杂度和空间复杂度上都比较大,对于具有众多较小组织结构的网络的社团模块度寻优处理,本文设计的小社团合并算法采用贪婪算法来寻找局部最优的模块度,最终一个具有典型社团结构划分特征的网络拓扑浮出水面。本文设计的社团发现算法由一组多粒度社团发现算法混合而成,称之为AY算法。目前在IPV6网络的社团发现方面:就社团划分质量的主流衡量标准模块度而言,AY算法微弱于fast unfolding of communities in large networks(简称FUOCILN)算法,在模块度评价方面,FUOCILN是目前国际上最优秀的算法这一,这也从侧面印证了AY算法在模块度评价标准上的优秀性;就多粒度特征而言,AY算法发现的社团内部包含多种不同粒度的互联网基本拓扑结构,而FUOCILN算法发现的社团内部只有节点信息,AY算法的社团内部信息容量要远大于FUOCILN。对于互联网的社团可视化问题,传统的一些可视化算法仅仅只能做到整个网络拓扑级别的可视化,社团结构的可视化特点并不明晰,针对这种问题,本文的可视化工作在参考传统节点布局方式的基础上全新构建节点布局,这种布局分为两个层次:整个网络的社团之间位置布局、每个社团的内部节点位置布局。其中,第一个层次又分两个小层次:其一,根据物理类比法,模拟物理系统环境,全自动布局社团节点;其二,在第一步完成之后,采用动态交互布局模式,如果第一步布局有不合理的地方,可手动调节社团节点位置。由于大规模数据的复杂性以及考虑了突出社团特征等问题,这必将牺牲画布资源。为此,本可视化算法开辟一个新的画布资源,采用射线布局算法显示某个特定社团内部节点的拓扑结构。鉴于本可视化算法的特点,称之为visualCommunity算法(简称VC)。VC算法能够合理清楚的可视化互联网的社团结构特征。
其他文献
人文精神是一个国家、一个地区的“内动力”,是最重要、最基础的“软实力”。一个国家、一个民族,如果没有现代科学,没有先进技术,一打就垮;而如果没有人文精神的凝聚和激励,不打自
目的:通过对《黄帝内经》(下简称《内经》)中腧穴名称、归经、主治以及相关针灸处方的梳理并做以分类比较,将《内经》中分散的腧穴理论予以归纳。考证《内经》中确切记载的腧穴数
目的观察卡培他滨及氟尿嘧啶作为胃癌术后同步放射治疗和化学治疗(放化疗)措施的近期不良反应、对患者生活质量的影响。方法术后病理分期符合同步放化疗指征的胃癌患者67例,
艺术具有形象性、真实性、审美性这三个特点,使得艺术可以成为大学生思想政治教育的载体。优秀的艺术作品可以发挥思想政治教育作用。本文从艺术的激励作用、感染作用、净化作
我国能源消费以煤炭为主,其中燃煤电厂消费的煤炭约占煤炭消费总量的50%。燃煤电厂是我国重要的大气污染物排放行业之一,其引发的区域雾霾和酸雨问题引起了广泛关注。针对燃
随着人们对生活环境要求的日益提高,我国园林工程项目越来越多,与此同时,园林建设市场竞争也日趋激烈,保持原有的利润空间越来越难。园林施工过程中的成本逐渐成为企业关注的
目的建立高效液相色谱法测定维库溴铵中的有关物质。方法色谱柱:DiamondC18(4.6mm×200mm,5μm),流动相:氯化铵溶液(取氯化铵1.6g,溶于8mL浓氨溶液中,加0.25mol·L-1高氯酸溶
在能源利用方式多样化和用电需求高标准化的形势下,提高微电网供电可靠性,保证其电能质量势在必行,而微电网系统谐波是影响其供电质量的主要原因之一。本文针对有效抑制微电网谐
以考古资料与田野调查相结合的方法研究云南少数民族传统纺织与纺织机械,在介绍云南传统纺织与纺织机械起源情况的基础上,指出了云南少数民族传统纺织的主要特点,分析了以纺
目的:研究精神病风险综合征与相关心理、社会因素间的关联性。方法:采用美国前驱期综合征标准(COPS)对收集的254例(年龄16-35岁)精神分裂症一级亲属进行筛选,符合精神病风险综合征的