大图采样方法综述EI北大核心CSCD

大图采样是常用的网络图简化方法,可显著降低大图数据的规模.文中从随机图采样、特征驱动的大图采样方法、大图采样的评估指标和大图采样方法的应用4个角度进行综述.首先介绍随机点、随机边和随机游走的随机图采样方法;然后论述拓扑结构、社区结构、动态网络关联和语义关联特征驱动的大图采样方法;再介绍拓扑结构、视觉感知和特征驱动的大图采样指标;最后介绍了大图采样方法在社交网络、地理交通、生物医学和深度学习等领域的应用,并展望了该方法的发展前景.     

大图结构特征对划分效果的影响

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法。首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性。然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系。当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32%,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6233和316。实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础。     

基于采样的在线大图数据收集和更新

互联网中,以网页、社交媒体和知识库等为载体呈现的大量非结构化数据可表示为在线大图.在线大图数据的获取包括数据收集和更新,是大数据分析与知识工程的重要基础,但面临着数据量大、分布广、异构和变化快速等挑战.基于采样技术,提出并行、自适应的在线大图数据收集和更新方法.首先,将分支限界方法与半蒙特卡罗采样技术相结合,提出能够自适应地收集在线大图数据的HD-QMC算法;然后,为了使收集的数据能反映实际中在线大图的动态变化,进一步基于信息熵及泊松过程,提出高效更新在线大图数据的EPP算法.从理论上分析了该算法的有效性,并将获取的各类在线大图数据统一表示为RDF三元组的形式,为在线大图数据分析及相关研究提供方便易用的数据基础.基于Spark实现了在线大图数据的收集和更新算法,人工生成数据和真实数据上的实验结果展示了该方法的有效性和高效性.     

一种多到一子图同构检测方法

提出一种方法来解决从多个小图到一个大图的子图同构检测问题,其中多个小图是预先给定的,而大图是用户在线提交的.首先,基于DFS 编码提出一种小图集合的压缩组织方法;其次,提出一种带有前向剪枝技术的从多个小图到一个大图的子图同构检测算法.另外,给出一种有效的基于数据挖掘的索引技术.分析和实验结果证实,所提出方法的在线计算代价远小于现有方法,在线执行时间比现有方法快约一个数量级,离线构造时间快一个数量级以上.     

图实现算法综述与评测分析

图实现(Graph realization)问题研究基于节点间全部或部分距离关系测量, 在$d$维空间中计算图的顶点坐标, 使得在所实现图中各节点之间实现距离与测量距离尽可能一致.图实现问题是一个典型的优化问题, 在传感器网络定位、蛋白质结构重建、数据可视化、社交网络分析、机器人同步定位与构图等领域有着广泛应用.图实现的研究同图刚性理论有着紧密的联系, 图的刚性与全局刚性决定图的可实现性.在可实现图中, 现有工作提出几类典型的代表性图实现算法, 包括: 1)基于三边测距类方法; 2)求解距离方程类方法; 3)基于全局优化类方法; 4)基于模块拼合类方法.本文对图实现的刚性理论, 四类图实现算法的设计思想、适用条件、算法流程等进行综述分析, 通过实验对算法进行准确性、计算复杂度、可靠性等方面的比较和分析.     

ZigBee网络拓扑可视化再现算法研究

基于Zig Bee的网络拓扑结构在网络性能分析、网络节点部署、节点压力测试、安全监控等方面起着重要作用。但是在拓扑结构可视化时,由于网络拓扑图可视化模型会出现点覆盖、边交叉和图形拥塞,导致算法复杂度高、耗时陡增,影响可视化效果。为了解决以上问题,并满足实时在线显示需求,提出了一种基于坐标变换-虚拟节点模型的Zig Bee Tree-Star型网络拓扑结构可视化再现算法。该算法能够自适应节点变化。在节点数量较少时,层次算法模型对节点进行布局规划;当节点数量较多时,虚拟节点模型对布局进行扩展延伸。该算法对Zig Bee网络管理具有较高的参考价值。试验表明,该算法所需时间复杂度与空间复杂度低,可解决大量边交叉导致的布局混乱问题,并能适应Zig Bee网络大规模节点的实时可视化需求。     

谈谈图学教材

讨论大图学下的教学理念与方法及大图学学科系列教材的配套建设问题。从学科 分类、图学的科学基础、计算基础、图学实践、图学应用等各个角度讨论了图学的理论教学与 实践教学,以及各学科间的相互关系。基于形是图之源,图是形的载体的认识基础,给出了工 程图学、画法几何、计算机图形学、计算机图像学等主要教材的一些编写原则。基于图学的根 本是几何,建议专门编写一本《图学计算基础》作为图学的公共教材。     

基于小波变换的散乱点数据处理方法

散乱点数据处理在科学可视化研究、逆向工程、计算机视觉等领域有广泛应用。本文根据小波变换的基本原理和多维小波变换算法,设计了一种基于小波变换的散乱点数据处理方法。通过对散乱点的分层处理,将图像视频的三维小波变换应用于散乱点。在满足后期可视化显示要求的基础上,按照需要约减表示细节的高频子带,可应用于三维可视化数据的前期处理方面。     

FMR:基于FR的快速多层次算法

图可视化技术是可视化研究的重要内容,近年来大图的绘制问题一直是图可视化 技术的焦点。为此,提出了一种快速多层次算法用于解决大图绘制问题。采用多层次方法作为 算法的框架,以 FR 力导向算法的变体结合质心算法以及四叉树空间分解等方法对单层布局进 行优化。另外,还使用了约束规范化和能量模型 2 种加速方法。实验表明,该算法具有高效的 性能和良好的布局效果。其效率非常高,在单核 CPU 下,可以在大约 5 s 内很好地绘制出 10 000 个顶点的图。并与几种经典的算法进行了比较,也证明了该算法的有效性和实用性。此外,该 算法易于实现,可被轻易推广到其他布局算法上,以加速其运算。     

基于可扩展计算平台的大图数据管理

随着数据采集和存储技术的发展,社交网络、生物信息科学、交通导航等领域中出现了规模庞大、内部结构复杂、查询需求多样的大图数据。传统基于单机内存的图处理方法无法满足大图数据管理需求。可扩展计算平台的发展为大图数据管理提供了可行的技术方案。本文首先分析了大图数据之上的不同类型查询,重点探讨了基于关系数据库、基于MapReduce计算框架、基于BSP(Bulk Synchronous Parallel)计算模型和基于第三方外包服务器的大图数据管理方法,并分析了未来可能的研究路线。