基于Twitter Storm平台并行挖掘最稠密子图

• 作者: 王远方 王金明
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 最稠密子图发现 查询标签集 DSFLC算法 Twitter Storm平台
• 年，卷（期）: 2014,（1）
• 所属期刊栏目: 人工智能
• 页码范围: 274-278
• 页数: 5页
• 分类号: TP392
• 字数: 5207字
• 语种: 中文

摘要

在大规模图结构数据中发现最稠密子图具有极其广泛的应用,如社区发现、垃圾邮件检测和论文引用关系抽取等.基于带标签的无向图,提出了查询标签集的概念,设计了一个可以快速发现最稠密子图的近似算法DSFLC(Densest Subgraph Finding based on Labelset Constraint):用户提交自定义的查询标签集,算法便可保证在用户可以接受的时间内返回满足查询标签集约束的最稠密子图.对于任何参数ε(ε＞0),DSFLC算法只需扫描大规模数据集O(log1+εn)次,同时可保证算法的近似因子是2(1+ε).对DSFLC算法进行分析后,发现该算法在预处理阶段易于并行化,因此选择Twitter Storm平台,并行化地实现了DSFLC算法.最后对从DBLP数据库中抽取的合作关系图进行测试,一方面研究Storm平台对算法的加速程度；另一方面分析挖掘出的子图的稠密度与参数ε之间的关系,最终验证了DSFLC算法的实用性和可扩展性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王金明	东南大学计算机科学与工程学院	5	20	2.0	4.0
2	王远方	东南大学计算机科学与工程学院	2	18	2.0	2.0