大型网络随机化的社区挖掘算法

《大型网络随机化的社区挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机研究与发展ISSN1000—12391CN1卜1777／TPJournalofComputerResearchandDevelopment46(Suppl．)：406—412，2009一种面向大型网络的快速随机化社区挖掘算法余韬肖仰华何震瀛汪卫吴文涛(复旦大学计算机科学技术学院上海200433)(yyuuttaaoo@gmail．com)FastRandomizedAlgorithmforCommunityDetectioninLargeNetworksYuTao，XiaoYanghua，HeZhe

2、nying，WangWei，andWuWentao(SchoolofComputerScience，FudanUniversity，Shanghai200433)AbstractDetectingcommunitystructureisfundamentalforuncoveringtheorganizationprincipleofrealnetworks．Existingcommunitydetectionalgorithmsarenottractableforlargegraphs，inpartic

3、ularthegraphswithmillionsofnodes．However，proliferationoflarge-scalerealnetworkdatademandsnewmethodstoidentifycommunitiesefficientlyandeffectively．Forthispurpose，arandomizedalgorithmisproposedtoefficientlyminecommunitystructurewithhighqualityfromlargenetwo

4、rks．EachrandomizedstepofthenewalgorithmistorenumbertheverticesbyaDFSorder．SuchDFSrenumberingishelpfultoidentifytheedgesbetweencommunities．Finally，theeffectivenessandefficiencyofthenewalgorithmareshownbyexperimentalresultsonbothsyntheticandrealnetworks．Key

5、wordsrandomizedalgorithm；communitydetection；largenetworks摘要寻找网络的社区结构对于理解真实网络的自组织机制、可视化大网络有重要的作用．然而，现有的社区挖掘算法由于性能较低，还难以处理大型网络，特别是有着百万顶点的网络．然而，百万规模的大网络却在越来越多的真实应用中大量涌现，这对于高效的有效社区识别算法提出新的需求．为此，一种新颖的随机算法被提出，能够在接近线性时间内，从大型网络上高效地挖掘质量较高的网络社区：新算法的核心思路是在每一随机步骤中对网络

6、中的顶点进行基于深度优先顺序的编码，这样的编码有助于有效地识别社区之间的边．最后，通过针对模拟网络和真实网络的一系列实验验证了新算法的高效，}生和有效性．关键词随机算法；社区挖掘；大惆络中图法分类号TP391近年来，大量的真实网络数据大量涌现，常见的包括Www、互联网、生物网络和社会网络．在各种网络分析中，社区挖掘是最为常见的网络分析任务之一，且已被成功地应用于各种不同主题的网络¨4]的分析中．通常，网络上的一个社区划分是指将网络上的全部顶点划分成若干分组，使得组内顶点之间的链接密度显著高于组间．寻找以及

7、评估网络上的社区结构不仅有助于人们理解网络系统的功能和行收稿日期：2009一06—19基金项目：国家自然科学基金项目(60673133，60703093)，国家“九七三”重点基础研究发展计划基金项目(2005CB321905)；上海市重点学科建设基金项目(B114)余韬等：一种面向大型网络的快速随机化社区挖掘算法407为，也有助于改善大型网络结构的可视化．然而，在可接受的时间内从网络中挖掘较高质量的社区结构绝非易事．在某个给定的社团结构质量指标的度量下，挖掘该指标度量下最优网络社区结构似乎是一个NP难的问

8、题，因为可能的社区划分的数量与网络规模呈指数关系．而近年来，迅速膨胀的网络规模使得面向这些网络的社区挖掘更加复杂．某些在线社会网络，比如MySpace，Facebook上的交友网络，其规模已经达到数百万的点和数亿的边∞]．现有的非线性社区发现算法显然已经难以胜任这一规模网络上的社区分析．因此，我们迫切需要新的高效的方法来挖掘网络的社区结构．虽然已经有大量的研究工作致力于各类大型网络的社区挖掘，但是设计一个能够保证挖掘质量的高效