计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

基于k-core的大规模复杂网络压缩布局算法

李甜甜,卢罡,许南山,郭俊霞   

  1. (北京化工大学计算机科学与技术系,北京 100029)
  • 收稿日期:2015-04-24 出版日期:2016-05-15 发布日期:2016-05-13
  • 作者简介:李甜甜(1990-),女,硕士研究生,主研方向为复杂网络;卢罡(通讯作者),讲师、博士;许南山,副教授;郭俊霞,讲师。
  • 基金项目:
    北京高等学校青年英才计划基金资助项目(YETP0506)。

Compressing Layout Algorithm for Large Complex Network Based on k-core

LI Tiantian,LU Gang,XU Nanshan,GUO Junxia   

  1. (Department of Computer Science and Technology,Beijing University of Chemical Technology,Beijing 100029,China)
  • Received:2015-04-24 Online:2016-05-15 Published:2016-05-13

摘要:

为在复杂网络规模不断扩大的情况下优化其可视化布局效果,将力导引布局算法与k-core概念相结合,提出一种改进的大规模复杂网络压缩布局算法。利用复杂网络中的k-core概念划分网络数据,根据k-core值选择节点处理方式,实现网络节点的压缩布局。定义面向压缩的复杂网络信息量概念,对算法的压缩效果进行量化评估。实验结果表明,改进后的布局算法能有效利用有限的显示空间,减少布局结果中的边点密集现象,清晰地显示网络结构,同时在一定程度上保持原始网络性质。

关键词: 复杂网络, 可视化, 布局算法, 力导引算法, 压缩布局, k-核

Abstract:

In order to optimize the visual layout effect of complex network while they become larger,by combining force-directed algorithm and k-core concept,this paper proposes an improved compressing lay algorithm for large complex network.The nodes are divided into various categories by k-core concept in a complex network,and they are handled in different ways by different k-core values.In this way,the scale of network nodes is decreased.In addition,this paper gives the definition of the compression oriented complex network information,which is used to measure the compressing effect quantitatively.Experimental results show that the proposed algorithm can effectively use limited display space,reduce the overlapping phenomenon in layout result,show the structure of the network clearly,and maintain the original network information.

Key words: complex network, visualization, layout algorithm, force-directed algorithm, compressing layout, k-core

中图分类号: