时序图中Top-k稠密子图查询算法研究

稠密子图的查询是图分析领域的重要研究问题之一,在社交用户相关性分析、Web中社群分析等方面都有着广泛的应用.目前,关于稠密子图查询的研究工作主要基于静态图.而在实际应用中,时序信息会对稠密子图查询产生重要的影响,使得图拓扑结构随时间序列不断发生变化,包含的信息量也不断增加,使得已有的针对静态图的查找方法不再适用于时序图...     

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

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

滑动时间窗算法的Matlab实现

滑动时间窗算法是飞机终端区排序算法中非常重要的一种。介绍了飞机终端区排序中滑动时间窗算法的思想,实现了滑动时间窗算法的Matlab编程,给出了编程代码,为进一步研究滑动时间窗算法提供了基础,通过算例仿真验证了所设计算法的有效性、优越性。     

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

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

稠密子图发现的视频语义挖掘方法

目前基于内容的视频语义挖掘方法并未考虑到视频的多模态特性,不能够实现对于目前海量涌现视频的自动分析处理任务。针对此问题,提出了基于稠密子图发现的视频语义挖掘方法。该方法对待处理的视频进行中文连续语音识别、视频目标识别和视频文字识别,对于识别结果进行中文分词和词性标注,保留名词和动词作为图模型的顶点,顶点之间的边权重设置为两个顶点所代表的词语的中文语义距离,根据稠密子图发现算法挖掘视频的语义信息。实验结果表明这种方法是有效的。     

基于K-sup稠密子图的大规模复杂网络概要算法及可视化

现实社会存在大量复杂网络,随着大数据时代的来临,复杂网络数据规模不断扩大,难以进行算法分析和可视化展示.针对复杂网络小世界、无标度特性,提出基于K-sup稠密子图的复杂网络概要算法,利用三角形在网络中的同质性和传递性发现复杂网络中的稠密子图,结合模块度最大化,将子图中相似的节点归并为超点;运用分层结构存储概要图,并进行可视化显示.该算法能对大规模复杂网络进行有效压缩,保持原网络的性质.在5个真实数据集上进行对比实验,显示出该算法在压缩率、幂率性和平均聚类系数的保持等指标优于已有算法,同时在大规模数据下具有保持网络拓扑结构且支持概要图分层可视化的优点.     

基于不确定性PPI网络的最大稠密子图挖掘*

研究表明使用PPI数据进行蛋白质功能预测是很有意义的。然而,从生物学实验得到的PPI数据一般是含有噪声的、不完全的和不精确的,这使得将PPI网络作为不确定图来处理变得更加合理。提出了一种基于深度优先搜索策略和点扩展的挖掘算法,它可以有效地从不确定的PPI网络中挖掘最大稠密子图。该算法使用了几种高效的剪枝技术来提高挖掘的时间效率。在酵母菌PPI数据上的实验结果表明该算法在精度和效率上都有很好的表现。     

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

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

基于状态约束的滑动时间窗软测量模型

工业过程的模型通常具有非线性强、系统时变明显、工况变化大等特点。传统的滑动时间窗选择方法容易包含大量关联度低的数据,影响了数据模型的建模精度和建模效率。本文提出了一种带状态约束的滑动时间窗口选择算法,应用于工业连续过程软测量模型的训练数据选取。将该时间窗口选择算法与最小二乘支持向量回归算法结合,利用电站锅炉的历史运行数据,建立了燃煤电站锅炉尾部烟气含氧量的软测量模型。研究结果表明,相比于传统的滑动时间窗选择算法,利用该算法进行训练样本选取后,提高了所建立的最小二乘支持向量机模型的模型精度和运行效率。利用该方法建立的烟气含氧量软测量模型具有较高的精度,可以在氧化锆传感器发生故障时代替其工作,保证了氧量信号的稳定性和可靠性。     

基于路径的频繁子图挖掘算法研究

图挖掘是数据挖掘的一个重要研究方向,而图挖掘主要集中在图数据集内频繁子图的挖掘。频繁子图挖掘技术的关键是建立有效机制减少冗余候选子图,以便高效计算和处理所需的频繁子图。提出了一种基于路径的频繁子图挖掘算法,该算法首先找出所有频繁边从而挖掘出频繁单路径,然后通过组合、双射和操作扩展出较多的频繁路径,再通过连接操作产生所有频繁子图候选集。通过定理证明了该算法的正确性和完整性,从理论上分析了该算法时间复杂度低于现有的算法,最后进行了2个图数据集实验,在候选集产生的数量和时间性能2方面验证了算法的优越性。     

基于滑动窗口的不确定性数据流频繁项集挖掘算法

为了提高频繁项集挖掘算法的准确性,在不确定性数据流频繁项集挖掘算法SRUF-mine的基础上引入最大可能误差,提出一种基于滑动窗口的false-positive挖掘算法UFIM。UFIM算法对数据流进行分块处理,在内存中维护一个存储滑动窗口内频繁项集的概要数据结构,随着窗口的滑动对该概要结构进行增量更新。实验表明,与SRUF-mine相比,UFIM算法能获得较高的频繁项集挖掘的准确性。     

基于动态可调衰减滑动窗口的变速数据流聚类算法

在数据流聚类算法中,滑动窗口技术可以及时淘汰历史元组、只关注近期元组,从而改善数据流的聚类效果。如果同时数据流流速无规律地随时间动态变化,原来单纯的滑动窗口技术在解决这类问题时存在缺陷,所以,在充分考虑了滑动窗口大小和数据流流速之间关系的前提下,提出了基于动态可调衰减滑动窗口的变速数据流聚类算法。该算法对历史元组和近期元组分别赋予一定的权重进行处理,然后依据数据流流速的不同函数改变窗口的大小,从而实现数据流的聚类。提出了该数据流聚类算法的数据结构——变异数据流聚类的数据结构。通过真实数据和模拟数据来构造动态变速数据流从而作为验证算法的原始数据。实验结果表明,与Clu Stream聚类算法相比,该方法具有较高的聚类质量、较小的内存开销和较少的聚类处理时间。     

基于图连通支配集的子图匹配优化算法

在子图匹配过程中,随着图规模不断增长,匹配时间呈现指数爆炸的趋势.对此,提出一种基于图连通支配集的子图匹配优化算法VF-SMDS.根据贪心算法构建查询图的最小连通支配子图;通过代价模型计算最小连通支配子图节点的匹配代价,构建最优k查询节点匹配序列;通过支配节点的结构特征缩小查询节点搜索空间范围,在数据图中遍历到满足要求...     

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

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

基于语义的Web服务发现算法

传统的Web服务发现只是简单的基于关键字的语法匹配,查询得到的服务往往不是用户想要的.在基于接口的Web服务发现的基础上,改进了Web服务描述模型,增加了服务质量(QoS),提出了分步过滤匹配算法.先通过服务类别过滤器进行语义过滤筛选,去除不相关的Web服务,然后通过服务相似度度量候选服务和请求服务之间的相似程度.候选服务和请求服务之间的相似度是通过服务功能相似度和服务质量相似度两个方面进行综合评估的.最后,通过实验证明了该匹配算法的可行性和有效性.     

基于密集连接的FPN多尺度目标检测算法

图像中目标对象的多尺度问题一直以来都是目标检测领域的主要难点之一,尤其是极端尺度对象的检测。研究发现,目标检测网络模型的深层语义特征有利于对象的识别,而浅层空间特征对对象的边界框回归很有帮助。DC-FPN使用密集连接代替FPN网络模型中的横向连接,能够从多层特征层中获取目标检测所需的特征信息,其中密集连接可以融合FPN自底向上传输模块中的所有特征层的特征信息,使FPN自顶向下传输模块的预测特征层能从中获取不同尺度对象检测所需的特征信息。实验表明,DC-FPN目标检测算法能够显著地提升模型的多尺度目标检测性能,使用MS COCO数据集训练和测试,其检测准确度(AP)能达到43.1%。     

一种基于交错的窗口标量乘算法

从研究窗口标量乘法出发,通过将交错技术与Koblitz曲线上的窗口TNAF标量乘法相结合,给出一种新的标量乘算法,该算法不对标量乘进行预计算,只是在赋值阶段施加交错.由于Frobenius映射效率高,加之使用交错技术,本算法的效率比传统窗口NAF标量乘法要高.对新算法运行时间进行分析,新算法的时间复杂性比传统窗口NAF算法大约减少60%～75%,比Comb算法大约减少70%～79%.     

基于时间加权的协同过滤算法研究

协同过滤算法是目前个性化推荐系统中应用最成功的推荐算法之一,但传统的算法没有考虑用户兴趣漂移的问题,导致推荐系统的推荐质量下降.针对这个问题,提出了基于时间加权的协同过滤算法.实验表明,改进的算法提高了推荐系统的推荐质量.     

“灵活”的滑动窗口算法及其计算量的估计

通过对预存储空间的充分利用,首先给出了一种"灵活"的滑动窗口算法,然后对该算法所涉及的整数表示方法的汉明重量进行了仔细的估计.通过与原有滑动窗口算法、m-ary算法的平均模乘次数的比较,最后得出"灵活"的滑动窗口算法在基本保持原有滑动窗口算法计算复杂度的同时,克服了原有算法中对预存储空间的限制.     

基于WCF tree加权滑动窗口数据流元项集挖掘

数据流挖掘是当今数据挖掘领域内热点研究问题.通常频繁项集的数据量大,影响挖掘结果的理解与应用,提出一种基于WCF tree加权滑动窗口数据流元项集挖掘算法(TWEM算法).首先,考虑到数据在不同时间窗口内的重要性,允许用户定义窗口个数和各窗口权值;其次,利用WCF tree挖掘闭项集;最后,结合各等价类内项集与相应元项集支持度不完全相同,保持一种可估算的关系的特性,挖掘元项集.实验结果表明,TWEM算法缩小了搜索空间,提高了程序的运行效率.