基于TwitterStorm平台并行挖掘最稠密子图.pdf

《基于TwitterStorm平台并行挖掘最稠密子图.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷第1期计算机科学Vo1．41No．12014年1月ComputerScienceJan2014基于TwitterStorm平台并行挖掘最稠密子图王金明王远方(东南大学计算机科学与工程学院南京211189)摘要在大规模图结构数据中发现最稠密子图具有极其广泛的应用，如社区发现、垃圾邮件检测和论文引用关系抽取等。基于带标签的无向图，提出了查询标签集的概念，设计了一个可以快速发现最稠密子图的近似算法DSFLC(DensestSubgraphFindingbasedonLabelsetConstr

2、aint)：用户提交自定义的查询标签集，算法便可保证在用户可以接受的时间内返回满足查询标签集约束的最稠密子图。对于任何参数￡(￡>O)，DSFLC算法只需扫描大规模数据集O(1ogt+~n)次，同时可保证算法的近似因子是2(1+￡)。对DSFLC算法进行分析后，发现该算法在预处理阶段易于并行化，因此选择TwitterStorm平台，并行化地实现了DSFLC算法。最后对从DBLP数据库中抽取的合作关系图进行测试，一方面研究Storm平台对算法的加速程度；另一方面分析挖掘出的子图的稠密度与参数￡之间

3、的关系，最终验证了DSFI，C算法的实用性和可扩展性。关键词最稠密子图发现，查询标签集，DSFLC算法，TwitterStorm平台中图法分类号TP392文献标识码AParallelMiningofDensestSubgraphBasedoilTwitterStormWANGJin-mingWANGYuan-fang(SchoolofComputerScienceandEngineering，SoutheastUniversity，Nanjing211189，China)AbstractInla

4、rgescalegraph，findingdensestsubgraphhasawiderangeofapplications，suchascommunitydiscovery，sparedetectionandreferencerelationextraction．Basedontaggedundirectedgraph，weintroducedtheconceptofQLSanddesignedanapproximationalgorithmDSFLCwhichcanquicklyfindt

5、hedensestsubgraph：userssubmitaQLSandthealgorithmwillreturnthedensestsubgraphunderQLSwithinthetimethatusercanaccept．Foranye>O，DSFLConlyDeedstoscanlarge-scaledatasets0(1og1+e，z)times，andcanensuretheapproximationalgorithmisa2(1+e)-ap—proximationalgorith

6、m．AfteranalyzingDSFLC，wefoundthisalgorithmiseasytoparallelize，SOwechoseTwitterStormplatformtoparalleIDSH￡algorithm．Finally。thetestdatasetsextractedfromtheDBLPdatabaseverifyDS-FLCpracticalityandscalability．KeywordsDensestsubgraphfinding，QLS，DSFLCalgor

7、ithm，Twitterstormplatform1引言在大规模图结构数据中发现最稠密子图具有众多应用，涉及的领域包括：在社交网络中发现通过相似关系最紧密联系起来的社区l】0；在万维网中，发现通过超链接紧密相关的一系列网页l_3]，这些网页从逻辑上可视为内聚性较高的Web社区等。—本文所提出的算法基于带标签的无向图，所谓的标签，是指图中顶点是通过何种关系联系起来的。如图1所示，顶点1和顶点2是通过合作关系联系起来的。由于顶点间的关系往往不止一种，因此连接顶点间的边就具有一个标签集，该标签集记录的

8、是顶点间通过何种关系进行联系，如图1所示，顶二点2和顶点8之间既有朋友关系，也有同事关系，因此连接顶(朋友，同事}点2和顶点8的边具有的标签集就是{朋友，同事}。本文引入了查询标签集QLS(QueryLabelSet)的概念，用户提交自图1无向带标签图G，QLS={朋友，同事)己感兴趣的标签集合，这些标签集合就构成了查询标签集。先前的发现最稠密子图的算法，一方面没有考虑标到稿日期：2013～03—10返修日期：2013—04—28王金明(1988一)，男，硕士生，主要研究领域为图结构数据管理；王