面向子图同构的高效索引构建算法

针对子图同构中索引构建方法效率低、内存占用大而影响查询效率的问题,本文提出基于2次排序查找等价顶点的数据图索引构建算法。该算法采用不同邻接链表表示类别不同的语法等价顶点的邻居集合,并依此设计2次排序的方法快速查找数据图中两两互连和两两互不相连的等价顶点,然后依据语法等价和语法包含关系为数据图构建索引来提高子图同构查询的效率。最后,基于不同规模的数据集,通过实验验证了本文提出索引构建算法的高效性和可扩展性。     

基于DAG解构的图近似包含查询算法

为解决图集近似包含查询,提出一种基于图解构的GCSS算法.该算法通过对图集中的目标图进行解构,得到图集中子图分布情况,并利用该子图分布建立索引.在此索引基础上的查询算法对图集进行近似包含查询,不但可以避免确定候选集的过程中产生过多子图同构测试,而且形成较小候选集,提高验证阶段效率.实验结果表明,GCSS算法能高效完成近似包含查询任务,得到图集中被查询图近似包含的正确结果.     

基于子图交互关系的网络结构增强算法

已有研究基于子图交互关系构造子图网络来实现网络结构增强,然而其算法复杂度高.鉴于此,基于不同阶子图网络的拓扑属性分别对原始网络进行赋权,得到一阶和二阶加权网络,以权重的形式直观体现子图交互关系.同时,这两种加权网络的权重可以直接通过原始网络的拓扑结构计算得出,从而避免了子图网络的构造过程,大大降低了算法复杂度.最后,以...     

保持结点间可达性的社会网络图匿名技术

为了保护社会网络隐私信息,提出了多种社会网络图匿名化技术。图匿名化目的在于通过图修改操作来防止隐私泄露,同时保证匿名图在社会网络分析和图查询方面的数据可用性。作为图查询操作的基础,可达性查询是衡量图数据可用性的一项重要指标。然而,图匿名会对结点间的可达性造成影响,导致较大的可达性信息损失。为了保持匿名图中结点间的可达性,提出可达性保持图匿名化算法(简称RPA算法)。通过生成可达性保持最小子图并在图匿名化过程中保持该子图的完整性,RPA算法实现了在匿名图中保持结点间的可达性。基于真实数据集通过大量实验测试和分析,验证了RPA算法可以保证在匿名图中进行可达性查询的高准确度。     

一种基于完全子图与标签传播的重叠社区检测算法

提出了一种基于完全子图和标签传播的重叠社区检测ＣＬＰＯＡ算法。该算法首先搜寻完全子图,并为每个子图分配唯一标签,实现快速标签预处理;然后根据每个节点的邻接节点标签来更新该节点的标签,同时提出接触频数优化标签选择策略降低标签随机传播概率;最后,通过网络标签分布情况进行社区划分。选取两个小规模标准数据集和两个大规模网络数据集进行实验,结果表明ＣＬＰＯＡ算法能保持和ＣＯＰＲＡ算法相同社区划分质量,同时具有更好的算法稳定性和时间性能。     

一种基于数据图划分的关系数据库关键词检索方法

不同于常用的一次性将图加载入内存的检索方法,提出了一种基于数据图划分的关系数据库关键词检索方法,该方法首先将大图细分成多个相互之间具有简单连通性的小图并存储于缓存中,然后通过超图查询算法获取与查询条件相关的子图,进行关键词检索获取候选结果时,只需加载相关子图并恢复子图的初始结构,通过遍历子图获得最终结果.实验表明,该方法可以有效解决对无法放入内存的大型数据图的处理问题,使得关系数据库关键词检索实用于庞大而复杂的数据图中而不受内存约束.     

基于云计算数据查询的安全索引构建方法

为了加强云计算数据查询的安全性,防止用户数据查询过程中过度访问和检索过程的数据泄露,提出一种云计算服务端的数据安全索引构建方法.对图状部署的云计算数据采用相似子图和哈希函数进行构造,通过特征子结构将被查询对象与索引图状数据进行对比,找出被查询对象.该方法可防止非查询对象的图状数据泄露,同时将哈希函数对节点进行了散列,提高了节点安全性.仿真结果表明,该方法数据查询效率高,耗费存储资源少,安全性好.     

图同构的零知识证明协议

研究了图同构的交互式零知识证明协议,并通过分析基于零知识证明的基本模型,提出了子图同构的认证算法.大部分零知识证明的安全性是由复杂的数学运算和交互双方大规模的计算来保证的,而采用模运算方法对文件进行加密,仅需几个参数就可以表示,大大减小了存储空间.协议直接将模运算作用于文件加密,实现起来简单有效;而且由于零知识证明的特点,其安全保密性也较高,满足了基本保护需求.该算法同样适用于登录的身份验证及不可追查的选举投票.     

基于带权无向连接图的子装配体识别方法研究

子装配体识别是解决大规模装配序列规划问题的有效方法之一.为了高效、自动地识别子装配体,根据零件联接类型,建立了装配体的带权无向连接图模型.通过边权值的设定,使得装配体的带权无向连接图能够提供Ⅰ型和Ⅱ型子装配体识别所需的联接信息.将带权无向连接图与装配体的干涉矩阵和支撑矩阵相结合,设计并实现了Ⅰ型和Ⅱ型子装配体的识别算法.与有向连接图模型中子装配体识别算法相比,能够有效消除识别过程中对两种类型子装配体的冗余判断.实验结果表明,识别算法能够有效的进行两种类型子装配体的识别.     

基于拓扑子图与编辑距离的距离测量方法

图结构数据搜索的核心是为图的匹配寻找一个好的相似性测量方法.图编辑距离法和最大公共子图法是现有的两种较成熟的测量方法.图编辑距离法善于描述细小的距离差距,但缺乏结构上的描述;最大公共子图法与之相反,在结构描述上很有优势,但是在细节的描述上很弱.鉴于这种情况,将最大拓扑公共子图法与编辑距离测量法相结合,提出了一种新的相似性测量方法.这种方法先用拓扑公共子图进行结构性描述,然后利用编辑距离的细节描述能力对最大拓扑公共子图内部的相似性距离进行调整,从而有效地发挥了最大公共子图法和编辑距离法各自的优点,使得图之间的相似性衡量更加有效、精确;同时在图的相似性搜索、图像检索、对象识别等领域也更有相容力和理解力.     

基于低频浮动车数据的实时地图匹配算法

在考虑GPS误差等影响因素的前提下,按照5 min时间间隔为单位,对该时间段的GPS点筛选候选匹配链路;然后利用最短路算法获得浮动车行驶的候选径路集,并通过模糊逻辑推理确定最终行驶径路,实现低频浮动车数据的地图匹配;最后,基于北京市采集的浮动车高频数据,利用不同频率下随机抽取低频数据对算法进行验证.     

线性有源网络主子图的直接产生

本文提出了由混合图G_c直接成批产生主子图的方法,使线性有源网络的主子图分析法成为有效算法。     

一种XML多分支路径索引查询算法

为高效地实现XML多分支路径查询,提出了基于索引的XML多分支路径查询算法depthjoin.首先对XML文档进行编码并创建索引,然后对查询树进行查询匹配.采用栈存储多分支路径中的单路径,对多分支结点采用索引信息判定其子结点是否具有共同的祖先结点或父结点.与现有的XML分支查询算法相比,算法depthjoin充分利用索引,不需要进行单路径的连接操作,实验表明其查询效率比现有的查询算法高.     

并行最小割算法及其在金融社交网络中的应用

有效实施金融监管已成为金融健康发展的必要保证. 若能够在金融社交网络中,找到一部分承载网络中所有信息流动的关键节点,便能实现整个金融社交网络的有效监管. 金融社交网络图规模通常较大,须开发大规模图处理并行算法. 本文提出基于分布式图处理平台Pregel的并行最小割算法. 实验基于Apache Spark平台开展,所用数据均来自BoardEx数据库. 实验结果表明,在大规模社交网络图的处理中,该算法具有良好性能. 利用该并行算法得到金融社交网络图的最小割,便可有效实施金融监管.     

On the graph traversal method for evaluating linear binary-chain programs

Grahne et al. have presented a graph algorithm for evaluating a subset of recursive queries. This method consists of two phases. In the first phase, the method transforms a linear binary-chain program into a set of equations over expressions containing predicate symbols. In the second phase, a graph is constructed from the equations and the answers are produced by traversing the relevant paths. A new algorithm is described which requires less time than Grahne' s. The key idea of the improvement is to reduce the search space that will be traversed when a query is invoked. Further, the evaluation of cyclic data is speeded up by generating most answers directly in terms of the answers already found and the associated "path information" instead of traversing the corresponding paths as usual. In this way, this algorithm achieves a linear time complexity for both acyclic and most of cyclic data.     

无线传感器和执行器网络可靠高效路由

针对当前的无线传感器与执行器网络（WSAN）技术缺乏实时性能以及工业无线环境的动态性问题,基于Kautz图设计容错、实时、高效、可靠的先验式路由FRER,不需要维持路由表,只利用节点IDs,根据节点IDs的匹配长度快速找到目标节点的最短路径.当节点故障时,不需要进行路径重挑,根据自身ID与目标节点ID的匹配,上一跳节点能够快速找到剩余节点的最短路径.考虑路径的多样性,不局限于Kautz拓扑,利用邻居节点信息拓展网络中路径的多样性.考虑链路故障,基于链路可用性历史信息组合多路径,保证在链路故障情况下网络维持可接受水平的路由路径可用性.实验结果表明,与REFER和Debruijn图相比,FRER在实时性、容错性和可靠性性能上优于两者.     

新型用户访问模式挖掘方法研究

用户访问模式反映了用户浏览网站的规律,可从中发现用户的访问兴趣。常用的模式发现方法则是从用户的访问日志中挖掘用户的频繁遍历路径。由于基于Apriori算法的频繁遍历路径挖掘方法需频繁访问数据库和产生大量的候选项,提出了新型的遍历路径树的数据结构,用以挖掘用户的频繁遍历路径,通过与传统算法比较,提高了挖掘效率。