超大规模社交图上的子图匹配问题研究

《超大规模社交图上的子图匹配问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据指导小组成员名单肖仰华副教授何震瀛讲师王鹏副教授汪卫教授施伯乐教授计算机科学技术学院复旦大学万方数据摘要图是一种以顶点和边为基础形成的一种结构化数据表现形式，相比传统的数据库表形式，具有非常灵活的表达能力。近些年来，Twitter，Facebook，微博，微信等社交工具的出现，产生了超大规模的社交图数据。如何处理超大规模的图数据成为了非常关键的研究问题。子图匹配问题是图数据处理领域中的一个非常基础和重要的问题。图上的搜索，模式挖掘算法都必须基于快速的子图匹配算法。子图匹配问题是一个NP难问题，前人的研究工作中给出了一些纯算法的解法，这些方法难以处理十几万顶点以

2、上规模的图数据。也有一些工作通过建立索引的方式来处理大规模的图数据，但是这些索引的规模都是图规模的超线性函数，在图规模达到上亿级别的社交图时，索引的存储代价过大，无法实现。分布式图数据库的出现使得存储和操作超大规模的图数据成为现实。本文的工作以微软亚洲研究院(MSRA)研究的分布式图数据库Trinity为底层图数据存储引擎，研究了超大规模图上的子图匹配问题，提出了一个使用线性索引，基于快速图搜索的剪枝技术和大规模并行计算技术的子图匹配算法，论证了算法的正确性，完备性和不重复性。实验表明我们的算法具有很好的响应时间和可扩展性，说明了在大规模图上进行快速子图匹配的可行性。

3、关键词：超大规模图数据，图匹配，分布式图数据库，并行算法。中文法分类号：TP311万方数据AbstractGraphisakindofrepresentationformalismofstructureddatabasedonverticesandedges．Comparedwithtraditionalformofdatabasetables，itisveryflexible，visualizedandexpressive．Inrecentyears，socialmedialikeTwitter,Facebook，Micro．blog，andWeChatproduc

4、esmassivescaleofsocialgraphdata．Howtohandlelargescalegraphdatabecomesacrucialresearchproblem．Subgraphmatchingproblemisaverybasicandimportantproblem．Bothsearchingandpatternminingongraphsarebasedonefficientgraphmatchingalgorithms．SubgraphmatchingproblemisanNP-hardproblem，andpreviousresear

5、chgivessomepurealgorithmicsolutions，however,theycannothandlegraphslargethan100，000vertices．Otherworkstriedtosolvethisproblembybuildingkindsofindicesrequiringsuper-linearindexingtimeorsuper-linearindexingspace．Unfortunately,thosesuper-linearindexingmethodsarenotfeasiblewhengraphdataisasl

6、argeasarealsocialgraph．Distributegraphdatabasesmakestoringandmanipulatinglargescalegraphdataareality．Inthispaper,dependingontheworkofTrinitywhichisadistributedgraphdatabasedesignedbyMicrosoftResearchAisa(MSRA)，westudythesubgraphmatchingproblem，presentanefficientsubgraphmatchingalgorithm

7、usinggraphexplorationandmassiveparallelcomputingtechnology．Wedemonstratethecorrectness，completenessandnon—repeatabilityofouralgorithm．Experimentalresultsshowthatouralgorithmhasquickresponsetimeandgoodscalability,indicatingthefeasibilityofsubgraphmatchingonlarge-scalegraph．Keywo