面向多层网络可视化的多力导引节点自动布局算法

为展示多层网络层内社区结构和实现层间结构对比,基于传统力导引布局模型提出一种面向多层网络可视化的多力导引节点自动布局算法.首先在综合考虑节点所受层内引力、斥力和层间节点-副本间引力的基础上改进传统引力-斥力模型,构建多力导引模型;然后引入模拟退火思想为多力导引布局添加温度控制参数,控制节点移动速度;最后借鉴布局美学标准中的"总边长最短"原则,采用节点与副本的水平偏移与最优边长的平均相对长度和社区内部连边与最优边长的平均相对长度这2个指标评价文中算法的布局效果.通过对仿真数据和真实数据的实验结果表明,与基于层叠切片模型的独立布局算法相比,该算法能同时兼顾多层网络社区结构展示和跨层节点及其副本识别的效果,满足多层网络可视化对节点自动布局的要求.     

基于阈值的概率图可达查询

图的可达性查询被广泛应用于生物网络、社会网络、本体网络、RDF网络等.由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定图的可达查询不能有效地处理不确定性,因此该文研究用概率语义描述的图可达性查询.具体的,该文使用可能世界概率模型定义不确定图(称为概率图),基于该模型,研究了基于阈值的概率可达查询(T-PR).首先为避免枚举所有可能世界,给出一个基本算法可精确求解T-PR查询.其次为进一步加速基本算法,给出3种改进方法,它们是不确定事件界、同构图的缩减、基于不相交路径和割集的界.通过合理的组合给出3种方法的合并算法.最后基于真实概率图数据的大量实验验证了该文的设计.     

多域网络逻辑拓扑布局算法研究

网络空间态势可视化已经成为网络空间态势信息综合与分析的重要环节,在态势可视化中网络逻辑拓扑的布局生成技术也得到了越来越多的关注。本文针对网络逻辑拓扑结构复杂、多域的特点,结合层级布局、力导引布局等图布局算法,提出了一种针对网络空间态势逻辑拓扑数据的布局生成算法。经过实验验证,该算法能够完成多域网络逻辑拓扑的自动布局,并保证布局的清晰、合理。     

面向不确定平面图的模式匹配查询

平面图的模式匹配查询可广泛应用于生物网络、社会网络、指纹识别和图像分割等。由于对数据操作时引入的噪声和错误使这些图数据具有不确定性,而确定平面图的查询处理技术不能有效地处理不确定性,因此利用概率语义描述的平面图的模式进行匹配查询。具体地,使用可能世界概率模型定义不确定平面图,基于该模型,研究了不确定模式匹配(UPM)查询。首先给出一个确定算法可避免枚举所有的可能世界,同时给出改进的确定算法可更快速地求解查询。其次设计出采样算法,可快速地估算出匹配概率,并具有较高的精确度。基于真实不确定平面图数据的大量实验验证了该设计。最后将该查询应用于肺部CT图像的分割,结果表明此方法优于经典的图像分割算法。     

基于改进力导引图布局的层级视觉抽象方法

随着图规模的增大,传统的力导引布局算法会出现节点重叠、边交叉等视觉混乱问题,为此提出一种基于改进力导引布局的可扩展的可视化层级抽象方法.首先结合FR算法与LinLog算法的优点对力导引算法进行改进,生成一个具有明显聚类结构、能够体现图结构信息的初步布局;然后基于布局结果,采用自下而上的层次聚类方法生成图的层级结构,同时定义了体现抽象层级的参数来决定不同层级下的聚类显示,允许用户在多个层级观察数据结构特征;最后采用几何距离、拓扑结构和拓扑结构加中介中心性3种不同的度量进行视觉抽象,并对抽象结果进行比较分析.为了说明文中方法的有效性,分别对信息可视化文章间的文献引用数据、2004年美国总统竞选的政治博客数据,以及IEEE Visualization会议文章的作者合作数据这3个数据实例进行实验,结果表明,使用该方法并结合移动、缩放、选择等可视化交互技术,能有效地帮助用户分析、探索和理解数据隐藏的信息.     

面向层次化数据的变分圆形树图

圆形树图(circular treemap)是面向层次化数据的一种信息可视化方法.提出一种圆形树图构造方法,将圆形树图的布局问题与组合优化中的圆排列(disk packing)问题相结合,以一种基于变分连续优化的算法求解多个半径不同圆的优化布局,由此提高圆形树图的空间利用率,并支持层次下行、层次上行与焦点+上下文等自然交互方式.实验结果表明了该方法的有效性.     

概率图模型学习技术研究进展

概率图模型能有效处理不确定性推理,从样本数据中准确高效地学习概率图模型是其在实际应用中的关键问题.概率图模型的表示由参数和结构两部分组成,其学习算法也相应分为参数学习与结构学习.本文详细介绍了基于概率图模型网络的参数学习与结构学习算法,并根据数据集是否完备而分别讨论各种情况下的参数学习算法,还针对结构学习算法特点的不同把结构学习算法归纳为基于约束的学习、基于评分搜索的学习、混合学习、动态规划结构学习、模型平均结构学习和不完备数据集的结构学习.并总结了马尔科夫网络的参数学习与结构学习算法.最后指出了概率图模型学习的开放性问题以及进一步的研究方向.     

基于数据结构可视化布局算法研究

为有效满足规模和密度快速增长的图数据对可视化结果可读性的需求,本文主要对数据结构可视化的布局算法进行了研究,针对大规模图数据完成了基于模块分析的可视化方法的构建,首先对LPA(Label Propagation Algorithm,标签传播算法)社团发现算法进行改进,再据此完成对大规模图数据的划分,分析划分后各模块的结构模式并将其抽象为节点,最后通过力引导算法的使用完成对处理后模块的布局及模块结构模式信息的展示,有效实现了大规模图数据的可视化处理过程,为进一步处理加工数据提供支撑。     

大规模社交网络社区发现及可视化算法

针对现有社区发现算法存在社区质量不满足图可视化要求和算法效率低的问题,提出一种改进的启发式社区发现算法.该算法基于模块度优化,通过结合预先选取种子节点的方法,抑制算法中大社区的过度合并,同时及时合并小的社区;然后针对力导引布局算法存在社区结构不明显和布局效率低问题,提出一种展示大规模社区结构的社区布局算法,通过引入社区引力促使同一社区中的节点聚拢,优化了社区引力建模,简化了布局算法步骤.实验结果表明,文中算法能够清晰、高效地展示大规模社交网络数据.     

不确定图数据库中高效查询处理

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.     

基于大规模社会网络的并行布局算法框架

随着社会网络的迅速发展,针对大规模社会网络的可视化已经成为数据挖掘领域中的一项重要的研究课题。传统的布局算法已经无法对大规模的社区网络进行全局管理和展示。因此,该框架基于并行化技术以及分层的思想,实现了大规模社会网络的可视化框架。其贡献主要有:提出了一种基于力导引算法的非重叠社区布局算法(简称NFR);设计了一个基于Spark的并行计算框架;将图数据库(Neo4j)无缝地整合到框架中。最后通过在真实数据集上的测试,验证了该框架的有效性。     

HPDBSCAN:高效的不确定数据处理算法

为了解决无线传感器网络中的不确定数据,提出了一种无线传感器网络不确定数据高效处理算法.根据不确定性数据的概率密度分布进行概率聚类,并利用Hilbert编码技术将多维数据映射到一维数据空间,通过基于Hilbert-R树索引的不确定性数据HPDBSCAN算法对不确定性数据进行聚类.实验结果表明,HPDBSCAN算法预处理效果较好,比其它聚类算法更适合不确定性数据的聚类.     

基于层次随机图模型的脑网络链路预测

针对一般链路预测算法在具有层次结构的脑网络中计算效率低且复杂度高的问题,提出了一种基于最大似然估计的层次随机图模型。该算法首先利用脑网络数据建立层次随机图,然后通过改进的马尔科夫蒙特卡罗算法采样树状图空间,最后计算脑网络边的平均连接概率,且通过评价指标对算法进行评价。实验结果表明,利用该算法对脑网络和3种不同的层次结构网络进行链路预测比较, 脑网络的预测结果最好。此外,所提出的算法较之传统的基于相似性的算法,该算法效果明显,且具有理想的计算复杂度。     

社交网络下的不确定图隐私保护算法

社交网络平台的快速普及使得社交网络中的个人隐私泄露问题愈发受到用户的关心,传统的数据隐私保护方法无法满足用户数量巨大、关系复杂的社交网络隐私保护需求.图修改技术是针对社交网络数据的隐私保护所提出的一系列隐私保护措施,其中不确定图是将确定图转化为概率图的一种隐私保护方法.主要研究了不确定图中边概率赋值算法,提出了基于差分隐私的不确定图边概率赋值算法,该算法具有双重隐私保障,适合社交网络隐私保护要求高的场景.同时提出了基于三元闭包的不确定图边概率分配算法,该算法在实现隐私保护的同时保持了较高的数据效用,适合简单的社交网络隐私保护场景.分析与比较表明：与（k,ε）-混淆算法相比,基于差分隐私的不确定图边概率赋值算法可以实现较高的隐私保护效果,基于三元闭包的不确定图边概率分配算法具有较高的数据效用性.最后,为了衡量网络结构的失真程度,提出了基于网络结构熵的数据效用性度量算法,该算法能够度量不确定图与原始图结构的相似程度.     

无线传感器网络中基于位置信息的路由算法研究

为了保证移动无线传感器网络中数据的高效稳定传输,提出了一种基于地理位置信息支持多个移动sink的路由算法.该算法将监测区域分成一个固定不变的规则网格网络,并对网格簇头节点的选举方法进行了改进;通过数据的冗余传递和搜索框、候选转发节点集合的设置保证了数据传送的可靠性与时延性;同时容忍圆的引入保证了低功耗的要求.仿真结果表明,该算法较两层数据分发协议有更高的传输可靠性和较低的功耗.     

不确定性交通网络中的top-k路径查询

该文将交通网络抽象为不确定性图模型,并用概率图的方式研究了不确定交通网络中的top-k路径查询,给出了求解概率图中top-k路径查询的数学模型,提出了一种基于遗传算法的不确定性交通网络top-k路径查询算法,并对算法进行了测试,得到了较好的结果。     

基于GPU的大尺度网络布局显示

复杂网络的可视化是复杂网络研究中的重要手段.随着Web2.0时代和大数据时代的来临,作为研究对象的复杂网络的规模越来越大,这对复杂网络可视化布局算法的布局效果和运算速度提出了新的挑战.本文针对复杂网络布局的力导引算法,从布局效果和算法效率两方面对该算法进行了改进和实现.布局效果方面,利用复杂网络中的关节点,对网络数据进行抽象合并,从而实现分层次的网络布局显示.算法效率方面,针对压缩后的网络采用具有强大浮点运算能力的GPU进行计算,对力导引算法需要斥力计算、引力计算和坐标更新三个部分均实现了基于GPU的并行计算,大大提高了计算效率.     

一种面向大数据的水塘采样分布式算法

水塘采样算法构建了一个样本集合,很好地解决了对未知的数据元素等概率采样的问题。然而当数据量较大时,单机的水塘采样算法时间复杂度较高、机器负载加重。面向大数据采样的需求,提出了分布式水塘采样算法,通过增加采样比例的方法实现了多机器并行采样,而且从理论上证明了分布式水塘采样的等概率性。为处理对数据元素贡献度不同的数据集,将该算法改进为加权重分布式水塘采样算法。基于水塘采样,提出了一种适用于大数据的分布式采样算法,只依据线性时间和样本大小的空间,实验验证了该算法的可行性和有效性。     

基于节点属性的启发式网络拓扑图布局算法

工业监控网络拓扑可视化作为网络拓扑可视化的一个分支,要求布图结构直观而且实时性强。然而,以往的拓扑布局算法并不能满足这一要求。针对这一问题,面向一层或二层星型、一层mesh型和mesh型与星型两层混合的工业监控网络结构,根据网络结构特点和节点关系属性改进斥力张力模型,提出一种基于节点属性的启发式网络拓扑布局算法。实验结果证明该算法时间复杂度较低,而且布图直观性良好。     

复杂网络中基于采样的近似三角计数方法研究

复杂网络中的三角计数可以用于分析网络的同质性和传递性。为了提高复杂网络中三角计数的性能,提出了一种基于采样的近似三角计数方法。首先,以一定的采样概率对网络中的边进行采样从而得到一个子网络,并在该子网络中统计三角的个数。其次,依据采样的概率思想,应用子网络中的三角个数估计原网络中的三角个数。最后,对采样方法的均值和方差进行了理论分析,并给出了由采样方法得到的加速比。理论分析与实验表明,与传统的节点迭代方法相比,提出的方法在保证高准确性的前提下大大提高了算法的运行效率,因而更适用于大规模网络中基于三角计数的相关应用。