资源描述：
《顶点加权图的最密集子图算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、摘要摘要图作为一种能有效描述现实世界中各类实体之间复杂关系的数据结构，被广泛地应用于社会关系网络、合著者网络、通信网络、生物信息网络等实际领域。随着这些新兴大规模网络的快速发展，相关的各类应用不断地涌现和丰富，图数据也急剧地增长和频繁地更新，使得对大规模图的处理需求也愈加迫切。密集子图查询是图数据处理中的热点研究问题，在复杂网络分析中扮演着非常重要的角色。给定一个图，密集子图查询旨在寻找到有一定联系紧密程度的子图。然而，大部分现有的密集子图查询方法没有考虑顶点的权值的影响，在许多现实图中，顶点有不同重要性。例如，目前社交网络中，有很多QQ群，微信
2、群等等，如何计算一定范围内平均联系最密集的群可以转化为顶点加权图的最密集子图问题。而一个群的人数可以作为一个图的顶点的权值。本文引进了顶点加权图的最密集子图问题，并提出计算顶点加权图的最密集子图的多项式时间算法。提出的算法的基本思想是：给定一个顶点加权图G，假设最密集子图的密度为D，给D一个猜测的值为g，然后构建一个无向图，并且建立这个g值与该图一个最小割值的关系，然后通过二分法查找逐步求解D的值，最终找到顶点加权图G的最密集子图。进一步分析了该算法的时间复杂度和证明了该算法是正确的。然后通过仿真实验和实际图数据的实验来验证算法的有效性，得到相关
3、结论。并且针对数据量比较大的顶点加权图的最密集子图问题，提出了一种基于贪心策略的近似算法，该算法通过不断的迭代删除掉平均最小值的顶点，以得到近似的密集子图，并且证明了这个近似算法的近似比。关键词：最密集子图；顶点加权图；近似算法；多项式时间算法IABSTRACTAbstractAsadatastructurewhichcaneffectivelydescribethecomplexrelationshipsamongvariousentitiesintherealworld,graphiswidelyusedinsocialrelationsne
4、twork,co-authornetwork,communicationnetwork,biologicalinformationnetworkandotherpracticalfields.Withtherapiddevelopmentofthesenewlarge-scalenetworks,therelatedapplicationsareconstantlyemergingandenriched,andthedataofthemapareincreasingrapidlyandupdatedfrequently,makingthedema
5、ndforprocessingoflargescalegraphsmoreandmoreurgent.Thedensestsubgraphsqueryisahotresearchtopicingraphdataprocessing.Itplaysaveryimportantroleincomplexnetworkanalysis.Givenagraph,theproblemofthedensesubgraphisdesignedtofindasubgraphwithatleastsomedensity.However,mostexistingde
6、nsesubgraphalgorithmsdonottaketheinfluenceofweightsofverticesintoaccount.Inmanyrealisticgraphs,verticesareofdifferentimportance.Forexample,insocialnetworks,therearemanyQQgroups,WeChatgroups,andsoon.Theproblemofcalculatingthemostconnectedgroupsonaveragewithinacertainrangecanbe
7、transformedintothedensestsubgraphproblemofthevertex-weightedgraph.Andthenumberofmembersinagroupcanbetreatedastheweightofthevertexofagraph.Inthispaper,weproposetheproblemoffindingthedensestsubgraphs(DS)ofvertex-weightedgraphs,andpresentanalgorithmforthedensestsubgraphsofvertex
8、-weightedgraphs.Toourknowledge,noonestudiedthisproblem.Webegantostud
