检索结果-内蒙古大学图书馆

作者：杨雅君哈尔滨工业大学

学位级别：博士

随着信息科技的高速发展，各个应用领域的的信息量都呈现了爆炸性的增长趋势。因此，不同应用领域所关注的实体对象之间的关系也变得愈加庞大和复杂。在这些复杂关系的背后，往往蕴含着巨大的科学价值和商业价值。近年来，许多领域的研... 详细信息

随着信息科技的高速发展，各个应用领域的的信息量都呈现了爆炸性的增长趋势。因此，不同应用领域所关注的实体对象之间的关系也变得愈加庞大和复杂。在这些复杂关系的背后，往往蕴含着巨大的科学价值和商业价值。近年来，许多领域的研究者都开始专注于实体对象之间关系的研究。“图”作为计算机科学中一般性的数据结构，它可以很好的反映数据对象之间的复杂关系。因此，图数据被广泛地用来刻画现实世界中各种各样实体间的复杂关系。然而，在现实世界中，实体对象间的关系每时每刻都在发生着变化。例如：在蛋白质交互网络中，各类蛋白质分子相互作用有着先后顺序，这使得整个蛋白质交互过程要随着时间顺序进行；在社会关系网络中，各类人和各类社会团体之间的交互关系会随着时间发生变化；在交通网络中，通过每条公路的时间和费用因交通拥塞的发生而随着时间发生变化。因此，描述实体间关系的图数据也会随着时间发生变化。动态图是指会随时间发生变化的图数据。动态图可以根据其变化的形式分为两类：(1)图中拓扑结构关系发生变化；(2)图中顶点和边所代表数据对象内容、或者图中某一特定对象的评价方式发生变化。我们分别称之为图的结构变化和图的内容变化。由于动态图在现实世界中广泛存在，因此对动态图上各类问题的研究就有着十分重要的意义。然而，传统静态图数据上解决各类问题的算法无法用于解决动态图数据上的各类问题，主要有以下几个原因：第一，传统的静态图模型无法描述图数据随时间发生演绎与进化的情况；第二，传统的静态图模型上的各类问题的定义在动态图模型上不再适用；第三，图数据的动态性使得各类问题的计算复杂性大大增加，原有的静态图上的各类方法将无法有效地解决这些问题。此外，现有的动态数据管理的研究主要关注于数据流和传统关系数据的动态维护，这些方法无法处理结构复杂的图数据。本文运用计算复杂性和算法学的理论和知识，分别对基于结构变化和基于内容变化的动态图上的相关问题开展了研究工作，主要研究成果如下： (1)本文研究了动态图上结构变化最频繁子图挖掘问题，提出了一个基于“累积连通度变化”概念的评分函数来评价子图的结构变化的频繁程度。本文提出一个两段式算法来计算动态图中任意一对顶点之间的累积连通度变化。进一步地，本文提出一个基于“划分树”结构的算法挖掘目标子图，该算法逐步地将不属于目标子图中的顶点从全图中移除。本文分析了算法的时间复杂度和空间复杂度。真实数据上的实验结果表明，本文算法所挖掘到的子图在整个动态图中变化最频繁。同时，本文算法具有很高的的时间效率。 (2)本文研究了动态图上连通度变化最大的k-顶点集挖掘问题，提出了一种名为“连通等价类树”的结构，利用该结构可以高效地计算图中所有顶点对之间的连通度变化。本文提出了一个高效的连通等价类树构建算法和更新算法。其中，更新算法是一个逐边增量式算法，当动态图发生变化时，该算法只需要更新图中一小部分顶点之间的连通度即可完成连通等价类树的更新。本文证明，在相同的空间复杂度下，本文提出连通等价类树更新算法的时间复杂度远远小于现有最快的连通度更新算法。进一步地，本文提出一种分支界限算法和三种高效的剪枝策略用于挖掘连通度变化最大的k-顶点集。真实数据上的实验结果表明，本文算法所挖掘到的顶点子集可以良好的反映整张动态图中连通度变化情况，因此，其可以作为动态图连通关系变化的一个概括。同时，实验结果表明，本文中算法具有很高的时间效率。 (3)本文研究了多维代价图上动态最优路径查询问题。本文证明了多维代价图上动态最优路径查询问题是一个NP-难问题，并提出了一个分支界限算法和三种高效的剪枝策略用于计算动态最优路径。进一步地，本文提出了一种新的索引结构，k-簇索引，使得本文算法在大规模图上是时间高效和空间高效的。k-簇索引利用“contour skyline”加速查询进程。本文证明计算“contourskyline”是一个NP-难的问题，并提出一个2-近似的算法。本文证明了不存在近似比小于2的多项式时间算法。同时，本文提出一个顶点过滤算法，该算法可将图中大部分不属于最优路径的顶点过滤掉，进一步提高了算法效率。真实数据上的实验结果表明，本文算法具有非常高的时间效率和空间效率。 (4)本文研究了时间依赖图上满足时间限制的费用代价最优路径查询问题，提出了一个两阶段算法计算满足时间限制的费用代价最优路径。算法在第一阶段计算了起点到终点满足时间限制的最小费用代价，在第二阶段根据最小费用代价计算了起点到终点的最优路径。本文分析了查询算法的时间复杂度和空间复杂度。真实数据上的实验结果表明，本文提出的查询算法具有非常高的时间效率和空间效率。

关键词：动态图数据数据挖掘与查询连通度变化最频繁变化子图动态最优路径代价最优路径

来源：评论

学校读者我要写书评

暂无评论

面向动态图数据的嵌套型可视表达与可视分析关键方法研究

面向动态图数据的嵌套型可视表达与可视分析关键方法研究

引用

作者：井明山东大学

学位级别：博士

现代人类社会和虚拟网络中存在很多类型的图数据,如社交网络数据、学术合作网络数据、脑神经连接网络数据等。这些数据包含一个时间维度,使该类数据具有了动态的特征,我们称这一类数据为动态图数据或动态网络数据。由于没有自然存在的形... 详细信息

现代人类社会和虚拟网络中存在很多类型的图数据,如社交网络数据、学术合作网络数据、脑神经连接网络数据等。这些数据包含一个时间维度,使该类数据具有了动态的特征,我们称这一类数据为动态图数据或动态网络数据。由于没有自然存在的形态,对于用户来说这些知识和信息是不可见的。动态图数据以及潜藏其中的时序特征信息,需要通过数据挖掘和可视分析等方法转化为形式化的表达呈现给用户,其中动态图可视化技术对复杂网络分析起到了关键作用。随着时间维度的增长,动态图数据规模也会迅速增长,同时动态图数据在可视化过程中时刻变化,新数据对原可视化效果的影响无法预估,这些特性给动态图的分析与可视化带来了巨大的挑战。目前动态图可视化方法的研究主要集中在布局调整、可视元素选择和时序特征表达等几个方面。其难点主要集中在:1)图数据可视化布局多采用比较直观的节点链接图或邻接矩阵的布局方法,对于复杂信息的可视化表达能力有限;2)表达时序特征多借助动画或者时间线的技术,缺乏对数据整体特征的表现;3)繁琐的交互手段提高了学习成本,有时会加重对信息理解的负担。因此,探索更为高效、直观的动态图可视化方法,是目前亟待解决的问题。基于此背景,本文提出一种嵌套型的动态图可视化方法,将时序信息嵌入到节点链接图中,对其中时序特征可视化、比较布局和增量式布局三个问题给出优化解决方案,并结合便捷的交互手段,增强信息的展示效果。本文的主要研究内容有以下四个方面:(1)研究一种动态图数据中时序特征的可视化方法。本文提出一种多维度的链接信息表示法,该方法在分析动态图数据中每一对节点随时间的特征变化基础上,提取并生成新的时序边数据。另一方面,本文探索分析多种时间方向表达的方式,结合动态图的时序特征,使用弧度曲线作为时间方向的表达方式,同时反映节点之间的关系方向和时序数据排列的时间方向。该方法结构清晰,易于理解,信息丰富,能有效明显地刻画动态图数据的时序特征。我们将该方法应用于真实的文献合作动态图数据,并通过用户实验验证了本文方法在动态图数据时序分析任务中的有效性。(2)研究一种嵌套型动态图数据比较和布局方法。该比较方法扩展了嵌套型动态图数据可视化方法,将进行比较的动态图数据二次嵌入时序单元中,实现了动态图数据的方便直观比较。在布局上提出支持交互干预和冲突检测的EGIB布局方法。该方法是对传统GIB方法的一种增强扩展,应用优化的聚类分析算法处理、优化的分割算法和改进的力引导布局算法进行布局。EGIB布局方法能够保证每次聚类分组的位置不受力引导布局弹性定位的影响,使得可视化结果在每次交互时不会打乱整体的布局,从而提高可视分析的沉浸度。基于可视化映射规则设计的冲突检测算法,避免了节点之间的重叠冲突。最后评估实验结果显示,本文方法能够实现动态图数据的快速直观比较。(3)提出一种适用于嵌套型可视化方法的增量式布局方法,该方法主要用于解决时序数据改变时,当前嵌套型可视化结果发生的布局调整问题。该方法针对数据节点增加、减少、分组改变、时间段改变等需求,分别提出了具体优化解决方案,使得布局调整对当前可视化结果的影响降到最低,从而帮助用户更好的理解数据的变化。该方法能够最大化实现嵌套可视化网络的意象图保留,并能对嵌套时序信息进行自适应调整,其中的细化技术可以独立地应用或与现有的力导向布局方法串联应用。我们将该方法应用于真实的动态图数据,并进行了评测,结果显示本文方法在数据发生改变时,能够高效的对可视化结果进行调整,并能提高用户对数据变化的理解程度。(4)将理论方法应用于真实数据进行深入分析。第一个数据是儿童多动症脑连接数据,研究适用于该数据的可视化方法,包括数据预处理方法、特征提取方法、数据对比可视表达与可视分析方法,并通过设计交互系统,完成对该数据的案例分析,发现其中有参考价值的脑连接模式。第二个数据是IEEE VIS数据,通过可视化结果深入分析该数据研究热点、合作关系随时间的变化趋势。通过对真实动态图数据的可视化及评估,本文设计的嵌套型可视化框架、嵌套型比较布局技术,以及相应的布局和可视化算法,能够有效帮助用户快速理解数据的时序特征。但是随着网络数据量或时序信息量的增长,整个可视化的过程花费时间会迅速增长,还不能处理大数据量的可视化需求。嵌套型动态图可视化仍然存在很多缺点,本文提出的可视化方法是在该领域的有益探索。

关键词：动态图数据嵌套型可视化时序特征提取 EGIB布局

来源：评论

学校读者我要写书评

暂无评论

支持动态图数据的子图查询方法

引用

计算机科学与探索 2014年第2期8卷 139-149页

作者：王楠王斌李晓华杨晓春东北大学信息科学与工程学院沈阳110819

近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加... 详细信息

近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加困难。针对上述问题,提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引,在序列中加入标号以便数据更新后对索引进行维护,再根据序列间的匹配关系过滤出候选集合,最后采用图同构算法验证候选集中的图,最终得到结果集合。该方法的索引构造简单且体积小,并且在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。

关键词：子图查询动态图数据拓扑序列图索引

来源：评论

学校读者我要写书评

暂无评论

支持动态图数据的图查询算法研究

支持动态图数据的图查询算法研究

引用

作者：王楠东北大学

学位级别：硕士

图作为一种复杂的数据结构被应用到各个领域中,如分子化学和社会网络领域,图查询作为图数据库管理的一项重要课题在近些年来受到国内外学者的广泛关注。图查询问题是在图数据库中找到满足条件的数据图集合,其中分为子图查询和超图查询... 详细信息

图作为一种复杂的数据结构被应用到各个领域中,如分子化学和社会网络领域,图查询作为图数据库管理的一项重要课题在近些年来受到国内外学者的广泛关注。图查询问题是在图数据库中找到满足条件的数据图集合,其中分为子图查询和超图查询。随着数据量的日益增加,图查询在为用户提供更强大更全面的功能的同时也使得查询处理过程及索引构建更加复杂。如何高效地支持静态图数据和动态图数据上的图查询问题至关重要。目前,已经有许多工作致力于解决图查询问题。其中大部分工作采用“过滤—验证”框架处理图查询问题,主要集中精力于建立索引等数据结构来提前过滤掉部分非结果集,再将查询图与候选集合中的图逐个做子图同构检测,最终得到结果集合。现有解决图查询问题的方法大致分为基于特征过滤和不基于特征过滤的,这些方法都是基于静态图数据的,而在现实应用中大部分图数据是频繁更新的,现有方法对于动态图数据上的图查询问题代价较高。图查询问题本身就是NPC问题,在动态图数据上图查询问题就变得更加困难。针对上述问题本文提出了支持动态图数据的子图查询方法和支持增量图数据的超图查询方法。支持动态图数据的子图查询方法首先构造出每张图的拓扑层次序列作为索引,再根据序列间的匹配关系过滤出候选集合,最后用图同构算法验证候选集中的图最终得到结果集合。该方法的索引构造简单且体积小,在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。支持增量图数据的超图查询方法基于“分治法”思想,将数据图分解成直至单个顶点的子图,然后从单个顶点的子图开始求它到查询图的子图同构,直到求出数据图到查询图的子图同构结果。该方法的优点是在数据图增加时只需将新加入的数据图进行分解即可,不必重新计算,时问复杂度不随数据图的增加而呈线性增长,节省了时间和空间代价。最后,本文方法在真实数据集上进行了大量的实验。通过实验结果本身及对实验结果的分析证明了本文提出的方法都能够高效地解决动态图数据和增量图数据上的图查询问题。

关键词：图查询动态图数据图索引拓扑序列图分解

来源：评论

学校读者我要写书评

暂无评论

面向动态图数据的开放式学习方法研究

面向动态图数据的开放式学习方法研究

引用

作者：李钦财深圳大学

学位级别：硕士

动态图数据是指节点特征和边关系会随时间发生变化的图数据,可被用于建模多种复杂数据,如交通网络、社交网络等。动态图数据中的一个关键的机器学习任务是节点分类,即预测未标注节点的类别。尽管近年来大量节点分类模型方法被陆续提出,... 详细信息

动态图数据是指节点特征和边关系会随时间发生变化的图数据,可被用于建模多种复杂数据,如交通网络、社交网络等。动态图数据中的一个关键的机器学习任务是节点分类,即预测未标注节点的类别。尽管近年来大量节点分类模型方法被陆续提出,动态图节点分类问题研究仍然面临以下三方面的挑战:一是已有方法大多基于“封闭式学习”的假设,即模型测试阶段所遇到的类别都是训练阶段已学习过的类别。然而在现实世界中,模型测试阶段往往会面向更加开放的环境,新类别和未知类别会持续涌现。传统的封闭式分类模型会强制将所有测试样本归纳到训练阶段学习过的已知类别中,从而获得极差的分类效果。针对动态的图节点分类问题,建立一个开放式学习的分类器能更有效的适应真实的应用场景和实际需求,获取更准确和更可信的分类结果。二是实际应用问题所对应的动态图数据常常携带大量的噪声数据,例如由于测量错误造成的离群值和异常值,由于设备性能造成的数据噪声等。在面向动态图数据的开放式分类模型构建中,如何规避噪声数据的影响,是构建准确可信、具有实际应用意义的动态图分类模型面临的另一个挑战。三是现有的模型通常使用one-hot向量对类别进行编码,这种编码方式较为简单粗暴。实际应用中出现的众多类别并不一定是独立等距离的,如何更好的对类别进行表示学习,从而服务于开放式的动态图分类学习,是我们可以进一步探索的另一个方向。针对以上分析,面向开放环境下的动态图分类问题,本文做了如下研究: （1）本文提出了一个新的基于动态图数据的开放式学习模型OSSC（Open-world Structured Sequence node Classification）。利用一个基于图卷积神经网络（Graph Convo-lutional Network,GCN）GCN的动态变化框架,OSSC能够捕获动态图数据中变化的结构和时序信息。通过不确定性状态和确定性状态的结合,以及抽样过程来生成节点表示,OSSC学习每个节点的潜在分布,以捕获节点属性和图的拓扑结构变化特征。另外,OSSC还引入了一个开放式分类损失函数以确保节点表示对未见类样本保持敏感。为了能够在真实环境中更好的分类,OSSC采用Openmax和Softmax的结合,来区分未见类以及把已见类正确分类。实验表明,OSSC能够在动态图数据中学习一个准确的开放式学习分类器。为了提高OSSC算法对噪声样本的鲁棒性,本文进一步提出了ROSSC（Robust Open-world Structured Sequence node Classification）算法,通过采用拉普拉斯分布表征节点和重抽样去除尾部概率,使得学习框架能够有效应对数据中存在的异常标注样本。（2）传统的深度学习模型通常将目标类编码为one-hot向量,即把不同的类别表示为C维空间上相等距离的点集,这种方法不能很好地刻画类别的特征。为了进一步提高动态图数据的开放式学习框架的分类准确率,基于密集目标编码,本文提出DTE-ROSSC（Dense Target Encoding based Robust Open-world Structured Sequence node Classification）算法。本文将为每个已见类i（i=1,...,C）定义类别特定的密集目标编码Ei={eij|j=1,...,K}。密集目标编码学习将为每一个测试样本赋予其最邻近的目标向量。通过这种方式,所提出的DTE-ROSSC算法能够有效提高分类准确率。

关键词：动态图数据开放式学习节点分类鲁棒性图卷积网络

来源：评论

学校读者我要写书评

暂无评论

面向非统一特征的动态图可视分析关键技术研究

面向非统一特征的动态图可视分析关键技术研究

引用

作者：常宝峰浙江工业大学

学位级别：博士

随着信息收集和数据建模等技术水平的提高，对多个体之间的时序关联的感知、理解、和分析逐渐变得越来越重要。研究人员使用动态图来描述现实场景中的多个体之间的时序关联和属性信息，如社交媒体网络、通信网络、以及城市交通网络等。... 详细信息

随着信息收集和数据建模等技术水平的提高，对多个体之间的时序关联的感知、理解、和分析逐渐变得越来越重要。研究人员使用动态图来描述现实场景中的多个体之间的时序关联和属性信息，如社交媒体网络、通信网络、以及城市交通网络等。对这些时序的、描述个体关系的网络数据的感知和分析能够揭示现实场景中的宏观模式以及隐含规律，进而帮助相关人员进行知识验证和数据价值支撑的决策等重大任务。但是随着动态图数据集日益增长的规模、维度、以及体量等，人脑的感知、记忆、关联、以及计算等能力受到了巨大的挑战。因此，使用可视分析技术帮助人们对动态图数据进行直观的基于视觉通道信息的展示和交互式的关联分析具有重大意义。　　近年来，尽管众多科学家开始关注使用可视分析技术对动态图数据进行分析和挖掘，但是仍然存在一些难以解决的挑战。首先，现有的工作大多针对某一个具体的场景，如通信、交通、社交媒体等场景。但是，过于针对某一具体场景下的动态图数据特征导致众多工作难以扩展到其他领域。不同领域的动态图数据之间具有不同的领域、结构、以及属性特征，进而导致动态图可视分析技术存在领域局限性。针对不同领域、不同结构特征的动态图数据可视分析方法的探索和研究能够改善当前动态图数据可视分析方法的领域局限性。其次，当前面向动态图数据的可视分析工作缺乏对数据特征的总结和讨论，没有形成一套行之有效的面向非统一数据特征动态图数据的可视分析方法和理论。现有的针对动态图数据的可视分析方法大多集中在时间线映射、快照提取、以及图模式探索等方面，缺乏对不同数据结构特征的讨论和分析，尚未形成一套可用的可视分析方法。针对不同动态图数据结构的可视分析理论能够有效帮助研究人员快速针对不同的动态图数据进行可视化视图的设计、实现和分析探索。　　为了应对上述挑战，本学位论文基于三种不同数据特征的动态图数据，即固定拓扑结构的动态图数据、时变拓扑结构的动态图数据、以及多动态图数据，总结动态图数据的数据特征，围绕数据特征对动态图特征构造、建模、可视化和评估等问题展开了相关研究，针对数据特征提出具体的可视化分析方法，搭建可视分析原型系统，从而形成面向非统一特征动态图数据的可视分析方法，为面向非统一特征动态图数据的可视分析理论提供实验基础。本文的主要研究内容和贡献概况如下：　　(1)提出了固定拓扑结构的动态图数据可视分析方法。通过对真实场景数据的计算和建模，构建固定拓扑结构的动态图数据，围绕动态图数据特征提出真实场景特征，搭建可视分析原型系统帮助用户进行交互式可视分析，使用真实的城市交通网络数据为例进行案例分析和专家调研验证方法的有效性和可用性。　　(2)提出了时变拓扑结构的动态图数据可视分析方法。围绕时变拓扑结构的动态图数据的数据特征，提出描述动态图的数据指标，设计交互式动态图快照生成算法，搭建可视分析原型系统帮助用户进行交互式可视分析，使用真实的运动员网络数据为例进行案例分析和专家调研验证方法的有效性和可用性。　　(3)提出了多动态图数据可视分析方法。围绕多动态图数据的数据特征，针对有限可视化空间不能同时展示多个时序动态图的特征，提出动态图扁平化序列提取算法，聚焦于多时序动态图的概览模式，搭建可视分析原型系统帮助用户进行交互式可视分析，引入实验任务和专家调研验证方法的有效性和可用性。

关键词：动态图数据可视分析特征提取拓扑结构

来源：评论

学校读者我要写书评

暂无评论

差分隐私约束下的图数据发布方法研究

差分隐私约束下的图数据发布方法研究

引用

作者：徐抢桂林电子科技大学

学位级别：硕士

伴随整个互联网产业的不断升级,新的智能设备以及软件不断发展,使企业积累了大量应用数据。数据挖掘中,许多数据可以抽象成图数据,使用图(网)等方法来表达现实关系,有着直接、自然等特征,图数据库能够较为高效地插入和查询关联数据,便... 详细信息

伴随整个互联网产业的不断升级,新的智能设备以及软件不断发展,使企业积累了大量应用数据。数据挖掘中,许多数据可以抽象成图数据,使用图(网)等方法来表达现实关系,有着直接、自然等特征,图数据库能够较为高效地插入和查询关联数据,便于后续的建模工作。企业需要对这些数据进行共享或者交由第三方数据分析公司对数据进行分析,挖掘数据的潜在信息特征,方便企业更好地开发产品。然而,直接使用这些数据会造成网络图中用户不愿意透漏的敏感信息泄露,对企业和用户都会造成损失,因此在发布前需要进行一定的隐私保护。因此,数据共享和挖掘中保护用户敏感信息逐渐被人们所重视,成为各界普遍关注的热点问题。差分隐私是一种能够对抗背景知识的攻击,具备较为理想的隐私保护效果的模型,逐渐被用到图数据的发布领域中。本文将重点研究网络图数据统计特征在发布过程中的安全问题,针对三角计数发布中投影算法图结构信息丢失严重和发布数据误差过大的问题以及动态图发布中,需对每个时刻的度直方图分配隐私预算且在直方图发布中累积噪声过大的问题展开研究,利用差分隐私模型保护网络图中用户的隐私。主要研究内容如下:1.研究网络图中点差分隐私约束下的节点三角计数发布问题,针对发布算法敏感度高和图投影过程全局结构发生较大变化这一问题。提出了一种基于图全局结构特征的图投影算法,该方法参考节点的紧密中心度和间接中心度,在图投影的过程中保留了原图的结构信息的同时降低了全局敏感度,保留了更多的三角形;在直方图发布阶段,进一步提出了一种基于k-means聚类分组的直方图发布机制,采用统计学中直方图分组的思想确定k-means聚类中的k,并且在研究中选择初始聚类中心,尽可能规避k-means对于初期的簇中心敏感。根据理论分析与仿真实验得出,当前设计的图投影能够保留较多的三角形,直方图发布算法在隐私保护强度较高时,L1误差和KS误差较小,在符合差分隐私定义的基础上提升了数据可用性。2.研究点差分隐私约束下节点度的持续发布问题,设计以点差分隐私为基础的动态图数据发布方案。该算法首先将动态图数据抽象成增量图数据,针对增量图数据随时间不断增加这一问题,提出了增量-投影算法来对增量图序列进行投影,降低直方图发布的敏感度,另经增量-投影算法得到的压缩图序列仍然是一个增量序列,避免了动态发布过程中隐私预算的分配;在直方图发布阶段,依靠层次聚类对直方图序列的差分序列进行分组,有效的减少了累积噪声。通过理论分析与仿真实验得出:本文研究的算法在图投影过程能够保留较多的边,在相同的隐私保护强度下,减小了发布直方图和原始直方图间的误差,在符合差分隐私定义的基础上提升了数据可用性。

关键词：差分隐私动态图数据三角计数节点的度直方图发布

来源：评论

学校读者我要写书评

暂无评论

云环境下社会网络隐私保护及子图匹配技术研究

云环境下社会网络隐私保护及子图匹配技术研究

引用

作者：袁昊晨内蒙古科技大学

学位级别：硕士

随着信息技术的快速发展,社会网络的数据量变得越来越大。因为社会网络中含有非常多的有价值的信息,所以现在对于社会网络中的数据进行数据挖掘方式越来越多。社会网络中含有大量用户的个人信息,如果使用社会网络中的数据的方式不正确,... 详细信息

随着信息技术的快速发展,社会网络的数据量变得越来越大。因为社会网络中含有非常多的有价值的信息,所以现在对于社会网络中的数据进行数据挖掘方式越来越多。社会网络中含有大量用户的个人信息,如果使用社会网络中的数据的方式不正确,会导致用户的隐私数据的泄露,危害个人信息安全。为了达到保护社会网络中个人隐私数据安全的目的,现阶段已经提出了许多关于社会网络隐私保护的成熟的技术及研究成果。云平台作为存储和处理分析大规模社会网络数据的工具逐渐变为主流,为了解决大规模社会网络子图匹配隐私保护问题,提出了分布式K-自同构社会网络隐私保护算法,保护上传至云平台的社会网络图的结构隐私。通过结点间传递标记信息的方式添加噪声边,使原始图匿名为具有K个对称子图的K-自同构社会网络图。并提出分布式的子图匹配方法对上传图进行子图匹配,根据搜索图中结点的选择性对搜索图进行分解得到搜索分解子图;在每个计算结点内进行分布并行的子图匹配得到搜索分解子图匹配结果,将结果连接后得到关于搜索图的匹配结果;在客户端中根据K-自同构社会网络图的对称性和K自同构函数对得到的子图匹配结果进行恢复和过滤得到正确匹配结果。因为云环境中数据的不断的更新,所以子图匹配结果会随时发生改变。如果图数据每更新一次就重新进行一次子图匹配操作,会浪费大量的时间成本。针对这种情况,提出基于增量方法的子图匹配隐私保护技术。该方法添加两种辅助数据结构:匹配集和候选集,通过利用辅助数据结构,简化匹配操作,达到节省匹配时间的目的。搭建分布式图处理平台GraphEngine,在分布式图处理平台上分别实现以上提出的方法,并采用真实数据集roadNet-CA和roadNet-PA对以上两种方法的执行效率和空间成本进行实验。实验结果表明分布式K-自同构社会网络隐私保护算法提高了处理大规模图数据的效率同时提高了子图匹配的匹配效率并保证了匹配结果的正确率;基于增量方法的子图匹配方法提高了在动态社会网络情况下子图匹配的效率。

关键词：分布式子图匹配大规模图数据动态图数据隐私保护

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：