计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2014年
1期
274-278
,共5页
最稠密子图发现%查询标签集%DSFLC算法%Twitter Storm平台
最稠密子圖髮現%查詢標籤集%DSFLC算法%Twitter Storm平檯
최주밀자도발현%사순표첨집%DSFLC산법%Twitter Storm평태
Densest subgraph finding%QLS%DSFLC algorithm%Twitter storm platform
在大规模图结构数据中发现最稠密子图具有极其广泛的应用,如社区发现、垃圾邮件检测和论文引用关系抽取等.基于带标签的无向图,提出了查询标签集的概念,设计了一个可以快速发现最稠密子图的近似算法DSFLC(Densest Subgraph Finding based on Labelset Constraint):用户提交自定义的查询标签集,算法便可保证在用户可以接受的时间内返回满足查询标签集约束的最稠密子图.对于任何参数ε(ε＞0),DSFLC算法只需扫描大规模数据集O(log1+εn)次,同时可保证算法的近似因子是2(1+ε).对DSFLC算法进行分析后,发现该算法在预处理阶段易于并行化,因此选择Twitter Storm平台,并行化地实现了DSFLC算法.最后对从DBLP数据库中抽取的合作关系图进行测试,一方面研究Storm平台对算法的加速程度；另一方面分析挖掘出的子图的稠密度与参数ε之间的关系,最终验证了DSFLC算法的实用性和可扩展性.
在大規模圖結構數據中髮現最稠密子圖具有極其廣汎的應用,如社區髮現、垃圾郵件檢測和論文引用關繫抽取等.基于帶標籤的無嚮圖,提齣瞭查詢標籤集的概唸,設計瞭一箇可以快速髮現最稠密子圖的近似算法DSFLC(Densest Subgraph Finding based on Labelset Constraint):用戶提交自定義的查詢標籤集,算法便可保證在用戶可以接受的時間內返迴滿足查詢標籤集約束的最稠密子圖.對于任何參數ε(ε＞0),DSFLC算法隻需掃描大規模數據集O(log1+εn)次,同時可保證算法的近似因子是2(1+ε).對DSFLC算法進行分析後,髮現該算法在預處理階段易于併行化,因此選擇Twitter Storm平檯,併行化地實現瞭DSFLC算法.最後對從DBLP數據庫中抽取的閤作關繫圖進行測試,一方麵研究Storm平檯對算法的加速程度；另一方麵分析挖掘齣的子圖的稠密度與參數ε之間的關繫,最終驗證瞭DSFLC算法的實用性和可擴展性.
재대규모도결구수거중발현최주밀자도구유겁기엄범적응용,여사구발현、랄급유건검측화논문인용관계추취등.기우대표첨적무향도,제출료사순표첨집적개념,설계료일개가이쾌속발현최주밀자도적근사산법DSFLC(Densest Subgraph Finding based on Labelset Constraint):용호제교자정의적사순표첨집,산법편가보증재용호가이접수적시간내반회만족사순표첨집약속적최주밀자도.대우임하삼수ε(ε＞0),DSFLC산법지수소묘대규모수거집O(log1+εn)차,동시가보증산법적근사인자시2(1+ε).대DSFLC산법진행분석후,발현해산법재예처리계단역우병행화,인차선택Twitter Storm평태,병행화지실현료DSFLC산법.최후대종DBLP수거고중추취적합작관계도진행측시,일방면연구Storm평태대산법적가속정도；령일방면분석알굴출적자도적주밀도여삼수ε지간적관계,최종험증료DSFLC산법적실용성화가확전성.
