复杂网络中重叠社团发现的算法探讨.pdf

。知鞘誊牖论坛 复杂网络中重叠社团 发现的算法探讨 口矗丽娟屈宝强／中圆科学技术信息研完所北京1∞0∞ 0126 i玛／西安电子科技大荦西安71 现实世界中许多系统都可以用 不断增多，复杂网络聚类算法旨在 矩阵的特征向量来优化预定义的 复杂网络来描述，如科研合作网、 揭示出复杂嘲络中真实存在的网络 “截(cut)”函数。后者将复杂 万维网、沦文引用网．因特网、电 簇结构，对其的研究对分析复杂网 列络聚类问趣转化为预定义启发式 力同、神经喇络、新陈代谢嘲络以 络的拓扑结构、理解复杂网络的功 规则的设计问题。如被广泛引用 及食物链网络等。近年来，复杂婀 能、发现复杂刚络中的隐藏规律以 的Oi…．New呻Ⅱ算法”’的启发式 络已经成为当令抖学界研究的前沿 及预测复杂网络的行为．不仅具有 规则是簇问连接的边介数(edge 和热点．研究者来自物理学、生物 十分重要的理论意义，而且具育广 bccw优恤嘲)应人于壤内连接的边 学、计算机科学、管理学、社会学 泛的应用前景。 升数。 以及经济学等各个不同领域。从 虽然上述算法都有自己的优 美国科学信息研究所(IsI)的统 1现钉聚类算法及其 点，怛都仅局限在某些特定的网络 计结粜可知”I．200m2009卜年问发 结构中．不适用于所有网络结构。 局限性 表的．以“复杂网络”(com口1ex 在现实世界复杂网络社团之问通常 日etwofks)为主题(toDtc)的scIH前已存在多种复杂瞄络聚 台存在一些重叠点，这些点属于社 论文达到了4925篇之多．引用高达类算往其中扬博”1等^在相关研 团问的交叉部分。现有的许多算法 究中提出，按照所采用的基本求 部只能得到标准化划分，即节点有 76834敬，而且依旧呈现强劲的E 涨势头。得益J僻芙荣、汪小帆等 解镱略．将其归为两太类：基于 且只属于个社团的情况． based T程科学学者以及A锦清、何太 优化的^法(oⅢImIzallon 韧、狄增如等物理科学学者早期的 method)和启发式方法(heum“c 推动．我国学青得以较早意识到复 m劬0d)．前者将复杂恻络聚类问 杂时络研究的重要性．也昼现出了 题转化为优化问题．通过撮优化 迅猛发展的势头。在统计的scj论颅定义的目标函数米¨算复祭州 卤硷 空中．地址中标明中国的论史儿 络的牍结构。如谱方法(s口ectral 有l3I8篇．超过了旧分之”】。同 mcIhod)将阿络聚娄问j曼l转化为 样耐复帑网络聚擞^浊”的研究电 一次型优化问题．通吐¨算特殊 翻I社团结构圈之一 48 2011年尊5■fe第叫m) 万方数据 ov罱鞴论佑 如图l所示，白色节点既可以 2聚类算法的嫂进 接的边数为2．3：2=l510，则认为 属十左边社团，也可以属于右边社