面向大图的Top-Rank-K频繁模式挖掘算法

频繁模式挖掘(Frequent Pattern Mining,FPM)在社交分析中扮演重要角色,能从海量社交数据中挖掘用户行为的模式和规律,为社交网络的研究提供新的认识和决策支持.然而,对于一个FPM任务,设置一个合适的支持度阈值不容易;此外,FPM作为一个NP-hard问题,不存在多项式时间的算法.针对上述问题,提出一种无须用户设置初始支持度阈值的算法ItrMiner.该算法使用一种新的兴趣度指标对模式进行评估,综合考虑模式的大小和支持度,挖掘Top-Rank-K频繁模式.同时,为了解决去除初始支持度阈值后在算法剪枝阶段遇到的困难,提出基于树模式优先识别的策略和模式扩展约束策略,减少非必要候选模式的生成.在真实图和人工合成图数据集上进行了广泛的实验,证明ItrMiner在执行效率和可扩展性方面表现出色,尤其在稠密的数据集上,其时间开销仅为基线算法Top-K Graph Miner的13.2%.另外,提出的模式扩展约束策略的有效性较高,和无扩展约束优化的ItrMiner_(nopt)算法相比,效率提升最高可达9.5倍.

基于Motif的图采样算法

图采样通过对图数据进行约简操作,获得比原图的规模更小的图结构,进而服务于图谱分析、图可视化等下游任务.现有的图采样算法侧重于保留图中显著的结构特征而忽略了节点属性,导致采样图在许多下游任务如频繁模式挖掘等,难以取得预期效果.为此,提出基于Motif的节点有偏采样算法(Motif-Based Node Biased Sampling,MNBS),利用频繁Motif结构重新定义图中节点的重要性,随后进行有偏节点采样,实现融合节点属性与结构特征的采样.为了快速识别频繁Motif模式,设计了具有“提前终止”特性的Motif模式快速发现算法(Fast Motif-Pattern Discovery,FMPD),能高效且准确地发现Motif模式以支持图采样.实验表明,MNBS采样算法在多项指标上优于其他基线算法,其对数归一化累积组相关性指标平均降低0.54,使用包含“提前终止”特性策略的FMPD算法的时间消耗和内存消耗比基线算法分别降低56.1%和29.8%.