大规模时序图中持续性稠密子图搜索算法研究

时序图是一种边上带有时间戳的图结构,其中边上的时间戳表示该边出现时间,即图随时间变化不断变化.图数据中的稠密子图挖掘问题具有非常强烈的现实意义.目前,时序图中大多数现有的工作都集中在稠密子图检测问题,该问题目标是找到时序图中所有的目标子图.然而,当时序图的规模过大时,这一问题将变得极其复杂且收效甚微.旨在研究在时序图中...     

时序图上动态子图查询优化算法

挖掘时序图中的特定模式,能够有效地发现有价值的信息,并进行预测与决策支持,因此动态子图的查询及索引优化成为时序图研究的一个热点。研究了聚焦在动态子图的快速查询,着重探讨了索引优化,给出了查询模型的定义及基本查询算法。针对查询算法进行索引优化,提出了两种不同的建立索引的方法,波形索引及二叉树索引。为了验证索引的适用条件,设计了相应的实验,并使用随机数据集对实验程序进行测试,从时间消耗和空间占用的角度对两种索引的运行效率进行了验证分析。波形索引的优势在于存储结构简单,适用于边长度较长边数量不多的情况。二叉树索引的查询速度快,适用于边长度较短边数目较多的情况。     

基于滑动时间窗的稠密子图发现算法研究

针对在滑动时间窗中发现稠密子图的问题,提出一种有效的动态算法,结合时间窗将网络时间线划分为k个非重叠的间隔,间隔内包含最大密度的子图.算法输入是一个边流,输出是一系列稠密子图及相应的时间间隔.现有技术在图更新时需要迭代整个图,所提算法仅影响图的有限区域,只需要局部更新稠密子图.结合理论分析,证明了该算法比基线KGOPT...     

基于双索引的子图查询算法

传统的子图查询算法大多只在图数据库上进行一次挖掘算法,即在图数据库上建立稳定的数据库索引后将不再对索引进行更新.随着查询兴趣的改变或数据库的频繁更新,原有的数据库索引将不再能提供有用的信息来减少查询过程中候选图的数量.为此,提出一种双索引的子图查询算法,同时在数据库和查询流上挖掘频繁子图并建立索引.子图查询和查询流索引的建立同步进行,即使查询兴趣改变,查询流索引也能自适应地更新索引信息来优化查询效率.针对数据库的频繁更新,查询流索引已提供实时的有效信息,数据库索引无需重新建立.实验结果表明,双索引的结合能有效提高查询子图的处理效率.     

多用户偏好的 Top-k 查询处理算法研究磁

传统的 Top-k 查询处理都是利用单用户偏好来计算评分函数,这种方法有极大的局限性。针对基于多用户偏好的 Top-k 查询处理问题进行研究,为了提高查询效率,首先提出了预处理算法 PA 与 PVA ,生成一些具有代表性的系统用户偏好,并据此将初始数据集进行全排序,保存在物化视图中,以便利用它们进行 Top-k 查询。然后,提出了处理 Top-k 查询的 VBA 算法且进行了正确性与完备性论证。最后,实验结果表明,该算法比直接在原数据集中查询的效率有极大的提高。     

无线传感器网络Top-k多查询算法

针对无线传感器网络中多个Top-k查询问题,提出了一种Top-k多查询处理的算法,对接收到的多个Top-k查询请求进行预处理,预处理依据是约束条件,得出两类不同的查询集合:单约束条件的多查询和多约束条件的多查询。针对单约束条件的多查询提出了ETOP算法,该算法首先对排在时间序列最前面的Top-k查询请求进行基于网内处理,然后把查询结果存入基站缓存,并把结果的最小值设定为阈值传输到各个节点,再根据后续查询请求的查询范围进行相应的查询,从而快速地获得Top-k查询结果。实验表明:Top-k多查询方法在能够很好地实现查询的同时,减少了无线传感器网络中的传输消耗和能量消耗。     

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

一种加权稠密子图社区发现算法

目前,针对复杂网络的社区发现算法大多仅根据网络的拓扑结构来确定社区,然而现实复杂网络中的边可能带有表示连接紧密程度或者可信度意义的权重,这些先验信息对社区发现的准确性至关重要.针对该问题,提出了基于加权稠密子图的重叠聚类算法（overlap community detection on weighted networks,简称OCDW）.首先,综合考虑网络拓扑结构及真实网络中边权重的影响,给出了一种网络中边的权重定义方法;进而给出种子节点选取方式和权重更新策略;最终得到聚类结果.OCDW算法在无权网络和加权网络都适用.通过与一些经典的社区发现算法在9个真实网络数据集上进行分析比较,结果表明算法OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能.     

基于增量信息索引的子图查询算法

当前图数据库中的子图同构查询算法主要是依赖倒排索引,然而处理那些具有庞大数据的数据库和复杂的查询愈发成为挑战。研究目的是设计一个算法,使用新的索引作为查询处理的核心,记录查询图的每一个细小改变,并使用一种特殊的数据结构来维护。先是引出一个索引算法,然后逐渐分析整个索引、查询过程,并利用该算法实现一个系统,最后在不同数据集和查询上进行实验。实验证明了该算法具有良好的时间、空间效率和扩展性。新的索引算法能够支持更大的查询图和更加灵活的查询。通过实现的系统和其他系统的对比实验,验证了算法的有效性。     

基于Twitter Storm平台并行挖掘最稠密子图

在大规模图结构数据中发现最稠密子图具有极其广泛的应用,如社区发现、垃圾邮件检测和论文引用关系抽取等。基于带标签的无向图,提出了查询标签集的概念,设计了一个可以快速发现最稠密子图的近似算法DSFLC(Densest Subgraph Finding based on Labelset Constraint):用户提交自定义的查询标签集,算法便可保证在用户可以接受的时间内返回满足查询标签集约束的最稠密子图。对于任何参数ε(ε0),DSFLC算法只需扫描大规模数据集O(log1+εn)次,同时可保证算法的近似因子是2(1+ε)。对DSFLC算法进行分析后,发现该算法在预处理阶段易于并行化,因此选择Twitter Storm平台,并行化地实现了DSFLC算法。最后对从DBLP数据库中抽取的合作关系图进行测试,一方面研究Storm平台对算法的加速程度;另一方面分析挖掘出的子图的稠密度与参数ε之间的关系,最终验证了DSFLC算法的实用性和可扩展性。     

空间数据上Top-k关键词模糊查询算法

基于位置的服务(LBS)变得日益普及,越来越多的研究开始关注如何对空间中的兴趣点(POI)做有效的检索.现有的方法提出了空间数据上的关键词检索,研究如何根据查询的位置和关键词找到相关的POI点.然而,现有方法主要对查询关键词进行精确匹配,不能支持模糊查询:当查询关键词与底层数据存在微小差异的时候,LBS系统不能返回相关的结果.为了满足移动用户的模糊查询需求,文中对空间数据上的Top-k关键词模糊查询问题进行研究:给定一组POI点,检索与查询关键词近似匹配且空间上距离相近的Top-k个结果.为了提供高效的模糊查询,文中首先定义了一种新型的相关性函数,综合考虑了文本相似性和空间距离,进而提出了一种有效的索引结构RegionTrie,并基于RegionTrie设计了高效的Top-k算法.真实数据集上的实验结果表明,文中提出的Top-k算法十分高效,性能远好于对比方法.     

大图中子图的可测性质

对于给定的距离参数。,性质测试算法A需以高概率正确地区分给定的对象具备预定性质II与二远离性质 II。若存在II的测试算法A满足其询问复杂性独立于规模参数n,则称II是可测的。设H是一个图,性质仔了)℃。为 不含井子图的图所构成的集合。在有界度模型中,Goldreich与Ron证明了对任意连通图H,性质仔力℃。是可测 的}s}。在邻接矩阵模型中,证明了对任意图H,不管其连通与否,性质件厂re。是可测的。     

Subgraphs of 4-Regular Planar Graphs

We shall present an algorithm for determining whether or not a given planar graph H can ever be a subgraph of a 4-regular planar graph. The algorithm has running time O(|H|^2.5) and can be used to find an explicit 4-regular planar graph G⊃H if such a graph exists. It shall not matter whether we specify that H and G must be simple graphs or allow them to be multigraphs.     

Discovering Cohesive Temporal Subgraphs with Temporal Density Aware Exploration

Real-world networks, such as social networks, cryptocurrency networks, and e-commerce networks, always have occurrence time of interactions between nodes. Such networks are typically modeled as temporal graphs. Mining cohesive subgraphs from temporal graphs is practical and essential in numerous data mining applications, since mining cohesive subgraphs gets insights into the time-varying nature of temporal graphs. However, existing studies on mining cohesive subgraphs, such as Densest-Exact and k-truss, are mainly tailored for static graphs (whose edges have no temporal information). Therefore, those cohesive subgraph models cannot indicate both the temporal and the structural characteristics of subgraphs. To this end, we explore the model of cohesive temporal subgraphs by incorporating both the evolving and the structural characteristics of temporal subgraphs. Unfortunately, the volume of time intervals in a temporal network is quadratic. As a result, the time complexity of mining temporal cohesive subgraphs is high. To efficiently address the problem, we first mine the temporal density distribution of temporal graphs. Guided by the distribution, we can safely prune many unqualified time intervals with the linear time cost. Then, the remaining time intervals where cohesive temporal subgraphs fall in are examined using the greedy search. The results of the experiments on nine real-world temporal graphs indicate that our model outperforms state-of-the-art solutions in efficiency and quality. Specifically, our model only takes less than two minutes on a million-vertex DBLP and has the highest overall average ranking in EDB and TC metrics.     

Clique Numbers of Random Subgraphs of Some Distance Graphs

We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows:

$$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$

where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.

     

演变图上的连接子图演变模式挖掘

探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动态规划算法.模拟数据集上的实验结果表明,该算法具有较低的误差率和较高的效率.真实数据集上的实验结果表明,挖掘结果在真实应用中具有实际意义.     

演变图上的连接子图演变模式挖掘

探讨演变图(即随时间变化的图)的挖掘,重点研究在演变图中挖掘连接子图的演变模式集合.提出一种连 接子图的相似度函数及其快速计算算法.基于该相似度函数,提出一种发现演变模式集合的多项式时间复杂度的动 态规划算法.模拟数据集上的实验结果表明,该算法具有较低的误差率和较高的效率.真实数据集上的实验结果表 明,挖掘结果在真实应用中具有实际意义.     

KWSDS:关系数据库中Top-k关键词搜索系统

关系数据库中的关键词搜索技术已经成为信息检索领域的研究热点,它为没有任何SQL语法知识的用户提供了一个简单友好的接口.但是现存的关键词搜索系统主要依赖于数据图或模式图,而单独使用数据图或模式图的算法搜索效率不高,结果准确率也较低.设计实现了一个Top-k关键词搜索系统(keyword search system based on database graph and schema graph,KWSDS),用户提交关键词后,系统对关键词进行预处理,消除一些脏关键词.首次提出使用数据图与模式图相结合的方法,设计了同表查询算法和异表查询算法,分析了算法的正确性和时间复杂度,并且提出了相关性结果排序方法.KWSDS系统的搜索算法运行时间短,搜索结果准确性高,具有良好的查询性能.最后通过实验验证了KWSDS的效率.