复杂网络的社团结构分析.pptVIP

1 章祥荪 复杂网络的社团结构分析Communitystructureincomplexnetworks http zhangroup aporc org中国科学院数学与系统科学研究院全国复杂网络会议 苏州大学 2010 10 17 复杂网络的动态性质研究复杂网络的静态结构研究小世界 Smallworld 尺度无关 Scalefree 聚类特性 Clustering 的确切数学模型 社团结构 CommunityStructure 2 3 复杂网络的模块化性质 复杂网络中存在模块或者社区结构 ModuleorCommunitystructure 模块或者社区定义为网络中内部连接稠密 与外部连接稀疏的节点的集合 FilippoRadicchiet al PNAS Vol 101 No 9 2658 2663 2004 数学表述 其中V是子图 K是顶点的度 即子图V是模块的条件是模块内顶点的内部连边的度值之和大于模块内顶点的外部连边的度值之和 PNAS Proc Natl Acad Sci USA美国科学院院刊 4 模块划分的重要性 许多复杂网络共有的性质 研究模块结构有助于研究整个网络的结构和功能 圣塔菲研究所的科学家合作网 模块代表从事相似领域研究的科学家集合 数学生态学 统计物理 5 MartinRosvall CarlT Bergstrom PNAS vol 105 no 4 1118 1123 2007 自然科学论文引用网络 6128期刊 约600万次引用 划分为88个模块和3024条模块间的连接 刻画了学科之间的联系 6 一个社会网络的例子 1970年美国大学里的一个空手道俱乐部关系网络 节点是其34名成员 边是他们两年间的友谊关系 边数为78 俱乐部里的矛盾导致其分裂为两个小的俱乐部 问题是能否用网络的模块结构来重现这个过程 它是模块探测研究中的经典例子 W W Zachary Aninformationflowmodelforconflictandfissioninsmallgroups JournalofAnthropologicalResearch33 452 4731977 Girvan M Newman M Proc Natl Acad Sci 2002Ravasz E Somera A Mongru D Oltvai Z Barabasi A Science 2002Radicchi F Castellano C Cecconi F Proc Natl Acad Sci 2004Guimera R Mossa S Turtschi A Proc Natl Acad Sci 2005Guimera R Amaral L Nature 2005Newman M Proc Natl Acad Sci 2006Rosvall M Bergstrom C Proc Natl Acad Sci 2007Fortunato S Barthelemy M Proc Natl Acad Sci 2007Weinan E Li T Vanden Eijnden E Proc Natl Acad Sci 2008Rosvall M Bergstrom C Proc Natl Acad Sci 2008PeterJ Mucha etal Science2010Yong YeolAhn JamesP Bagrow SuneLehmann Nature 2010 生物信息学与最优化方法 7 Importanceofthetopic 社团结构探索方法概述 Alargenumberofmethodshavebeendevelopedfordetectingcommunities whichcanbegenerallycategorizedintolocalandglobalmethods Localmethodsforcommunitydetectionidentifyasubsetofnodesasacommunityaccordingtocertainlocalconnectionconditions independentlyfromthestructureoftherestofthenetwork Suchmethodsincludecliqueoverlap basedhierarchicalclustering cliquepercolationmethod andsub graphfitnessmethod Globalmethodsforcommunitydetectionoptimizecertainglobalquantitativefunctionsencodingthequalityoftheoverallpartitionofthenetwork suchasinformationtheoreticalmethod Pottsmodel andoptimizationofmodularitymeasures 8 9 ShihuaZhang Rui ShengWang andXiang SunZhang Identificationofoverlappingcommunitystructureincomplexnetworksusingfuzzyc meansClustering PhysicaA 2007 374 483 490 Rui ShengWang ShihuaZhang YongWang Xiang SunZhang LuonanChen Clusteringcomplexnetworksandbiologicalnetworksbynonnegativematrixfactorizationwithvarioussimilaritymeasures Neurocomputing 2007 ShihuaZhang Rui ShengWangandXiang SunZhang Uncoveringfuzzycommunitystructureincomplexnetworks PhysicalReviewE 76 046103 2007 我们小组在研究这一问题的早期发展了一些基于图论和矩阵谱分解的模块探测算法 localmethod 10 衡量网络模块化的指标Q值 设网络为N V E Pk V1 E1 Vk Ek 为一个分划 L Vi Vj Eij iinVi jinVj Newman和Girvan PhysicalReviewE 2004 提出一种衡量网络社区结构的指标Q值 11 指标Q的问题 Resolutionlimit FortunatoandBarth lemy PNAS 2007 利用Q划分网络的计算步骤 目前很大一部分模块探测的方法集中于利用各种启发式算法来极大化Q值 例如模拟退火 遗传算法等 Newman PNAS 2006 Guimera Nature 2005 Resolutionlimit现象 12 极端例子 ringofcliques Fortunato Barthelemy Proc Natl Acad Sci USA104 1 36 41 2007 13 提出新的模块化指标D值 模块化密度函数D ZhenpingLi ShihuaZhang Rui ShengWang Xiang SunZhang LuonanChen Quantitativefunctionforcommunitydetection PhysicalReviewE 77 036109 2008 14 D值克服了Q值存在的resolutionlimit问题 15 结果 Q值 D值 划分正确的顶点的比例 错分现象 Misidentification 用Q或D作优化可能得到不满足定义的模块 Qpartitionsthenetworkintothreecommunities twoKnandoneK5 whenn 16 respectively n 21 inwhichK5isasub graphviolatingallreasonablecommunitydefinition Xiang SunZhang Rui ShengWang YongWang Ji GuangWang Yu QingQiu LinWang andLuonanChen Modularityoptimizationincommunitydetectionofcomplexnetworks EurophysicsLetters EPL 87 2009 被评为EPL2009bestpaper 16 17 该文的主要贡献是用离散凸规划的概念对两个重要问题进行解析分析 Q值和D值的最优化模型都是非线性整数规划目标函数的凸性和凹性无法解析得到对两个具有特殊结构的网络进行分析引入离散凸规划 变量是离散的 可以嵌入一个连续的凸规划 的概念进行分析 得到解析解 所有对modularity进行研究的论文 指上面所列的的PNAS Nature Sience文章 都是试题论证的 即没有解析的证明 为了彻底分析resolutionlimit和Misidentification现象 我们对两类典型网络建立了优化模型 引入了离散凸分析技术 得到了两类问题的解析解 生物信息学与最优化方法 18 这两个例子出现在PNAS中几乎所有讨论网络模块探测的论文里 基于特殊结构的凸分析 adhocnetwork ringofdenselumps Finding1对 生物信息学与最优化方法 21 Finding2 Finding3 解析解表明 对这两个经典的算例 Q和D都有Resolutionlimit和Misidentification的现象产生 所以Q和D均只是近似的定量评估函数 网络社团划分的问题可以用一个优化问题来精确描述 我们证明了这一模型是NP hard的 我们相信用优化理论可以彻底解决网络社团划分的问题 网络科学是运筹学的下一个热点 22 23 为了彻底解决这些问题 提出一个新的OR模型和相应的算法 这一算法不会产生resolutionlimit和mis identification现象 Xiang SunZhang ZhenpingLi Rui ShengWang YongWang AcombinatorialmodelandalgorithmforgloballysearchingcommunitystructureincomplexnetworksJournalofCombinatorialOptimization JCO 2010 DOI 10 1007 s10878 010 9356 0 AnewORmodel Problemdefinition Givenanetwork thecommunityidentificationproblemistopartitionthenetworkintoasmanynon overlappingsub networksaspossiblesuchthateachsub networksatisfiesagivencommunitydefinition 24 以上文字定义可以用一个整数线性规划来描述 我们证明了这个模型是NP hard 25 Aqualifiedmin cut QMC algorithm Aheuristicprincipleisgiventofindafeasiblepartitionwiththelargestnumberofcommunities Itisrealizedbyamin cutoperation Amin cutoperationiscalledqualifiedifthetworesultingsub networkssatisfythemoduledefinition Thecommunityidentificationproblemcanbesolvedbasedonaseriesofqualifiedmin cutoperations 26 Experimentresults artificialnetworks Ringsofcliques Unevenad hocnetwork 27 Experim