稠密子图抽取及其应用
发布时间：2021-08-04 02:58
随着信息技术的发展,大量的数据使用图来建模实体之间的关系。从复杂的图数据中挖掘出有效的信息具有重要的理论意义和应用价值。稠密子图抽取是图数据挖掘的基本任务之一,目标在于从复杂的图中,抽取出结点间连接紧密的子图,被广泛地应用在社交网络、生物信息学和社会学等领域中。本文提出一种基于最大加权k-团密度的稠密子图抽取方法。首先定义了加权k-团密度来衡量子图的稠密程度,然后提出了最大加权k-团密度问题,一种新的稠密子图抽取方式。对于最大加权k-团密度问题,本文设计了一个多项式时间复杂度的精确算法,通过将问题分解为一系列的最小割问题来求解。同时,本文还设计了一个更高效的近似算法,并证明了该近似算法的近似比。在大量数据集上的实验表明,提出的基于最大加权k-团密度的稠密子图抽取方法能够有效地抽取出稠密子图,并且抽取出的子图的密度都要优于现有的稠密子图抽取方法。最后,本文将稠密子图抽取方法应用于异常检测的特征选择任务上。通过构造特征异常图,来捕获特征本身和特征对组合的异常度。在特征异常图上使用提出的稠密子图抽取算法进行稠密子图抽取,抽取出的子图顶点即代表与异常检测相关的特征。实验表明,该算法能够有效过滤...
【文章来源】：华南理工大学广东省 211工程院校 985工程院校 教育部直属院校
【文章页数】：67 页
【学位级别】：硕士
【部分图文】：
桶队列结构示意图
华南理工大学硕士学位论文14就将以父节点为根的子树，从树中移除，挂在根链表中。同时，如果修改后的值比当前min指针指向的节点值还小，需要更新min指针。整个操作的时间复杂度为(1)。图2-2斐波那契堆修改顶点示例图2-2给出了修改节点的值的操作过程。节点填充白色，表示标志位为假，填充黑色表示标志位为真。对节点蓝色方框内的节点的值进行减少，变为3。由于破坏了最小堆性质，因此将以其为根的子树，整个挂到根链表中，更新父节点的标志位为真，所以值为7的节点被填充上黑色。而因为3比当前min指针指向的4还小，因此，更新min指针指向3。而斐波那契堆删除最小节点是最复杂的操作。首先把最小节点的所有子树都直接挂在根链表中。接着和二项堆类似，需要将所有度相等的树合并，直到没有度相等的树存在。整个操作的时间复杂度为(log).2.3稠密子图抽取基准算法在这个小节中，主要介绍常用的几种稠密子图抽取算法。这些算法将会在实验小节中和本文提出的算法，在大量数据集上进行对比。基于边的抽取方法Goldberg[12]提出平均边度1来衡量一个子图的稠密程度，并提出了最大平均边度问题，即在给定图中找到一个平均边度最大的子图。通过构造一个特殊的流网络，将最大化平均边度的优化问题转化为一系列在流网络上的最大流最小割问题来求解，通过二分法不断逼近图中最稠密的子图的平均边度。这个基于最大平均边度的稠密子图抽取算法被称为DS算法（densestsubgraph）。
华南理工大学硕士学位论文16定义2-2（TGDS问题）给定一个无向图1=(1,1)，在其构造的三角形图′=(′,′)中找到一个子图，使得平均顶点权重最大：maxV′∑()∈||(2-9)其中顶点的权重()被定义为顶点在图1所对应的三角形的边集合中，参与的三角形数量最小的边，其参与的三角形个数。对于TGDS问题，Nikolentzos通过二分法搜索最大密度，将最大化三角形图密度函数分解为一系列超模优化，该算法简称为精确TGDS算法。精确TGDS算法的整体算法复杂度较高，为(||32+(|()|5(|()|+||)+|()|6)log|()|)。图2-3输入图转换成三角形图示例Nikolentzos同时也提供了一种基于贪心策略的近似算法。在该贪心算法的每次迭代中，都从三角形图′中选择权重最小的顶点从图中删除，直到删除所有的顶点。然后，保留下迭代删除过程中产生的子图中三角形图密度最高的作为稠密子图。基于准团的抽取方法Tsourakakis[16]使用了准团密度来表示图的稠密程度，给定一个无向图=(,)和参数α∈(0,1)，V1V，定义准团密度为α(V1)=|E1|α(|V1|2)(2-10)其中E1是由顶点集V1诱导的子图1=(1,1)的边集。参数α控制抽取的稠密子图的稠密程度的参考值。基于准团密度，Tsourakakis提出了最优准团问题：定义2-3（最优准团问题）给定一个无向图1=(1,1)和参数，找到一个子图=(,)使得准团密度最大:maxV1()(2-11)
本文编号：3320862
【文章来源】：华南理工大学广东省 211工程院校 985工程院校 教育部直属院校
【文章页数】：67 页
【学位级别】：硕士
【部分图文】：
桶队列结构示意图
华南理工大学硕士学位论文14就将以父节点为根的子树，从树中移除，挂在根链表中。同时，如果修改后的值比当前min指针指向的节点值还小，需要更新min指针。整个操作的时间复杂度为(1)。图2-2斐波那契堆修改顶点示例图2-2给出了修改节点的值的操作过程。节点填充白色，表示标志位为假，填充黑色表示标志位为真。对节点蓝色方框内的节点的值进行减少，变为3。由于破坏了最小堆性质，因此将以其为根的子树，整个挂到根链表中，更新父节点的标志位为真，所以值为7的节点被填充上黑色。而因为3比当前min指针指向的4还小，因此，更新min指针指向3。而斐波那契堆删除最小节点是最复杂的操作。首先把最小节点的所有子树都直接挂在根链表中。接着和二项堆类似，需要将所有度相等的树合并，直到没有度相等的树存在。整个操作的时间复杂度为(log).2.3稠密子图抽取基准算法在这个小节中，主要介绍常用的几种稠密子图抽取算法。这些算法将会在实验小节中和本文提出的算法，在大量数据集上进行对比。基于边的抽取方法Goldberg[12]提出平均边度1来衡量一个子图的稠密程度，并提出了最大平均边度问题，即在给定图中找到一个平均边度最大的子图。通过构造一个特殊的流网络，将最大化平均边度的优化问题转化为一系列在流网络上的最大流最小割问题来求解，通过二分法不断逼近图中最稠密的子图的平均边度。这个基于最大平均边度的稠密子图抽取算法被称为DS算法（densestsubgraph）。
华南理工大学硕士学位论文16定义2-2（TGDS问题）给定一个无向图1=(1,1)，在其构造的三角形图′=(′,′)中找到一个子图，使得平均顶点权重最大：maxV′∑()∈||(2-9)其中顶点的权重()被定义为顶点在图1所对应的三角形的边集合中，参与的三角形数量最小的边，其参与的三角形个数。对于TGDS问题，Nikolentzos通过二分法搜索最大密度，将最大化三角形图密度函数分解为一系列超模优化，该算法简称为精确TGDS算法。精确TGDS算法的整体算法复杂度较高，为(||32+(|()|5(|()|+||)+|()|6)log|()|)。图2-3输入图转换成三角形图示例Nikolentzos同时也提供了一种基于贪心策略的近似算法。在该贪心算法的每次迭代中，都从三角形图′中选择权重最小的顶点从图中删除，直到删除所有的顶点。然后，保留下迭代删除过程中产生的子图中三角形图密度最高的作为稠密子图。基于准团的抽取方法Tsourakakis[16]使用了准团密度来表示图的稠密程度，给定一个无向图=(,)和参数α∈(0,1)，V1V，定义准团密度为α(V1)=|E1|α(|V1|2)(2-10)其中E1是由顶点集V1诱导的子图1=(1,1)的边集。参数α控制抽取的稠密子图的稠密程度的参考值。基于准团密度，Tsourakakis提出了最优准团问题：定义2-3（最优准团问题）给定一个无向图1=(1,1)和参数，找到一个子图=(,)使得准团密度最大:maxV1()(2-11)
本文编号：3320862
本文链接：https://www.wllwen.com/kejilunwen/yysx/3320862.html
