基于图压缩的最大steiner连通k核查询处理-李鸣鹏.pdf

《基于图压缩的最大steiner连通k核查询处理-李鸣鹏.pdf》由会员分享，可在线阅读，更多相关《基于图压缩的最大steiner连通k核查询处理-李鸣鹏.pdf（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、基于图压缩的最大Steiner连通k核查询处理李鸣鹏高宏邹兆年哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨 150001摘要：研究了基于图压缩的最大Steiner连通k核查询处理，提出了一种支持最大Steiner连通k核查询的图压缩算法SC，证明了基于SC压缩算法的查询正确性.由于最大Steiner连通k核查询仅需要找到符合要求的连通区域，提出了图压缩算法TC，进一步将压缩图压缩为树.证明了基于压缩树的查询正确性，并提出了线性时间的无需解压缩的查询处理算法.真实和虚拟数据上的实验结果表明：压缩算法平均可将原始图压缩掉88，且对于稠密的原始图，压缩算法的压缩效果更好，可将原始图压缩掉90，与

2、在原始图上直接进行查询处理相比，基于压缩图的查询处理算法效率更好，平均提升了12个数量级.最大Steiner连通k核；图压缩；等价类；查询处理；压缩比TP31110.13328/ki.jos.005044Maximum Steiner Connected k-Core Query Processing Based on Graph CompressionLI Ming-PengGAO Hong ZOU Zhao-NianSchool of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001

3、, ChinaAbstract: This paper focuses on maximum Steiner connected k-core query processing based on graph compression, and proposes a maximum Steiner connected k-core query preserving graph compression algorithm, SC. The correctness of querying based on SC algorithm is proved. Since maximum Steiner co

4、nnected k-core query only requires a connected component which satisfies certain properties, graph compression algorithm TC is proposed to further compact the compressed graph into a tree. It is proved that querying based on the compacted tree is correct. A novel linear query processing algorithm wh

5、ich is able to query on the compacted tree without decompression is also introduced. Experiments on both real and synthetic datasets demonstrate that the compression algorithm could compress the original graph by 88 in average, and for denser graphs, the compression algorithm achieves better compres

6、sion ratio, reducing the original graph by nearly 90. Comparing with the query processing on original graphs, the query performance on compressed graphs is better, and in average, it could be 1 to 2 orders of magnitude times better.maximum Steiner connected k-core; graph compression; equivalent clas

7、s; query processing; compression ratio基金项目：国家重点基础研究发展计划(973)(2012CB316200);国家自然科学基金(61190115，61033015，61173023);中央高校基本科研业务费专项(HIT.NSRIF.201180)Foundation item: National Basic Research Program of China (973) (2012CB316200); National Natural Science Foundation of China (61190115, 61033015, 61173023);

8、Fundamental Research Funds for the Central Universities (HIT.NSRIF.201180)2015-09-242016-02-22万方数据2266 Journal of Software软件学报V0127，No9，September 2016用户的社会行为【21；在作者合作网络中，一群联系密切的人可能具有相近的研究领域【31；在购物数据中，组关系密切的商品很可能被兴趣相近的客户所关注41；在蛋白质网络中，一些关系紧密的蛋白质往往可能共同形成特定的官能团【51目前，对于紧密社团【6的定义有许多种，如：团、七团、滩团、k丛等上述问题均是NP

9、hard的，故计算以上的紧密社团将非常耗时而k核作为一种社团的定义，则可以被有效地在线性时间内计算对于无向图G=(K目，k核是图G的一个极大子图，满足子图内的顶点都至少有k个邻居出现在子图中例如在图1(a)中，8,9，1l，12，14)的导出子图就是一个3核，因为每个顶点在导出子图中都至少有3个邻居作为一种紧密社团，k核有着广泛的应用：七核可以作为一种拓扑结构信息用于网络分析7和网络可视化8】；扣1核还可以用于近似表示k团：七核还可以用于给出最稠密子图的12近似【9】以及最稠密至少k子图的13近似算法【lo】事实上，在很多应用中，用户往往更加关心包含一组给定查询顶点Q的连通的k核由于满足上述要

10、求的k核并不唯一，而其中最稠密的往往最有意义，故本文所关注的是包含给定查询顶点集Q且具有最大k值的连通k核，简称为k-MSC仍以图1(a)为例，若给定查询顶点集Q=4，8，15，那么包含Q的k-MSC为91，是一个2核(b)压缩图GcFig1 Instances of graph compression图1 图压缩实例本文首先提出了k-MSC问题，而现有方法并不能有效地解决k-MSC问题这是因为：(1)枚举包含Q的所有导出子图，并找到其中k值最大的连通k核，将访问指数级别数量的子图，故并不可行；(2)借助于现有计算k核的最快算法【l，一种直观的算法(Base)n-I以通过不断递减k的值，然后检

11、查是否存在一个连通的k核包含了Q中的全部顶点为保证连通性，上述过程每次都需要遍历整个图，当原始图规模很大时，该计算将变得非常耗时本文使用图压缩以及压缩图上直接进行查询处理的技术来解决k-MSC问题其思想是：首先将图G进行压缩，得到一个规模很小的压缩图Gc；然后，对于任意G上的k-MSC查询(G，Q)，将其转换成Gc上的等价查询(Gc，Qc)，使得G上对Q的查询结果与Gc上对Qc的查询结果完全相同由于Gc的规模远小于G，故可以大幅提高查询处理效率，并节省存储空间文献1214中的图压缩技术将图中的邻接信息用bit表示，并通过适当的合并、调整顺序等操作令所使用的bit数最少，从而使得其对网络图和社交

12、网络的压缩效果非常可观然而上述方法仅仅关注了存储代价的降低而忽视了查询效率，这导致压缩图并不能直接被使用，即使是最简单的邻居查询，也需要将压缩图进行适当的解压缩才能够进行查询除了上述通用的图压缩技术，一些针对特定查询的图压缩技术也被提出【”_1 81文献15】提出了针对可达查询和图模拟查询的图压缩技术；文献【16探讨了在XML树中能够处理XPath查询的压缩方法；文献17】针对邻居查询，提出了具有误差保证的有损压缩技术然而，由于查询结构的差异，上述方法就不能适用于“MSC查询本文首先提出了图压缩算法sc，其时间复杂度为O(IEI)SC算法是基于等价类划分的，故查询转换的时间复杂度为O(IQI)

13、本文证明了基于压缩图Gc的查询正确性通过实验验证，sC算法可以有效地将原始图压缩掉一半以上；且对于稠密图，压缩效果将进一步提升，达到压缩掉近70对于道路交通网络和基于偏好模型的虚拟O卜“舌万方数据李鸣鹏等：基于图压缩的最大Steiner连通k核查询处理 2267图，SC算法可将原始图压缩掉近90由于k-MSC查询仅需要找到符合要求的连通区域，故SC算法得到的压缩图Gc还可被进一步压缩本文提出了图压缩算法TC，将压缩图Gc进一步压缩为树Gr，其时间复杂度为D(1VcI+IEc|)本文证明了基于压缩图Gr的查询的正确性，并提出了压缩树上无需解压缩的查询算法QueryGT,其时间复杂度为o(IRo

14、J)其中，I尺DI为查询结果集的大小通过实验验证：在真实数据集上，TC算法可进一步将SC算法的压缩比提升35倍与直接在原始图上查询的Base算法相比，基于压缩树的查询算法QueryGT的查询效率将提升l2个数量级本文的主要工作及贡献如下(1) 提出了一种支持k-MSC查询的图压缩算法SC以及相应的查询转换算法，证明了其正确性，SC算法的时问复杂度为OilEI)；(2) 在SC算法的基础上，提出了图压缩算法TC，将压缩图进一步压缩为树，证明了压缩树上查询结果的正确性，TC算法的时间复杂度为D(Ivcl+lecI)；(3) 提出了压缩树上的查询算法，其时间复杂度为o(IRo|)；(4) 分别在真实

15、数据和虚拟数据上验证了所提出图压缩算法的有效性真实数据集上的实验结果表明：压缩算法的压缩比可达到12；而对于稠密图，算法将取得更好的接近10的压缩比算法对于虚拟数据集同样有效，平均压缩比仍然在12左右；且压缩效果随着图稠密度的增加而提高对平均度数为30的虚拟图，压缩比为67基于压缩算法的查询算法效率也得到了很好的提升，无论在真实还是虚拟数据集上，查询效率与Base算法相比均提高了l2个数量级1相关工作网络图和社交网络的通用图压缩技术已经被广泛研究，文献12】的压缩技术能够有效地将网络图压缩，文献13，14】也可以将社交网络以bit的形式有效存储由于上述技术保存了原始图中全部的结构信息，即，并不

16、针对特定查询，且查询前必须进行解压缩操作，故反而降低了查询效率面对特定查询且无需解压缩即可查询的图压缩技术也被提出：文献151提出了能够处理可达查询和图模拟查询的图压缩技术，文献16币lJ用了双向模拟的思想提出了针对XPath查询的压缩技术，文献17则针对邻居查询给出了一种具有误差保证的有损压缩技术然而上述技术仅能处理特定的查询，因此无法适用于k-MSC查询对于给定图和一组查询顶点Q，围绕如何找到图中包含Q的社团也展开了一些研究【1 8-21】其中，文献18】提出了一种基于局部模块化的社团计算方法，文献19定义了基于k-truss的社团并给出了求解算法，文献20】研究了基于雕团定义的社团发现问

17、题由于对社团定义的差别，上述技术无法适用于k-MSC查询文献21研究了基于连通度定义的最大连通社团发现问题，并提出了SMCC索引提高查询性能本文将以SMCC索引作为对比，说明SC和TC算法的有效性2最大Steiner连通k核本文针对简单的无向无权图进行研究，即对于给定图G=(目，V是顶点集，是边集，那么图中不存在自环(甜，“)，其中，UE矿本文使用的图数据是以邻接表形式存储的，因此，图的规模lGl为邻接表中邻接顶点对的数量对于顶点UE以vK(“，v)和(v，“)表示同一条边，而由于(“，v)和(，“)分别在顶点U和v的邻接表中各出现一次，故图的规模IGI=21EI对于图G中的任意的顶点集MG明

18、表示的导出子图，即G明=(且(，v)eElu，vH”记图G中连接顶点U和v的简单路径为PiG，U，v)，则PiG，U，v)=“，Wl，W2，Wf，v)，其中，(“，W1)eE，(wf，v)eE，(wf，WHl)eE，0一p，而GW】中顶点的度不会小于前两者因此，我们找到了一个G明的超图G舢F】并且GHuI-I是pSC，矛盾!故而胙F，即，顶点甜和v一定出现在同一个k-MSC中 口结论1在图G=(KD中，若zf；v，则对于图G中任意一个最大Steiner连通k核G明，若“E则wH证明：根据引理1，易证该结论 口根据上述结论可知，属于相同等价类的顶点一定会出现在相同的k-MSC中这说明本文中等价关

19、系的定义是合理的定理1给定图G=(KD，Gc=(，Ec力是由SC算法计算的压缩图，若也是Gc中的一个k-MSC，则H是G中的一个k-MSC，其中，肛川vE“，UE如证明：用反证法若G旧不是一个k-MSC，则图G中要么存在一个G明的超图G【F】，使得G】是k-SC；要么存在一个G目】，使得GF，】的核值比G明更大首先讨论第1种情况由于GF是连通的，不妨假设wHV-Pl W与日相邻显然，W对应的等价类【w】c萑凰根据结论l可以发现：(1)GcH：Uw】c)是连通的；(2)GcH划wk)】的核值不小于Gc日d矛盾!故第一种情况是不存在的下面讨论第2种情况若存在一个核值更大的G目】，则记日：=“Vcl

20、vEu，vF根据sc算法，若(“，v)E，则(“k，Ivc)Ec，故Gc哦】一定是连通的因此，我们在压缩图Gc中找到了一个核值更大的k-SC，这意味着Gc中一定存在着一个核值更大的k-MSC矛盾!故第2种情况也是不存在的综上所述，可证结论 口定理2给定有向图G=(K司，查询顶点集Q，Gc=(Vc，Ec力是由SC算法计算的压缩图，Qc是Q对应的等价类集，则在原始图G上包含Q的缸MSC与在压缩图Gc上包含Qc的k-MSC是相同的证明：根据定理l，在压缩图Gc上包含Qc的k-MSC一定是原始图G中包含vlvEu，“Qc)的k-MSC下面只需证明在原始图中，查询顶点集Q和vlvEu，”Qc具有着相同的

21、k-MSC根据结论l，同一等价类中的顶点一定在同一个k-MSC中，故定理2得证 口22 SC算法的分析SC算法采用了基于等价类的压缩思想，因此，如何有效地划分等价类是SC算法的关键首先需要计算图中所有顶点的核值，根据文献1l】中的算法，通过使用桶排序，所有顶点核值的计算可以在D(吲)内完成见算法l第l行其次，为了划分等价类，将依次为每一个顶点分配唯一的类别根据定义5，lt=-V当且仅当图中存在P(u，v)，使得对于任意顶点wP(u，v)，旭(w)=cD理(“)=co陀(v)因此可以从任意的顶点U出发，采用广度优先搜索算法，不断地扩展与顶点“核值相同的顶点，直至无法扩展为止将上述顶点集划分为同一

22、等价类“c，同时标记为已访问至此顶点甜所在的等价类划分完毕对于图中剩余的等价类，只需要不断重复上述过程，直至图中所有顶点均被访问过为止，见算法1第3行第ll行显然，基于BFS的等价类划分可以在伏lED的时间内完成最后，通过依次访问原始图G中的每一条边，可以确定压缩图的边集显然，生成压缩图仍然可以在O(IEI)内完成故，图压缩算法sc的时间复杂度为O(IEI)算法1SCInput：Graph G=(以司；Output：Compressed Graph Gc=(，Ec力，Map List MKcoreO；万方数据2270 Journal of Software软件学报V0127，No9，Septe

23、mber 2016Vc=Ec=O；For each UEVdo IfU is not visited then BFS(core(u)；仅扩展与“核值相同的顶点 For each v expanded by BFS(core(u)do Mlvl=lulc； 1，is visited； end for廷多 vc=ZcUuc，贝甜】c)=co，(甜)； M“_M c，U is visited； endifend for For each veaex pair甜】cVc，v】cdo计算压缩图的边集 if(“，v)E then Ec=Ecu(uc，Mc)； end ifend forreturn Gc

24、=(，Ec)，M；值得注意的是：图压缩算法sc在返回压缩图Gc的同时还将返回一个映射表MM记录了原始图中每一个顶点所对应的等价类借助于M对于给定查询(G，Q)，可以在O(IQI)时间内将之转换为(Gc，Qc)，以用于进一步的查询处理由于M的规模为D(1吲)，故可将M存放于内存，且由于M的大小并不影响查询速度，故不将M计入压缩图另外，压缩图需要额外保存顶点的核值信息这是由于压缩后顶点的邻居信息不再完整，即：如果不保存核值信息，那么将无法从压缩图得到正确的k-MSC结果而在真实的图数据中，顶点的核值往往是比较小的，比如在Brightkite和Gowalla两个社交网络中，顶点的最大核值分别为52和

25、51而在道路交通网络中，顶点的核值更小，比如roadNetCA网络中，顶点最大核值仅为3这说明压缩图中用于保存顶点权值所占的空间是很小的，故在考查压缩比时，仍然以JEcIIEI为准3最大生成树压缩算法TC本文将在SC算法的基础上给出第2种图压缩算法TC，从而将压缩图Gf进一步压缩TC算法的大致思想为：将压缩图Gc中的边进行适当选择，得到一棵树G，=(Vr,En力，使得VfVc；且对于查询(GcQc)，通过计算(GnQc)可以得到相同的查询结果上述思想来自于对压缩图Gc上查询过程的观察在计算包含Qc的k-MSC时，可以分为两个步骤：(1)找到包含Qc的一个连通区域C，记C的权值为C中顶点权值最小

26、者，即以C)=Min状“)阻C，那么查询所要找到的C是所有包含Qc的连通区域中权值最大者；(2)在保持权值不变和连通的前提下，将C扩展至极大，得到且即为包含Qc的k-MSC根据k-MSC的定义和结论l，上述查询结果显然是正确的由于步骤(2)依然可以使用广度优先搜索算法实现，故问题的关键在于如何发现包含Qc且权值最大的连通区域e计算C可以进一步地分解为不断地构建连接Qc中顶点对的简单路径记Qc=ut,甜2，那么计算C就可以看作依次构建Pl条简单路径：P(“l，“2)，P(u1，“3)，P(ul，up)记每条简单路径尸的权值为P上顶点权值最小者，即(P)=Min(u)IuEP，那么查询所要找到的每

27、一条P(ul，“，)都是连接顶点材l和U，的所有简单路径中权值最大者万方数据李鸣鹏等：基于图压缩的最大Steiner连通k核查询处理 2271以图l(b)中的压缩图Gc为例，若查询顶点集为8，12，15，则转换后可知Qc=u3，“5那么查询过程分为以下两步：首先，找到包含U3,U5)的权值最大的连通区域，该过程可以进一步转换为计算权值最大的P(u3，“5)，易知，路径(“3，“4，“5)是符合条件的，因此C叠“3，U4，甜5)且贝o=2；最后，在保持连通性和权值不变的前提下，将c进一步扩展为“2，“3，“4，U5，那么Gc【22,3，U4，“5】就是最终的查询结果定义6给定图G=(V,E，聊，

28、W是边集E上的权值函数，G的子图Gl是一棵生成树当且仅当Gl是树且Gl包含了G中全部顶点，若Gl在所有生成树中具有最大的权值和，则Gl为最大生成树下面证明Gf(Vc，Ec刀的最大生成树G尸(Vr,En，)满足本文的查询要求，即：对于查询(Gc，Qc)，计算(GnQc)可以得到相同的查询结果这里需要强调的一点是：对于Ec中每条边(“，v)的权值，取(“，v)两端的顶点中权值较小者这是因为当路径P经过(“，v)时，苁P)一定不会超过U和v中权值较小者定理3给定图Gc=(，Ec力，G=(Vr,E胡是Gc的最大生成树，则对于顶点“vc，vVc，P(GnU，v)是图Gc中连接甜和v的权值最大的简单路径证

29、明：用反证法假设P(Gn“，v)在图Gc中不是权值最大的简单路径，那么一定存在一条权值更大的路径P，下面通过例子来说明以图l(c)为例，不妨设P(GnU，v)=(“2，U3，U6)，P|(“2，U4，甜6)那么向Gr中增加两条边(“2，U4)和(“6)，此时，Gr中至少产生了两个环首先找到路径P(GnU，v)上权值最小的边(“3，U6)并将之删除；然后，Gr中还存在着一个环继续删除剩余环中权值最小的边(“2，z，3)，得到一棵新的生成树G；在上述过程中，可以将插入边和删除边的操作配对，即：首先插入边(“4，“6)，随后产生环(甜3，U4，甜6)，再删除边(地，)破坏环得到新的生成树；然后插入边

30、(”2，材。)，产生环(“2，“3，U4)，再删除边(“2，的)得到G；因为P，的权值大于P(GnU，v)，故首次产生环并破坏环的操作一定使生成树的权值和增大又因为每次产生环并破坏环的操作一定不会令生成树的权值和减小，故G的权值和一定大于Gn所以G，不是最大生成树矛盾!故结论成立 口定理4给定图Gc=(Vc，Ec力，Gr=(VT,En)是Gc的最大生成树，则(Gc，Qc)与(GnQc)的查询结果相同证明：用构造法证明根据定理3，对于甜Qc，wQc，P(GnU，v)一定是图Gc中连接甜和v的权值最大的简单路径，那么对于Qc=ul，“2，up，通过依次构建P一1条简单路径：P(Gn“1，u2)，P

31、(GT,Ul，u3)，P(Gr,ul，up)，并据此形成的连通区域C=vlvP(Gn“l，“)，0一rain thenpush(Queue，v)，v is visited，胙麒Jv)；endifendforend whileReturnH：4实验结果2273在实验部分，本文在真实数据集上对两种图压缩算法SC和TC的有效性和查询效率进行了考查在考查压缩比时，使用SMCC索引作为对比；在考查查询效率时，使用了直接在原始图上查询的直观算法Base的查询算法作为对比为验证SC和TC算法的扩展性，本文还在虚拟数据集上检验了两种算法的压缩比和查询效率下面首先介绍实验考查的几种测度，包括压缩算法压缩比和查询

32、处理时间；随后介绍使用的实验数据、实验环境和对比实验；最后给出实验的对比及分析在考查算法的压缩比时，分别用CRsc和CRTc表示压缩算法Sc和TC算法的压缩比，其中，CRsc=IEcIIEI，CRTc=IETqIEI可知：当压缩比越小时，压缩图的规模也越小，说明压缩算法更加有效在考查查询处理时间时，对比了基于压缩树的查询处理算法QueryGT的时间开销与在原始图上直接进行查询的Base算法的时间开销为公平起见，Base算法并不计算原始图中顶点的核值，即，认为顶点核值也是Base算法的输入实验中使用的真实数据集来源于斯坦福大学的共享数据集(http：snapstanfordedudata#twi

33、tter)本文使用的数据规模在404K一239M之间，包括了以下网络：(1)EmailEnron，美国安然公司的邮件网络，其中，顶点表示邮箱，边表示某个邮箱向另一邮箱发送过邮件；(2)caAstroPh，天体物理学期刊Arxiv中的作者合作网络，其中，顶点表示作者，边表示两位作者合作过；(3)Brightkite和Gowalla，在线社交网络，其中，顶点表示用户，边表示朋友关系；(4)roadNetTX和roadNetCA，美国德克萨斯卅I和加利福尼亚州的道路交通网络，其中，顶点表示道路交汇点，边表示道路；(5)asSkitter,互联网拓扑图，其中，顶点表示网页，边表示超链接表1中给出了本文

34、所使用真实数据集的特性，其中，平均度数为IEIIVI，反映了图的稠密程度；最大核值为图中核值最大的顶点，反映了图中最稠密社团的稠密度实验所使用虚拟图是基于偏好模型生成的【2 41，即：图中顶点更容易和度数大的顶点共同组成一条边，而不容易和度数小的顶点组成边为了突出少数顶点的度数，图中将初始化一个规模为平均度数的团，为使虚拟图能适用于实验，将人为去掉图中的自环和多重边上述实验使用C+实现，在双核340GHz Intel Core(PM)D CPU、320GB内存、Window7系统的台式机上运行Table 1 Properties for real datasets表1 实验中使用真实数据集的基

35、本特性表2中给出了sC，Tc算法和SMCC索引在真实数据集上的压缩比实验结果表明：(1)图压缩算法的压缩万方数据2274 Journal of Software软件学报V0127，No9，September 20 1 6效果非常可观，且对于稠密图将取得更好的压缩比；(2)TC算法可以在SC算法的基础上进一步有效地压缩原始图首先可以发现：所提出图压缩算法的平均压缩比为12，而对于平均度数大于10的EmailEnron，ca-AstroPh和asSkitter，压缩Lk贝,U接近10其中，对于平均度数为211的作者合作网络caAstroPh，压缩图规模仅为原始图的39除道路交通网络外，最稀疏的Br

36、ightkite的压缩效果最差，但是也达到了178这是由于稠密图中往往会出现多个稠密区域，而这些稠密区域就很可能会被压缩算法归为同一个等价类，故本文的压缩算法对于稠密图更有效其次，除去道路网络图，可以发现，TC算法可以将SC算法得到的压缩图Gc进一步压缩3-5倍比如：对于as。skitter，SC算法可以将原始图压缩至421，而TC算法则可进一步将其压缩至105；而对于caAstroPh，尽管SC算法的压缩比已经比较客观，为194，但是TC算法仍然能进一步将压缩效果提升至39这说明两种算法都是必要的在道路交通网络中，尽管顶点的平均度数很小(往往不超过3)，但是由于道路交通网络中的稠密区域大部分

37、都很稀疏(这一点可以在表l中发现，roadNetTX和roadNetCA的最大核值均仅为3)，所以道路交通网络更加容易被基于等价类划分的SC算法压缩可以发现，TC算法在上述两个数据集上无法将SC算法得到的压缩图Gr进一步压缩这说明仅使用SC算法，就能够将道路交通网络图充分压缩与SMCC索引相比，本文所使用的图压缩算法具有更好的压缩性能SMCC索引的平均压缩比为33，这几乎是所提出算法的3倍可以发现：在Brightkite，Gowalla和asskitter上，SMCC索引的规模更小，仅为压缩图的15倍：而在roadNetTX和roadNetCA上，SMCC索引的规模都超过了原始图的70，这意味

38、着SMCC索引几乎无法将原始图压缩上述情况的出现是由于道路交通网络是十分稀疏且连通的，因此几乎可以看作一棵树，而SMCC索引的思想就是将原始图表示成树，故SMCC索引几乎不能缩减道路交通网络的规模Table 2 Compressed graph size and compression time of SC，TC and index size of SMCC on real datasets表2真实图数据上SC，TC的压缩图大小、压缩时间与的SMCC索引大小数据集 EmailEnron caAstroPh Brightkite Gowalla roadTX roadCA asskitter顶点

39、数 22 829 7 691 38 228 123 452 224 530 278 301 1 167 322边数 125 910 76 962 183 804 811 300 449 034 556 544 9 343 008SC压缩比() 342 194 429 427 117 101 421压缩时间(s) 0018 0029 O032 O184 O54 O80 451顶点数 22 829 7 69I 38 228 123 452 224 530 278 301 1 167 322边数45 574 15 334 76 392 246 902 449 034 556 544 2 334 62

40、6TC压缩比() 124 39 178 130 117 101 105压缩时间(s) 0019 0013 O025 018 008 011 268顶点数 36 692 18 772 58 228 196 591 1 379 917 1 965 206 1 696 415SMCC 边数 71 254 35 826 115 362 393 180 2 758 986 3 925 136 3 391 318压缩比() 194 90 269 207 718 70 9 153表2还给出了SC，TC算法的压缩时间，实验结果表明：两种压缩算法的压缩时间都很快速对于规模最大的roadCA和asskitter，

41、压缩算法分别可在1s和8s内完成图2给出了Base算法与基于压缩图的QueryGT算法在真实图上的查询时间对比，所使用的图包括Gowalla，roadNetTX和asskitter这是由于邮件网络EmaiEnrom、作者合作网络caAstroPh和在线社交网络Brightkite、Gowalla均具有相似的社交网络的特性，roadTx和roadCA均为道路网络，而asskitter则代表着网络图，故本文仅以3类图数据中规模较大的Gowalla，roadTX和asskitter为例考查基于压缩图的查询效率查询顶点集是1 000组随机生成的、大小从5增加至10的顶点集，查询时间是1 000组查询时

42、间的总和实验结果表明：(1)QueryGT的查询效率比Base提高了一至两个数量级；(2)两种算法的查询时间均随着给定查询顶点集大小蚓的增大而略有增加首先可以发现：对于Gowalla和roadNetTX，QueryGT的查询速度是Base的5060倍；而对于asskitter,QueryGT的查询效率则是Base的200倍左右这是由于图压缩算法不仅将原始图进行了有效地压缩，且保证了QueryGT在压缩图上查询时仅仅需要访问查询结果集中的顶点，因此查询效率得到极大的提升其次，当查询顶点集大Jlal从5增加至10时，两种算法的查询时间均有微小的增加这是因为随着查询顶万方数据李鸣鹏等：基于图压缩的最

43、大Steiner连通k核查询处理 2275点集的增大，查询结果将有可能变成核值更小、覆盖顶点更多的连通区域，这将使查询结果集变得更大，而两种算法的运行时间均与查询结果集大小相关，故查询时间会随之增加(a)Gowalla数据集 (b)roadNet-TX数据集 (c)as-skitter数据集Fig2 Query time of Base vsQueryGT on real datasets图2真实图数据上查询算法Base和QueryGT的对比图3(a)图3(d)给出了SC和TC算法在虚拟图上的压缩比，为了验证算法的扩展性，分别在顶点数为1M10M时，将虚拟图的边数从98M增加至274M(a)压

44、缩比结果，顶点数1M (b)压缩比结果，顶点数2M (C)压缩比结果，顶点数5M(d)压缩比结果，顶点数10M (e)压缩时间，顶点数5M (D压缩时间，顶点数10MFig3 Compression ratio and compression time of SC，TC on synthetic datasets图3虚拟图数据上SC，TC算法的压缩比与压缩时间实验结果表明：图压缩算法在虚拟图上仍然就有很好的压缩效果；且随着平均度数的增加，压缩图的规模更小即，算法更适用于稠密图首先可以发现：压缩算法在顶点数为1M10M的虚拟图上都取得了平均低于12的压缩比，这说明压缩算法可以将虚拟图有效地压缩；

45、当虚拟图的平均度数为20左右时(即边数为199M，423M，993M，224M时)，两张虚拟图压缩后的规模均在原始图规模的10左右其次，当顶点数固定、边数增加时，算法的压缩比从198降至67，且保持了单调下降的趋势这说明压缩算法更加适用于稠密图值得注意的一点是：在虚拟图上，SC和TC算法的压缩效果极为接近，这是由于在偏好模型下，少数度数较大的顶点将构成一万方数据1 Smith C. By the numbers: 98 amazing facebook statistics. DMR, 2014.2 Agrawal R, Rajagopalan S, Srikant R, Xu Y. Mini

46、ng newsgroups using networks arising from social behavior. In: Proc. of the WWW 2003.2003.万方数据 3 Lappas T, Liu K, Terzi E. Finding a team of experts in social networks. In: Proc. of the KDD 2009. 2009. 4 Yah X, Zhou X J, Han J. Mining closed relational graphs with connectivity constraints. In: Proc.

47、 of the KDD 2005. 2005. 5 Asthana S, King OD, Gibbons FD, Roth FP. Predicting protein complexmembership using probabilistic network reliability. Genome Research, 2004,14(6):1170-1175. 6 Hanneman RA, Riddle M. Introduction to Social Network Methods. University of California, Riverside, 2005. 7 Seidman SB. Network structure and minimum degre. Social Networks, 1983,5:269-287. 8 Bollobas B. The evolution of sparse graphs, in graph theory and combinatorics. In: Proc. of the Cambridge Combinatorial Conf. in Honor of Paul Erdos. Academic Press, 1984.35-57. 9 Kortsarz G, Peleg D. Gen