基于结构一致性的图聚集算法研究
发布时间：2021-06-29 17:15
在社交网络、分子生物学、通信网络和许多其他领域通常面对具有数亿个顶点和数十亿条边的图。随着图数据的增长,挖掘和可视化这些大图成为具有挑战性的任务。大多数图算法的运行时间随着输入图的大小（节点和/或边的数量）而增长。当输入图太大而无法在内存中进行操作时,执行这些巨大的图是不切实际的。图聚集将原图中的节点和边进行聚集,多个节点聚集成一个超点,超点与超点之间的连接形成超边,从而形成一个简洁的超图,同时保留原图中大部分结构或属性信息。图聚集通过创建图数据的简洁表示来加速分析。由于结构复杂和图尺寸的增加,如何对大图数据进行高效的概括,发现一致的或有趣的结构,仍需要进行细致、系统性的研究。本文首先从简单图入手,提出的简单图聚集算法不仅考虑分组内或分组间的结构一致性,而且考虑聚集图边上存在的概率。通过压缩率衡量输入图的压缩程度,采用重构误差来量化原图与聚集图之间的相似性。基于信息熵度量结构一致性,优选节点间或节点内非常稠密或非常稀疏的结构。设计了一种通过行列交换逐步逼近目标函数的启发式方法,引入信息增益以减少计算量。基于简单图聚集的研究,进一步扩展到加权图和有向图。研究加权图聚集过程中,通过统计加权...
【文章来源】：昆明理工大学云南省
【文章页数】：74 页
【学位级别】：硕士
【部分图文】：
算法GSum_E描述基于信息熵的简单图聚集算法中核心操作是将个节点循环调至个不同的分组，其时间复杂度为()
谓?组中的节点调至组中，即邻接矩阵中行组中的行插入到行组中，列组中的列插入到列组中。节点调整前后聚集图邻接矩阵中信息熵的变化即为行列组和行列组中信息熵的变换，因此只需计算行列组和行列组中信息熵的变化即可，根据简单图的邻接矩阵的对称性可知需要计算(21)个盒子的信息熵。如图3.8(b)所示，只需要计算阴影部分盒子里的信息熵的变化即可，因此引入信息增益的概念。从而在很大程度上减少了计算量。基于信息增益的简单图聚集算法GSum_EG(GraphSummaryBasedonEntropyGain)如图3.7所示。图3.7算法GSum_EG描述基于信息增益的简单图聚集算法中核心操作是将个节点循环调至个不同的分组，其时间复杂度为()。在节点调至不同分组的过程中，计算每个节点在不同分组中的信息增益的时间复杂度为(),因此整体的时间复杂度为(2)。Input：Theoriginalgraph=(,)thenumberofsupernodeOutput：Theaggregationgraph=(,,p)1：/*InitializationStage*/2：Initializethemapbetweenanodeidanditslabel.3：ComputeBnz、Bszattheinitialdatadistribution4：Computetheentropyafterrandomgrouping5：/*dowhileloopgetthegroupwiththesmallestentropy*/6：for(inti=0;i<|V|;i++)7：for(intNewLabel=0;NewLabel<k;NewLabel++)8：if(NewLabel!=Label)9：NId"slabelshuffle10：updateBnz、Bsz11：endif12：calculatetheentropygain(EntGain)afterthenewgrouping13：if(EntGain>MaxEntGain)14：updatingthevalueofMaxEntGainandFinalLabel15：endif16：endfor17：endfor18：Calculatethereconstructionerroroftheoptimalgroup19：CalculatetheconnectionprobabilityPonthesuperedge20：Outputagg
第三章简单图聚集算法25法还能发现稀疏的分组，如二部图。图3.9Cave图聚集结果示例图3.10二部图聚集结果示例进一步地，在实际的DBLP数据集上的实验结果如图3.11所示，其中设为3，图3.11右边的超图节点编号0对应的是原图节点红色分组，1对应的是蓝色，2对应的是绿色。可以观察到，我们发现了如绿色分组2所示的稠密的图结构、如红色分组0所示次稠密的图结构，以及蓝色分组1所示稀疏的图结构（大多是较短的链式结构）。
【参考文献】：
期刊论文
[1]一种有效的加权图聚集算法[J]. 胡宝丽,游进国,周翠莲,王洋,崔红波. 中国科学技术大学学报. 2016(03)
[2]一种新的高效图聚集算法[J]. 尹丹,高宏,邹兆年. 计算机研究与发展. 2011(10)
硕士论文
[1]加权图聚集算法研究[D]. 胡宝丽.昆明理工大学 2016
[2]基于条件熵的图聚集算法研究[D]. 潘秋萍.昆明理工大学 2014
[3]图聚集算法与聚集图质量评价算法研究[D]. 尹丹.哈尔滨工业大学 2011
本文编号：3256828
【文章来源】：昆明理工大学云南省
【文章页数】：74 页
【学位级别】：硕士
【部分图文】：
算法GSum_E描述基于信息熵的简单图聚集算法中核心操作是将个节点循环调至个不同的分组，其时间复杂度为()
谓?组中的节点调至组中，即邻接矩阵中行组中的行插入到行组中，列组中的列插入到列组中。节点调整前后聚集图邻接矩阵中信息熵的变化即为行列组和行列组中信息熵的变换，因此只需计算行列组和行列组中信息熵的变化即可，根据简单图的邻接矩阵的对称性可知需要计算(21)个盒子的信息熵。如图3.8(b)所示，只需要计算阴影部分盒子里的信息熵的变化即可，因此引入信息增益的概念。从而在很大程度上减少了计算量。基于信息增益的简单图聚集算法GSum_EG(GraphSummaryBasedonEntropyGain)如图3.7所示。图3.7算法GSum_EG描述基于信息增益的简单图聚集算法中核心操作是将个节点循环调至个不同的分组，其时间复杂度为()。在节点调至不同分组的过程中，计算每个节点在不同分组中的信息增益的时间复杂度为(),因此整体的时间复杂度为(2)。Input：Theoriginalgraph=(,)thenumberofsupernodeOutput：Theaggregationgraph=(,,p)1：/*InitializationStage*/2：Initializethemapbetweenanodeidanditslabel.3：ComputeBnz、Bszattheinitialdatadistribution4：Computetheentropyafterrandomgrouping5：/*dowhileloopgetthegroupwiththesmallestentropy*/6：for(inti=0;i<|V|;i++)7：for(intNewLabel=0;NewLabel<k;NewLabel++)8：if(NewLabel!=Label)9：NId"slabelshuffle10：updateBnz、Bsz11：endif12：calculatetheentropygain(EntGain)afterthenewgrouping13：if(EntGain>MaxEntGain)14：updatingthevalueofMaxEntGainandFinalLabel15：endif16：endfor17：endfor18：Calculatethereconstructionerroroftheoptimalgroup19：CalculatetheconnectionprobabilityPonthesuperedge20：Outputagg
第三章简单图聚集算法25法还能发现稀疏的分组，如二部图。图3.9Cave图聚集结果示例图3.10二部图聚集结果示例进一步地，在实际的DBLP数据集上的实验结果如图3.11所示，其中设为3，图3.11右边的超图节点编号0对应的是原图节点红色分组，1对应的是蓝色，2对应的是绿色。可以观察到，我们发现了如绿色分组2所示的稠密的图结构、如红色分组0所示次稠密的图结构，以及蓝色分组1所示稀疏的图结构（大多是较短的链式结构）。
【参考文献】：
期刊论文
[1]一种有效的加权图聚集算法[J]. 胡宝丽,游进国,周翠莲,王洋,崔红波. 中国科学技术大学学报. 2016(03)
[2]一种新的高效图聚集算法[J]. 尹丹,高宏,邹兆年. 计算机研究与发展. 2011(10)
硕士论文
[1]加权图聚集算法研究[D]. 胡宝丽.昆明理工大学 2016
[2]基于条件熵的图聚集算法研究[D]. 潘秋萍.昆明理工大学 2014
[3]图聚集算法与聚集图质量评价算法研究[D]. 尹丹.哈尔滨工业大学 2011
本文编号：3256828
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3256828.html
