摘要:现实生活中的网络通常存在社区结构,社区查询是图数据挖掘的基本任务.现有研究工作提出了多种模型来识别网络中的社区,如基于k-核的模型和基于k-truss的模型.然而,这些模型通常只限制社区内节点或边的邻居数量,忽略了邻居之间的关系,即节点的邻域结构,从而导致社区内节点的局部稠密性较低.针对这一问题,将节点的邻域结构信息融入k-核稠密子图中,提出一种基于邻域连通k-核的社区模型,并定义了社区的稠密度.基于这一新模型,研究了最稠密单社区查询问题,即返回包含查询节点集且具有最高稠密度的社区.在现实生活图数据中,一组查询节点可能会分布在多个不相交的社区中.为此,进一步研究了基于稠密度阈值的多社区查询问题,即返回包含查询节点集的多个社区,且每个社区的稠密度不低于用户指定的阈值.针对最稠密单社区查询和基于稠密度阈值的多社区查询问题,首先定义了边稠密度的概念,并提出了基于边稠密度的基线算法.为了提高查询效率,设计了索引树和改进索引树结构,能够支持在多项式时间内输出结果.通过与基线算法在多组数据集上的对比,验证了基于邻域连通k-核的社区模型的有效性和所提出查询算法的效率.

摘要:超图是普通图的泛化表示, 在许多应用领域都很常见, 包括互联网、生物信息学和社交网络等. 独立集问题是图分析领域的一个基础性研究问题, 传统的独立集算法大多都是针对普通图数据, 如何在超图数据上实现高效的最大独立集挖掘是一个亟待解决的问题. 针对这一问题, 提出一种超图独立集的定义. 首先分析超图独立集搜索的两个特性, 然后提出一种基于贪心策略的基础算法. 接着提出一种超图近似最大独立集搜索的剪枝框架即精确剪枝与近似剪枝相结合, 以精确剪枝策略缩小图的规模, 以近似剪枝策略加快搜索速度. 此外, 还提出4种高效的剪枝策略, 并对每种剪枝策略进行理论证明. 最后, 通过在10个真实超图数据集上进行实验, 结果表明剪枝算法可以高效地搜索到更接近于真实结果的超图最大独立集.

摘要:近年来,将卷积神经网络推广到图数据上的图卷积神经网络引起了广泛关注,主要包括重新定义图的卷积和池化操作.由于图数据只能表达二元关系的局限性,使其在实际应用中表现欠佳.相比之下,超图能够捕获数据的高阶相关性,利用其灵活的超边易于处理复杂的数据表示.然而,现有的超图卷积神经网络还不够成熟,目前尚无有效的超图池化操作.因此,提出了带有自注意机制的超图池化网络,使用超图结构建模,通过引入自注意力的超图卷积操作学习带有高阶数据信息的节点隐藏层特征,再经过超图池化操作选择并保留在结构和内容上的重要节点,进而得到更准确的超图表示.在文本分类、菜肴分类和蛋白质分类任务上的实验结果表明:与目前多种主流方法相比,该方法均取得了更好的效果.

摘要:随着大数据和机器学习的火热发展，面向机器学习的分布式大数据计算引擎随之兴起.这些系统既可以支持批量的分布式学习，也可以支持流式的增量学习和验证，具有低延迟、高性能的特点.然而，当前的一些主流系统采用了随机的任务调度策略，忽略了节点的性能差异，因此容易导致负载不均和性能下降.同时，对于某些任务，如果资源要求不满足，则会导致调度失败.针对这些问题，提出了一种异构任务调度框架，能够保证任务的高效执行和被执行.具体来讲，该框架针对任务调度模块，围绕节点的异构计算资源，提出了概率随机的调度策略resource-Pick_kx和确定的平滑加权轮询算法.Resource-Pick_kx算法根据节点性能计算概率，进行概率随机调度，性能高的节点概率越大，任务调度到此节点的可能性就越高.平滑加权轮询算法在初始时根据节点性能设置权重，调度过程中平滑加权，使任务调度到当下性能最高的节点上.此外，对于资源不满足要求的任务场景，提出了基于容器的纵向扩容机制，自定义任务资源，创建节点加入集群，重新完成任务的调度.通过实验在benchmark和公开数据集上测试了框架的性能，相比于原有策略，该框架性能提升了10%-20%.

摘要:动态变化的图数据在现实应用中广泛存在，有效地对动态网络异常数据进行挖掘，具有重要的科学价值和实践意义.大多数传统的动态网络异常检测算法主要关注于网络结构的异常，而忽视了节点和边的属性以及网络变化的作用.提出一种基于图神经网络的异常检测算法，将图结构、属性以及动态变化的信息引入模型中，来学习进行异常检测的表示向量.具体地，改进图上无监督的图神经网络框架DGI，提出一种面向动态网络无监督表示学习算法Dynamic-DGI.该方法能够同时提取网络本身的异常特性以及网络变化的异常特性，用于表示向量的学习.实验结果表明，使用该算法学得的网络表示向量进行异常检测，得到的结果优于最新的子图异常检测算法SpotLight，并且显著优于传统的网络表示学习算法.除了能够提升异常检测的准确度，该算法也能够挖掘网络中存在的有实际意义的异常.

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

摘要:图结构聚类（SCAN）是一种著名的基于密度的图聚类算法，该算法不仅能够找到图中的聚类结构，而且还能发现图中的Hub节点和离群节点.然而，随着图数据规模越来越大，传统的SCAN算法的复杂度为O（m1.5）（m为图中边的条数），因此很难处理大规模的图数据.为了解决SCAN算法的可扩展性问题，提出一种基于MapReduce的海量图结构聚类算法MRSCAN，这是一种计算核心节点以及两种合并聚类的MapReduce算法.最后，在多个真实的大规模图数据集上进行实验测试，实验结果验证了算法的准确性、有效性以及可扩展性.

摘要:社交关系的数据挖掘一直是大图数据研究领域中的热门问题.图聚类算法如SCAN （structural clustering algorithm for network）虽然可以迅速地从海量图数据中获得关系紧密的社区结构，但这类社区往往只表示了社交对象的聚集，无法反馈对象间的真实社交关系，如家庭成员、同事、同学等.要获取对象间真实的社交关系，需要更多维度地挖掘现实中社交对象间复杂的交互关系.对象间的交互维度很多，例如通话、见面、微信、电子邮件等，而传统SCAN等聚类算法仅能够挖掘单维度的交互数据.在研究社交对象间的多维社交关系图数据与传统图结构聚类算法的基础上，提出了一种有效的子空间聚类算法SCA （subspace cluster algorithm），对多维度下子空间的图结构聚类进行研究，目的是探索如何通过图数据挖掘发现对象间真实的社交关系.SCA算法遵循自底向上的原则，能够发现社交图数据中所有子空间的聚类集.为提升SCA的运行速度，利用其子空间聚类的单调性进行了性能优化，进而提出了剪枝算法SCA+.最后进行了大规模的性能测试实验以及真实数据的案例研究，其结果验证了算法的效率和效用.

摘要:智能手机、车载GPS终端、可穿戴设备产生了海量的轨迹数据，这些数据不仅描述了移动对象的历史轨迹，而且精确地反映出移动对象的运动特点.已有轨迹预测方法的不足在于：不能同时兼具预测的准确性和时效性，有效的轨迹预测受限于路网等局部空间范围，无法处理复杂、大规模位置数据.为了解决上述问题，针对海量移动对象轨迹数据，结合频繁序列模式发现的思想，提出了基于前缀投影技术的轨迹预测模型PPTP（prefix projection based trajectory prediction model），包含两个关键步骤：（1）挖掘频繁轨迹模式，构造投影数据库并递归挖掘频繁前序轨迹模式；（2）轨迹匹配，以不同频繁序列模式作为前缀增量式扩展生成频繁后序轨迹，将大于最小支持度阈值的最长连续轨迹作为结果输出.算法的优势在于：可以通过较短的频繁序列模式，增量式生成长轨迹模式；不会产生无用的候选轨迹，弥补频繁模式挖掘计算代价较高的不足.利用真实大规模轨迹数据进行多角度实验，表明PPTP轨迹预测算法具有较高的预测准确性，相对于1阶马尔可夫链预测算法，其平均预测准确率可以提升39.8%.基于所提出的轨迹预测模型，开发了一个通用的轨迹预测系统，能够可视化输出完整的轨迹路线，为用户路径规划提供辅助决策支持.

摘要:极大二团枚举问题是二部图分析中的一个基本研究问题. 然而, 在实际应用中, 传统二团模型要求子图必须为完全二部图的约束往往过于严格, 因此需要一些更为宽松的二团模型作为代替. 为此, 提出一种新的称之为k-缺陷二团的松弛二团模型. 该模型允许二部图子图与完全子图二团最多相差k条边. 由于极大k-缺陷二团枚举问题属于NP-难问题, 设计高效的枚举算法是一项极具挑战性的任务. 为解决此问题, 提出一种基于对称集合枚举的算法. 该算法的思想是通过k-缺陷二团中缺失边的数量约束来控制子分支的数量. 为进一步提高计算效率, 还提出一系列优化技术, 包括基于排序的子图划分方法、基于上界的剪枝方法、基于线性时间的更新技术以及分支的优化方法. 此外, 提出的优化算法的时间复杂度与${mathrm{O}}(gamma _k^n) $有关, 其中${gamma _k} lt 2 $, 突破了传统${mathrm{O}}({2^n}) $的时间复杂度. 最后, 大量的实验结果表明, 在大部分参数条件下所提方法的效率相较于传统分支定界方法提高了100倍以上.