软件学报  2015, Vol. 26 Issue (1): 167-177   PDF    
图聚集技术的现状与挑战
潘秋萍, 游进国, 张志朋, 董朋志, 胡宝丽    
昆明理工大学 信息工程与自动化学院, 云南 昆明 650500
摘要:图聚集技术旨在获取能够涵盖原图大部分信息的简洁超图,用于提炼概要信息、解决存储消耗和社交隐私保护等问题.对当前的图聚集技术进行研究,综述了现有图聚集技术中的分组方法并对其进行分类,将分组标准划分为基于属性一致性、基于邻接分组一致性、基于关联强度一致性、基于邻接顶点一致性和基于零重建误差这5类;在高层次上将各分组标准概括为基于属性、基于结构和同时基于属性和结构的图聚集.较为全面地总结和分析了当前图聚集技术的研究现状和进展,并探讨了未来研究的方向.
关键词图数据     图聚集     分组标准     属性信息一致     结构信息一致    
Progress and Challenges of Graph Aggregation and Summarization Techniques
PAN Qiu-Ping, YOU Jin-Guo, ZHANG Zhi-Peng, DONG Peng-Zhi, HU Bao-Li    
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
Abstract: Graph aggregation and summarization is to obtain a concise supergraph covering the most information of the underlying input graph, and it is used to extract summarization, solve storage consumption and protect privacy in social networks. This paper investigates current graph aggregation and summarization techniques and further reviews and classifies their partitioning/grouping methods. Based on the consistency of grouping information, five grouping criteria are specified: The consistency of attribute information, the consistency of neighborhood group, the consistency of connection strength, the consistency of neighborhood vertex and reconstruction zero error. From the top level view, graph aggregation and summarization techniques can be classified into three types, namely, attribute similarity, structure cohesiveness and the hybrid of both. This paper comprehensively summarizes the state of art of current research works, and explores the research directions in the future.
Key words: graph data     graph aggregation     grouping criteria     consistency of attribute information     consistency of structure information    

图数据被广泛地应用于多种领域,用于描述事物之间的复杂关联,如各用户之间相互加为好友形成的社交网、各作者相互合作形成的学术研究网、各网页之间相互链接形成的Web网、各公路相互交错形成的公路网以及电力网、蛋白质交互网和语义网等[1, 2, 3].随着这些领域的发展和数据的增加,当前图数据应用面临如下挑战:

· 潜在信息很难获取

社交网、通信网和Web网等应用中图数据规模不断扩大,一些大规模图已由上亿个顶点和千亿条边构成[4],很难从中直接获取需要的信息.这些应用所构成的图已经大到无法直接观察去提炼其潜在的有用信息,只能将其中属性或结构相似的顶点聚集在一起,从而在更高的层次去研究这些图,准确地把握其中有效的信息[5].

· 存储空间的局限性

在存储图数据时不仅要存储顶点,而且要存储顶点间的关系,因此图数据的存储更占用空间.有效地压缩图数据的存储空间,对于提高图数据挖掘与分析算法的可扩展性、改进大图处理效率具有较大的实际意义.

· 社交网的隐私保护

社交网络作为一项虚拟的信息服务,占据的却是所有用户的真实信息.因此,社交网的隐私保护已成为当前新的研究热点.由于社交网络中的顶点对应着具体的人,所以可以将顶点集合抽象为一个超点,在一定程度上隐藏底层图的顶点和结构信息,起到有效抵制黑客攻击的作用[6].

图聚集技术由于能够有效地处理上述问题,因而成为学术界和工业界关注的新的研究内容.图聚集将原图中的顶点和边集合抽象到一个更高的层次,从而获得一个简洁的超图.该超图能够涵盖原图中几乎所有的信息,其顶点称为超级顶点(简称超点),它代表原图中的一组顶点;其边称为超级边(简称超边),它代表其关联的两个超点之间的边.

一些文献存在与图聚集含义相同或相似的专业术语,如图压缩(graph compression)[7, 8, 9, 10]、图概要(graph synopsis)[1]、图概括(graph summarization)[11-13]、图约化(graph simplification)[14]、网络抽象(network abstract)[15]等.以上术语当其输出为一个超图时,本文统一称为图聚集.但是有些术语与图聚集间存在较大的差异,如图聚类(graph clustering)[16]、图划分(graph partitioning)[17]等.

图划分与图聚集均划分图中顶点:

· 图聚集需保持同一组中顶点属性或者结构相似,且使用存储消耗、重建误差等度量函数评估结果图的性能;而图划分则保持每组中顶点数目近似一致,且交叉边总数最小;

· 通过交叉边数量及容量、负载均衡和数据冗余等衡量划分的好坏;

· 两者也应用于不同的领域,其中,图聚集一般用于图数据的分析与挖掘,而图划分则应用于大图的分布式存储.

图聚类与图聚集的相似点在于它们均将顶点进行分组.区别为图聚类侧重寻找局部稠密的结构;而图聚集从全局出发,侧重寻找属性或者结构相似的顶点,它不仅概括稠密的结构,还概括稀疏的结构.图聚类和图聚集之间详细的比较见表 1.

Table 1 Comparision between graph aggregation and graph clustering 表 1 图聚集与图聚类之间的比较

图 1所示,原图G(V,E)中,V={1,2,3,4,5,6,7,8},E={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4),(4,5),(5,6),(5,7),(5,8)},经过如图 1(a)所示的分组后,得到超图GS(VS,ES)(如图 1(b)所示).该超图含有3个超点VS={(1,2,3,4),5,(6,7,8)}以及3条超边,其中,超点(1,2,3,4)上的超边权值为6,表示超点内部顶点间所有边的数目为6;超点(5)和超点(6,7,8)之间的超 边权值为3,代表两超点间相连的边数为3.

图 1也可分析图聚集和图聚类之间的差别.图聚集不仅概括了如(1,2,3,4)间的局部稠密结构,而且从全局出发,由顶点(6,7,8)的邻接点均为顶点5,概括了(6,7,8)之间稀疏的结构;但图聚类只能概括(1,2,3,4)间稠密的结构.

Fig. 1 Example of supergraph图 1 超图示例

本文将图聚集技术划分为基于属性的图聚集、基于结构的图聚集、基于属性/结构的图聚集这3种,图聚集技术的分类标准取决于分组的特征,在第1节将详细描述不同分组标准的限制以及它们之间的关系,并根据分组标准将图聚集技术进行分类.

1 图聚集分类

图聚集过程中最重要的环节就是分组,为了将输入图抽象到更高的层次,需要将图划分成若干组,进行聚集,形成超点和超边.在当前图聚集算法中,文献[10]设置了基于邻接分组一致性的分组标准,使得同一分组内部各顶点具有相同的邻接分组,但并未区分各顶点的关联强弱;文献[18, 19, 20]基于邻接顶点一致性,使得同一分组内部各顶点具有相同的邻接顶点,然而分组内部顶点间的关联却并不一致;文献[11]提出零重建误差分组标准,使得分组内部各顶点间存在相同的关联,且分组间的边涵盖两分组间可存在的所有的边.这些标准仅适用于不含属性的图,但实际上大多数的图均具有属性.因 此,文献[21, 22, 23, 24, 25, 26]将分组标准设置为基于属性一致性的划分,使得各超点内部的属性值一致,但该分组标准忽略了图中的结构信息;文献[27, 28, 29]使得各分组均满足属性以及邻接分组一致性,该分组标准同时包含了图中的属性和结构信息,但基于邻接分组一致性得到的分组,其内部各顶点的关联强弱无法区分;文献[13]提出了基于属性以及关联强度一致的分组标准,其中,关联强度一致实现了同一分组内部各顶点关联的邻接顶点数目相同.由于图中包含的顶点非常庞大,且其中的属性以及结构较为复杂,因此上述精确分组标准并不完全适用于实际应用,但这些算法均以精确的分组标准为基准,在可控制的误差范围内获取有损图聚集.以上所述的图均指的是同构图,即,图中各顶点以及边的类型均一致,但实质上,就图的类型而言,不仅包含同构图,也包含异构图.异构图中各顶点以及边的类型均不相同,相对于同构图而言包含的信息更多,本文则着重针对同构图进行分析.

对此,本文提出5类分组标准:基于属性信息一致性的划分、基于邻接分组一致性的划分、基于关联强度一致性的划分、基于邻接顶点一致性的划分、基于零重建误差的划分.这5类分组标准的形式化定义如下所示,具体举例如图 2所示.其中,设原图为G(V,E),表示分组Vi中顶点u的邻接顶点所在分组,表示分组Vi中顶点u关联的邻接分组Vj中顶点的数目,表示分组Vj中的顶点总数,表示顶点u在分组Vi中的邻接顶点.

Fig. 2 Example of grouping criteria 图 2 分组标准示例

· 标准I. 基于属性信息一致性的划分:若两顶点在同一分组,则两顶点的任一对应属性值(用ai表示)均相同.即:

"u,vÎV,VjÍV,若uÎVjvÎVj,则"i,ai(u)=ai(v);

· 标准II. 基于邻接分组一致性的划分:若分组中某一顶点与另一分组中某些顶点存在邻接关系,则分组中任一顶点均与另一分组存在邻接关系.即:"u,vÎVi,Vi,VjÍV,若,则:

· 标准III. 基于关联强度一致性的划分:若分组中某一顶点与另一分组中某些顶点存在邻接关系,则分组中任一顶点与另一顶点中相同数目的顶点存在邻接关系.即:

"u,vÎVi,Vi,VjÍV,若则:

· 标准IV. 基于邻接顶点一致性的划分:分组中某一顶点与另一分组中某些顶点存在邻接关系,则分组中的任一顶点均与另一分组中所有顶点存在邻接关系.即:

"u,vÎVi,Vi,VjÍV,若则:

· 标准V. 基于零重建误差的划分:若分组中某一顶点与另一分组中某些顶点存在邻接关系,则分组中的任一顶点均与另一分组中所有顶点存在邻接关系,且组内任意两顶点均相连,或者均不相连.即:

"u,vÎVi,Vi,VjÍV,若,则:

图 2所示,A1,A2,A3是基于属性一致性划分得到的3个不同分组,此时,A1,A2,A3满足标准I,即属性信息一致性;对于超点A1,B而言,A1中每个顶点均能在B中找到其邻接顶点,且A1中顶点与B中对应的顶点关联的边数不一致,因此,A1相对于B仅满足标准II,即邻接分组一致性;A2中每个顶点均能在B中找到其邻接顶点,且关联边数一致,因此,A2相对于B满足标准III,即关联强度一致性;对于A3C而言,A3内的每个顶点均与C中所有顶点关联,因此,A3满足标准IV,即邻接顶点一致性;但A3内部两个顶点存在关联,导致超图不能完全重建成原图,而A2C不仅满足标准IV,且A2,C内部各顶点间关联一致,因此,A2相对于C满足标准V.

以上分组标准可概括为:基于属性一致性分组标准,基于结构一致性分组标准.其中,标准I属于基于属性一致性分组标准;标准II,III,IV,V属于基于结构一致性分组标准,且相互之间存在包含的关系,即,IIÊIIIÊIVÊV(如图 3所示),其中,U表示所有可能的分组集合.根据图 3中各分组标准对应的集合关系对图聚集进行以下分类:当图聚集仅满足标准I时,称为基于属 性的图聚集;当仅满足II,III,IV,V时,称为基于结构的图聚集;当满足I-II,I-III,I-IV,I-V的交集时,称为同时基于属性和结构的图聚集.

Fig. 3 Relationships between grouping criteria图 3 分组标准之间的联系

由上文可知,图聚集可分为基于属性的图聚集、基于结构的图聚集和基于属性/结构的图聚集.其中,基于属性和基于结构的图聚集均能实现属性或结构在同一分组一致、不同分组相异的特性.但由于基于属性的图聚集分组内部结构松散,而基于结构的图聚集分组内部属性值不一致,因此,当前更热衷于研究基于属性/结构一致性的图聚集.

图聚集也可根据重建误差划分为有损图聚集和无损图聚集.无损图聚集能够由超图重建成完整的输入图,能够精确地回答基于输入图的查询.但有损图聚集更有实际意义,这是由于一致性标准对于实际应用中的图数据并不完全适用.一些应用中的图数据无法避免噪音和不确定性,当对这些含有噪音和不确定性的图数据进行一致性分组时,得到的分组数目十分庞大,从而造成低效的图数据分析和挖掘.此外,在某些应用场景下,图查询不需要精确的回答,如:在并不精确的邻居顶点集合下,社交网仍能识别出相关的社区;Web网在并不清楚地知道每个网页所有链接网页的条件下,也能够获得很好的PageRank值等.图 1(b)所示的超图丢失了(4,5)这条边的信息,因此 只有1/4的概率准确地重建成原图,图 1所示的图聚集是有损图聚集.

2 主要图聚集技术 2.1 基于属性的图聚集

基于属性一致性的图聚集均满足分组标准I,一般与OLAP技术相结合,代表技术为Graph OLAP/Cube.

OLAP被广泛地应用于数据仓库,提供决策分析的功能.它基于多维数据模型,将数据看作数据立方体形式,通过计算每个维度组合的度量,提高在线分析性能.而在实际的多维网络中,暗含着的图结构数据却存在着管理、查询、聚集等问题.

文献[21, 22, 23, 24]涉及的Graph OLAP技术利用网络快照构建图模型,基于图的属性将网络快照进行聚集,得到高层次的超图,并实现OLAP的基本操作,如:上卷、下钻、切片/切块等.文献[21]将属性分为两种,分别是Info- Dims和Topo-Dims,其中,Info-Dims基于不同的维度和粒度决定网络快照所在的分组;Topo-Dims则操作单个网络内的顶点和边,将具有关联的顶点集合聚合成一个整体.基于Info-Dims和Topo-Dims构建的OLAP分别为I-OLAP和T-OLAP.

对于I-OLAP,利用Info-Dims覆盖多个网络快照,构建I-aggregated graph.由于多个快照描述的是相同顶点间的不同关联,因此,I-aggregated graph针对相同的顶点,将快照集合的顶点和边的属性进行聚集,不改变原图的拓扑结构.

对于T-OLAP,利用Topo-Dims压缩单个网络的拓扑结构,得到T-aggregated graph.任一顶点对应原图中Topo-Dims值相同的顶点分组,顶点属性覆盖对应分组中顶点属性集合,压缩原图的拓扑结构,隐藏图中的细节信息.

而Graph Cube[25]类似于关系数据库构建Cube,但不同于以往的度量值,图的度量是一个聚集网络,它代表的是对应顶点分组后,原图的聚集结果.而对于已构建的Graph Cubes,OLAP被分为Cuboid Query和Crossboid Query.Cuboid Query对应着传统的OLAP,即,对于一个或者多个维度进行上卷、下钻、切片、切块等,它们均仅涉及一个Cuboid.而Crossboid Query则是在多个Cuboids上进行交叉查询.

对于上述的图聚集技术,仅针对顶点的属性进行分组,无法回答基于原图结构的查询,如顶点a,b间相同的邻居顶点等;其次,相比于传统的OLAP,网络更加庞大和复杂,所以在多维空间中必须要压缩多重聚集网络.

2.2 基于结构的图聚集 2.2.1 基于概率的图聚集

文献[11]的切入点是在超图上精确地回答基于原图的查询,针对这种查询,方法之一就是将超图重建成原图进行查询,此时,超图的重建误差越小,查询结果越精确.虽然该方法利用随机划分进行分组,但它以零重建误差为基准,因此最终结果的分组均满足分组标准V.

基于Random-Worlds的Indifference原则,超图重建原图时,得到的各结果图的概率一致(包含原图的概率).将超图转换为矩阵,根据概率公式计算其期望邻接矩阵,概率公式如公式(1)~公式(3)所示.其中,Ei表示超点Vi内部的边数目,Eij表示超点Vi和超点Vj之间的边数目,|Vi|表示超点Vi内部顶点数目.如图 4所示.

Fig. 4 Example of graph aggregation based on probability 图 4 基于概率的图聚集举例

1) 当u,v属于同一超点Vi中的不同顶点时:

(1)

2) 当u,v属于不同超点Vi,Vj中的不同顶点时:

(2)

3) 当u,v属于相同顶点时:

(3)

通过超图得到的期望邻接矩阵和原图的邻接矩阵间的差异构建重建误差,重建误差越小,得到的超图精确性越好,重建误差公式如公式(4)所示.

(4)

基于期望邻接矩阵的图聚集方法得到的超图能够精确地回答基于原图的查询,但仅限于不含属性信息的图.通过计算模型的描述消耗TB(),能够有效地控制结果集的数目.但由于需要保证超图的信息完整性,它不能最小化结果集的数目.

2.2.2 基于最大化压缩的图聚集

S-Node[10]提出了Web图的两层表示方式,顶层图由超点和超边组成,它们分别指向底层对应的有向图结构.其顶层图即是超图,利用分组标准II,实现邻接分组一致.在Web图中体现为将域相同的顶点聚集形成初始分组,通过相同的URL前缀循环提炼原始分组.最后,基于K-Means等聚类方法进一步压缩,直至不能分裂.S-Node的表示包含4个部分,分别是超点图(supernode graph)、超点内部关系图(intranode graph)、超点间存在的超边图(positive superedge graph)、超点间不存在的超边图(negative superedge graph).根据存在的超边和不存在的超边数目比较,选择数目较少的作为S-Node中的超边图.但该方法存在这样的问题:超图中的超边未考虑两超点间的关联强度,仅存在一条边的两超点间也会构建超边,这给理解图中原有信息带来了困难,

文献[18]对S-Node进行改进,通过MDL原则构建超边,使其在强关联的情况下才构建超边,弱关联的边保存在corrections集合中,保证了信息的完整性.其中,各超边均包含两邻接分组间的所有边集合,实现分组标准IV,即邻接顶点一致,并且通过创建自连接边有效地将紧密的团结构合并成一个超点.S-Node通过URL的信息仅获取Web图的无损压缩,但基于MDL的图聚集方法不仅可以进行无损压缩,也允许有损压缩.在实际应用中,由于图的数据量较大,此时,有损压缩的意义更大.

基于MDL的图聚集方法,利用信息论中的MDL原则获取度量函数消耗减少率,如公式(5)、公式(6)所示.循环获取s值最大的顶点对合并,直至s的值小于等于0为止.

s(u,v)=(cu+cv-cw)/(cu+cv) (5)

cu,x=min{|Pu,x|-|Au,x|+1,|Au,x|} (6)

其中,s(u,v)表示合并前后消耗减少率,cu,cv,cw分别表示顶点u,v,w的消耗值,Au,x表示u,x之间实际存在的边集合,Pu,x表示u,x之间所有的边集合.如图 5所示.

Fig. 5 Example of graph aggregation based on MDL图 5 基于MDL的聚集方法举例

基于MDL的图聚集方法对应的corrections占据的空间消耗较大,几乎占所有消耗的80%,可针对这个进行再次压缩;其次,它的计算量比较大,每次循环合并两顶点,均需重新计算与两顶点或者其邻居顶点相关的顶点对的s值;本质上,它仅考虑了图的结构信息,忽略了顶点属性、边的类型以及权重等其他信息.

2.3 基于属性和结构的图聚集 2.3.1 基于熵模型(entropy)的图聚集

文献[13]利用信息论中的熵模型衡量属性/结构的信息量,并通过创建属性顶点和属性边将属性信息转换为邻接信息,如图 6所示.

Fig. 6 Example of graph aggregation based on entropy图 6 基于熵的图聚集方法举例

该方法不仅实现了分组标准I和II,保证了属性和邻接分组的一致性,而且实现了分组标准III,获取了关联强度的一致性.设置参数k控制各分组中顶点数目,但为了均衡属性和结构的信息,在一致性分组的基础上放宽了三者的限制.基于熵模型的度量函数R(P)的公式如公式(7)所示.

(7)

通过权值l和(1-l),自定义属性和结构在图聚集过程中所占的比重.由公式(8)、公式(9)可得到超点Si分别关联权值为l的属性顶点aj和权值为(1-l)的其他超点得到的熵值:

(8)

(9)

基于熵模型的图聚集实现了属性/结构的相似一致性,对于含有属性的图而言,该方法能够有效地度量属性和结构的信息量.但其并未计算出属性和结构的相应权重,需要用户自己定义,且不能自动调节所有边的权重.

文献[30]通过分组标准I和III,确保各分组的属性以及关联强度一致,并基于直观上较好的超图所满足的特性,推导出包含多样性、简洁性、覆盖性和实用性在内的超图质量函数Quality(Gf),相应的公式如下所示:

(10)

基于Jaccard相似度,利用LSH(locality sensitive hashing)划分技术,使同一组内顶点的属性集尽量相似,并降低时间复杂度至O(|V|log|V|+E).实现了多样性和简洁性,基于熵度量关联一致性,使用K-Means算法进一步分组,尽量实现关联一致性满足覆盖性和实用性.但整体上看,质量函数和计算过程并不紧密关联,并未体现出4种特性在同一情况下的整体度量.

2.3.2 基于多粒度的图聚集

文献[27]提出的SNAP算法由用户选定属性和关联类型,其超图中各分组虽然满足分组标准I和II,实现属性和邻接分组一致.但由于实际数据的噪音和不确定关联,导致其效果并不好.由此提出改进算法k-SNAP,该方法放宽了邻接分组的一致性,并给定分组数目k控制超图的大小.通过Top-Down方法,由属性一致性分组分裂到属性和邻接分组相似一致的k个分组,实现了OLAP中的下钻过程.也可通过Bottom-Up方法由属性和邻接分组一致的分组合并到属性和邻接分组相似一致的k个分组,实现了OLAP中的上卷过程.但k-SNAP中仍然存在如下一些问题[29,31]:

1) k-SNAP仅适用于属性域较小的情况,这是因为k-SNAP中要求各分组的属性值需保持一致,当选定的属性的值域较大时,如链接的引用次数,利用度量CT基于邻接分组一致性分裂成k个分组时,分组的数据在属性上存在严重的倾斜;

2) k-SNAP能够实现多粒度的图聚集,但是用户往往需要计算出很多超图,才能得到自己感兴趣的结果.

文献[29]针对上述问题进行了一些改进:针对问题1),它通过算法CANAL自动划分域较大的属性的值,将分组的属性值一致转换为属性值域一致.该算法将属性值相邻的任意两分组,基于两分组的邻接分组一致性度量SimLink进行合并后,通过合并前后D的转变率的度量up,获取合并后使得超图的性能最差的两邻接分组间的属性值边界线,进而将原属性域划分成C(期望分组数)个区间;针对问题2),通过给出的度量Interestingness(S),粗略地衡量了用户感兴趣的因素,包括超图信息的多样性(diversity)、覆盖性(coverage)以及简洁性(conciseness),使得超图在具有实际意义的同时含有较多的信息.

表 2总结了上文多种图聚集方法的特点:

Table 2 Collection of graph aggregation and summarization 表 2 图聚集技术汇总

· 基于属性的图聚集技术研究的多层次多维度的方法,包含Graph OLAP和Graph Cube,仅满足分组标准I;

· 基于结构的图聚集技术主要针对超图还原的概率和最大化压缩原图两方面进行研究;

· 基于属性/结构的图聚集则利用熵模型和OLAP方式,在属性一致性上均满足分组标准I,但对于结构一致的标准最多能满足标准III;

· 部分算法能够满足分组标准V,实现无损图聚集.

3 结 论

本文研究和分析了当前图聚集的技术及算法,给出了5种分组标准,并根据各分组标准对应的关系将图聚集划分成基于属性一致性、基于结构一致性和同时基于属性和结构一致性的图聚集这3类.接着,概括性地描述了当前主要的图聚集算法.

随着图数据的不断快速增长以及图数据应用的多样化,在图聚集和可视化领域将面临越来越多的挑战:

· 可扩展的图聚集

图聚集技术虽然是用于解决大图中可扩展的图挖掘问题,但是如今针对高度可扩展的图聚集算法仍然存在很多问题.大多数工作还停留在基于内存的图聚集算法上,因此有必要研究基于磁盘的图聚集算法,或者参考并行处理模型,如MapReduce等.

· 不确定图的图聚集技术

实际应用中,有些图数据存在关联不确定的问题,在处理此类图聚集问题时,可考虑引入概率这一概念.对图中顶点间不确定的关系使用概率计算其期望值,得到最接近实际情况的关联值.

· 属性和结构相融合的图聚集

大多数基于属性和结构一致性的图聚集技术均通过信息论中熵的模型来实现,但是熵并不能完全解决属性和结构相矛盾的问题.属性和结构相融合的图聚集之所以困难,就在于无法确定两者之间的权重,很难将它们放在同一个平台上去考虑.所以,同时基于属性和结构一致性的图聚集仍然需要细致而深入地加以研究.

· 多图及异构图的聚集和概括

现有图聚集技术的研究对象均是单个图,实际上,针对多个图进行研究也是一个新的研究点.当前,已出现了诸如获取包含相同查询子图的多个图聚集[32]以及使用单个图概括多个图的结构信息[33]等.异构图由于顶点以及边的类型都可能不相同,对其进行聚集和概括将是一个挑战.

致谢 衷心感谢审稿专家对本文提出的宝贵意见和建议.

参考文献
[1] Aggarwal CC, Wang H. Managing and Mining Graph Data. Springer-Verlag, 2010 .
[2] Chakrabarti D, Faloutsos C. Graph mining: Laws, generators, and algorithms. ACM Computing Surveys, 2006,38(1):2 .
[3] Leskovec J, Kleinberg J, Faloutsos C. Graphs over time: Densification laws, shrinking diameters and possible explanations. In: Proc. of the 11th ACM SIGKDD (KDD 2005). New York: ACM Press, 2005. 177-187 .
[4] Feng GD, Xiao YH. Distributed storage of big graphs. Communications of the CCF, 2012,8(11):12-15 (in Chinese with English abstract).
[5] Rodrigues JF, Traina AJM, Faloutsos C, Traina Jr C. SuperGraph visualization. In: Proc. of the 8th IEEE Int’l Symp. on Multimedia. 2006. 227-234 .
[6] Hay M, Miklau G, Jensen D, Weis P. Resisting structural re-identification in anonymized social networks. In: Proc. of the VLDB. 2008 .
[7] Adler M, Mitzenmacher M. Towards compressing Web graphs. In: Proc. of the Data Compression Conf. 2001. 203-212 .
[8] Boldi P, Vigna S. The Web graph framework I: Compression techniques. In: Proc. of the WWW. 2004. 595-602 .
[9] Suel T, Yuan J. Compressing the graph structure of the Web. In: Proc. .of the Data Compression Conf. 2001 213-222 .
[10] Raghavan S, Garcia-Molina H. Representing Web graphs. In: Proc. of the ICDE. 2003. 405-416 .
[11] LeFevre K, Terzi E. GraSS: Graph structure summarization. In: Proc. of the SDM 2010. 2010. 454-465 .
[12] Liu Z, Yu JX. On summarizing graph homogeneously. In: Proc. of the Database Systems for Adanced Applications. 2011. 299-310 .
[13] Liu Z, Yu JX, Cheng H. Approximate homogeneous graph summarization. Information Processing Society of Japan, 2011,20(1): 77-88 .
[14] Toivonen H, Zhou F, Hartikainen A, Hinkka A. Compression of weighted graphs. In: Proc. of the 17th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. ACM Press, 2011 .
[15] Zhou F. Methods for Network Abstraction. University of Helsinki, 2012.
[16] Zhou Y, Cheng H, Yu JX. Graph clustering based on structural/attribute similarities. Proc. of the VLDB Endowment, 2009,2(1) .
[17] Abou-Rjeili A, Karypis G. Multilevel algorithms for partitioning power-law graphs. In: Proc. of the IPDPS 2006. 2006 .
[18] Navlakha S, Rastogi R, Shrivastava N. Graph summarization with bounded error. In: Proc. of the 2008 ACM-SIGMOD Int’l Conf. on Management of Data (SIGMOD 2008). Vancouver, 2008. 419-432 .
[19] Toivonen H, Zhou F, Hartikainen A, Hinkka A. Network compression by node and edge mergers. In: Proc. of the Bisociative Knowledge Discovery. Berlin, Heidelberg: Springer-Verlag, 2012. 199-217 .
[20] Álvarez S, Brisaboa NR, Ladra S, Pedreira Ó. A compact representation of graph databases. In: Proc. of the 8th Workshop on Mining and Learning with Graphs. ACM Press, 2012. 18-25 .
[21] Chen C, Yan X, Zhu F, Han J, Yu PS. Graph OLAP: Towards online analytical processing on graphs. In: Proc. of the ICDM. 2008. 103-112 .
[22] Li C, Yu PS, Lin W. InfoNetOLAPer: Integrating InfoNetWarehouse and InfoNetCube with InfoNetOLAP. PVLDB, 2011,4(12): 1422-1425 .
[23] Qu Q, Zhu F, Yan X, Han J, Yu PS, Li H. Efficient topological OLAP on information networks. In: Proc. of the DASFAA 2011. Hong Kong, 2011. 389-403 .
[24] Li C, Zhao L, Tang CJ, Chen Y, Li J, Zhao XM, Liu XL. Modeling, design and implementation of graph OLAPing. Ruan Jian Xue Bao/Journal of Software, 2011,22(2):258-268 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3771.htm
[25] Zhao P, Li X, Xin D, Han J. Graph cube: On warehousing and OLAP multidimensional networks. In: Proc. of the SIGMOD 2011. 2011. 12-16 .
[26] Hassanlou N. Probabilistic graph summarization. University of Victoria, 2012 .
[27] Tian Y, Hankins RA, Patel JM. Efficient aggregation for graph summarization. In: Proc. of the 2008 ACM-SIGMOD Int’l Conf. on Management of Data (SIGMOD 2008). Vancouver, 2008. 567-580 .
[28] Tian Y, Patel JM. Interactive Graph summarization. In: Proc. of the Link Mining: Models, Algorithms, and Applications. 2010. 389-409 .
[29] Zhang N, Tian Y, Patel JM. Discovery-Driven graph summarization. In: Proc. of the 2010 IEEE 26th Int’l Conf. on Data Engineering (ICDE). IEEE, 2010 .
[30] Yin D, Gao H, Zou Z. A novel efficient graph aggregation algorithm. Journal of Computer Research and Development, 2011,48(10): 1831-1841 (in Chinese with English abstract).
[31] Louati A, Aufaure MA, Lechevallier Y. Graph aggregation: Application to social networks. In: Advances in Theory and Applications of High Dimensional and Symbolic Data Analysis. Hermann, 2013. 157-177.
[32] Zou L, Chen L, Zhang HM, Lu YS, Lou Q. Summarization graph indexing: Beyond frequent structure-based approach. In: Proc. of the Database Systems for Advanced Applications. Berlin, Heidelberg: Springer-Verlag, 2008.141-155 .
[33] Endriss U, Grandi U. Graph aggregation. In: Proc. of the 4th Int’l Workshop on Computational Social Choice (COMSOC 2012). 2012.
[4] 冯国栋,肖仰华.大图的分布式存储.中国计算机学会通讯,2012,8(11):12-15.
[24] 李川,赵磊,唐常杰,陈瑜,李靓,赵小明,刘小玲.Graph OLAPing的建模、设计与实现.软件学报,2011,22(2):258-268. http://www.jos.org.cn/1000-9825/3771.htm
[30] 尹丹,高宏,邹兆年.一种新的高效图聚集算法.计算机研究与发展,2011,48(10):1831-1841.