论文部分内容阅读
实际社会中的复杂系统要么以复杂网络的形式存在,要么可以通过某种形式的转换而变为复杂网络。而传统的利用数字和表格的形式来组织数据的方式,使得人们很难对复杂网络有整体上的认识。复杂网络可视化技术可以有效地展现网络的结构,使得人们可以从中及时获取有用的信息来加以利用。而由于信息社会的高速发展,所产生的数据也越来越多,复杂网络的规模在急剧增长,严格按照布局算法来对网络进行可视化变得越来越困难。一方面由于计算机性能的限制,导致其在应对大量的数据时不能有效地对节点进行布局,导致大量节点的重叠和边的交叉;另一方面,在结果展示的图上节点太多,会严重影响人们的观察,也就无法从其中获取任何有用信息了。因此,诞生了可视化压缩算法。可视化压缩算法的目标就是对网络的节点和边进行删除操作,这样做的目的是为了更好地展示网络的拓扑结构,便于人们更好地去理解它,以挖掘网络所包含的有用信息。众所周知,实际社会中的复杂网络的度分布都比较好地满足幂律分布,即大部分节点的度比较小,只有极少部分节点的度比较大。而这些具有较较小度的节点中,大部分的节点都属于不那么重要的节点,其存在与否对网络的整体拓扑结构影响不大。可视化压缩算法的做法就是删除重要程度不高的节点。本文设计了一个复杂网络压缩算法,该压缩算法的主要操作有节点的合并和节点的删除。节点的删除操作所依据的是节点的重要性程度,本文采用PageRank值来表示节点的重要性程度。复杂网络普遍存在社区结构的特性,所以节点的重要性程度也具有相对性。因此算法先利用基于标签传播的RAK社区挖掘算法对网络进行社区划分,然后以社区为单位来对节点进行删除。节点删除时,考虑到原网络的连通性,还要适当地进行边的添加。由于复杂网络的节点规模巨大,为了满足快速和准确的要求,采用了GraphLab并行框架。本文实现了上述的复杂网络压缩算法,且其中的PageRank值的计算及社区划分都是基于GraphLab框架的实现。通过在实际数据集上进行测试,来验证在GraphLab框架下的PageRank算法和RAK算法的准确性及高效性,同时测试本文的压缩算法。通过检验压缩后的网络的度分布,发现其仍满足幂律的特性,说明了压缩算法的有效性。最后展示了压缩效果。