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

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

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

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

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

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

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

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

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

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

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

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

基于不确定性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算法的实用性和可扩展性。     

二部图凝聚子图快速查询算法以及在电子商务中的应用

随着互联网的飞速发展,亚马逊,阿里巴巴和eBay这样的的电子商务平台已经成为世界经济不可或缺的一环.在这些电子商务平台中,用户和商品之间的互动可以自然地抽象成二部图,其中每个点表示用户或商品,每条边表示用户购买或评价了物品.如果一些用户和商品之间发生了紧密的联系,那么他们就形成了一个电子社区.基于二部图中的凝聚子图模型(α,β)-core,引入了(α,β)组的概念来代表社区.设计了有效且快速的算法来计算大规模用户-商品二部图中包含给定查询点的(α,β)组,给出了查询算法并分析了算法的时间和空间复杂度.在6个真实数据集上的实验证实了采用(α,β)组这一模型的合理性以及提出的算法的高效性.     

I/O Efficient Early Bursting Cohesive Subgraph Discovery in Massive Temporal Networks

Temporal networks are an effective way to encode temporal information into graph data losslessly. Finding the bursting cohesive subgraph (BCS), which accumulates its cohesiveness at the fastest rate, is an important problem in temporal networks. The BCS has a large number of applications, such as representing emergency events in social media, traffic congestion in road networks and epidemic outbreak in communities. Nevertheless, existing methods demand the BCS lasting for a time interval, which neglects the timeliness of the BCS. In this paper, we design an early bursting cohesive subgraph (EBCS) model based on the k-core to enable identifying the burstiness as soon as possible. To find the EBCS, we first construct a time weight graph (TWG) to measure the bursting level by integrating the topological and temporal information. Then, we propose a global search algorithm, called GS-EBCS, which can find the exact EBCS by iteratively removing nodes from the TWG. Further, we propose a local search algorithm, named LS-EBCS, to find the EBCS by first expanding from a seed node until obtaining a candidate k-core and then refining the k-core to the result subgraph in an optimal time complexity. Subsequently, considering the situation that the massive temporal networks cannot be completely put into the memory, we first design an I/O method to build the TWG and then develop I/O efficient global search and local search algorithms, namely I/O-GS and I/O-LS respectively, to find the EBCS under the semi-external model. Extensive experiments, conducted on four real temporal networks, demonstrate the efficiency and effectiveness of our proposed algorithms. For example, on the DBLP dataset, I/O-LS and LS-EBCS have comparable running time, while the maximum memory usage of I/O-LS is only 6.5 MB, which is much smaller than that of LS-EBCS taking 308.7 MB.     

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.     

面向时序图数据的快速环枚举算法

时序图数据是一类边上带有时间戳信息的图数据.在时序图数据中,时序环是边满足时间戳递增约束的回路.时序环枚举在现实中有着很多应用,它可以帮助挖掘金融网络中的欺诈行为.此外,研究时序环的数量对于刻画不同时序图的特性也有重要作用.基于2018年由RohitKumar等人提出的时序环枚举算法(2SCENT算法),提出一种通过添加环路信息来削减搜索空间的新型时序环枚举算法.所提出的算法为一个两阶段的算法:1)首先,通过遍历原图获得所有可能会形成环路的节点,以及相应的时间和长度信息;2)然后,利用以上信息进行动态深度优先搜索,挖掘所有的满足约束条件的环.在4个不同的真实时序图数据集上进行了大规模的实验,并以2SCENT算法作为基准对算法进行了对比.实验结果表明,所提出的算法较之前最好的2SCENT算法要快50%以上.     

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

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

扩展子图同构问题的优化算法

针对扩展子图的匹配问题,根据Ullmann剪枝和QuickSI的不同特性,提出优化处理距离信息的加边算法。根据Query中各个顶点到不同label顶点的最短距离进行剪枝,采用动态加边算法减少加边的运算时间,能够处理规模不大的稀疏图。在AIDS数据库上的实验结果表明,在不同距离值的条件下,QuickSI算法的平均运行速度比Ullmann算法快一个数量级以上。     

一种基于Apriori思想的频繁子图发现算法

如今,关联规则技术应用在许多非传统领域,许多已有的频繁项集搜索方法已经不适用了。一种解决的方法就是用图的形式表示这些领域的事务,然后利用基于图论的数据挖掘技术发现频繁子图。本文提出了一种基于Aproiri思想的频繁子图发现算法SLAGM,它可以有效地挖掘简单图中的频繁子图。实验证明,该算法在性能上优于另一种子图挖掘算法AGM。     

基于子图同构的子电路提取算法

从门级到功能模块级的子电路提取问题在大规模集成电路计算机辅助设计领域有广泛地应用,提出了基于子图同构的方法来解决该问题。针对子电路的特征,选择辐射路匹配和赋标号算法之一作为搜索的主算法。尽管子图同构问题是NP完全问题,算法对实际的电路是快速的,满足工程需要。     

基于有向网络非对等关系的异常子图识别算法

图异常检测将实体间通联关系抽象为复杂网络形式表示,旨在利用结构特征识别网络中存在的异常行为与实体,具有关系客观存在且异常可解释较强的优点。目前该类方法主要以无向网络结构为基础提取特征,以达到识别异常的目的,主要关注于连边层面异常结构,对于由集体异常行为构成的异常子图识别问题研究仍较少,缺少对行为方向异常协同关系的分析。传统方法通过提取节点邻域结构特征构建特征空间,并根据节点邻域结构在特征空间中的映射点距离发现离群点,虽可发现结构具有明显差异的异常子图,但忽略了网络结构中节点的实际物理联系,以及行为由于主客体不同所导致个体间关系非对等的实际情况。针对该问题,本文提出了基于有向网络非对等关系的异常子图识别算法,通过连边方向信息提取节点间行为方向特征,度量节点间关系非对等强度,后转化为子图密度形式表示,结合基于密度的异常识别方法挖掘异常,保留了实际物理联系。通过在4种不同异常类型的合成数据集与存在实际异常的真实数据集上进行实验,验证了其具有较高的异常识别精度与鲁棒性。