1、现实世界中的诸多系统都以网络形式存在，现实世界中的诸多系统都以网络形式存在，如社会系统中的如社会系统中的人际关系网人际关系网、科学家协作网科学家协作网和和流行病传播网流行病传播网，生态系统中的，生态系统中的神经元网神经元网、基因调控网基因调控网和和蛋白质交互网蛋白质交互网，科技系统中的，科技系统中的因特网因特网、万维网万维网、通信网通信网、交通网交通网等。由于等。由于这些网络所对应的系统具有很高的复杂性，这些网络所对应的系统具有很高的复杂性，因 此 被 统 称 为因 此 被 统 称 为“复 杂 网 络复 杂 网 络(c o m p l e x network)”。社会网络（社会网络（Socia
2、l Networks）科学家协作网移动电话网络圣经对应的社会网络生物网络（生物网络（Biological Networks）食物链网络新陈代谢系统网络新陈代谢系统网络蛋白质交互网络蛋白质交互网络科技网络（科技网络（Technological Networks）对于小规模网络，我们可以对于小规模网络，我们可以通过肉眼观测其形态、特征，通过肉眼观测其形态、特征，但是对于但是对于(超超)大规模复杂网大规模复杂网络，我们将很难通过肉眼深络，我们将很难通过肉眼深入理解和预测网络的结构、入理解和预测网络的结构、行为和功能，需要借助各种行为和功能，需要借助各种复杂网络分析方法。复杂网络分析方法。复杂网络复杂
3、网络已成为当已成为当前最重要的多学科前最重要的多学科交叉研究领域之一。交叉研究领域之一。小世界性、无标度小世界性、无标度性、网络模体和网性、网络模体和网络簇结构络簇结构是迄今为是迄今为止发现的最普遍和止发现的最普遍和最重要的复杂网络最重要的复杂网络拓扑结构属性。拓扑结构属性。Small World(Nature 1998)小世界网络：小世界网络：具有具有较小较小的平均路的平均路径长度，同时具有径长度，同时具有较大较大的聚类系数。的聚类系数。平均长度：网络中任意两点间最短路径长度的平均值。平均长度：网络中任意两点间最短路径长度的平均值。聚类系数：节点的任意两个邻居节点仍互为邻居的平均概率聚类系数
4、：节点的任意两个邻居节点仍互为邻居的平均概率Scale-free network(Science 1999)无标度性：网络的度分布呈现出幂率分布（无标度性：网络的度分布呈现出幂率分布（power law），而），而不是随机网络的泊松分布：不是随机网络的泊松分布：P(K)K-aDegree distribution()!keP Xkk()aP XkkPoisson distributionPower-law distributionNetwork Motif(Science 1999)Network Motif：在统计意义上，网络中频繁出现的：在统计意义上，网络中频繁出现的子图模式。（某些子图在
5、现实网络中出现的概率明显高子图模式。（某些子图在现实网络中出现的概率明显高于这些子图在随机网络中出现的概率）。于这些子图在随机网络中出现的概率）。Network Community Structure(Science 2002,Nature 2005,2007)网络簇结构网络簇结构（network community structure）具有具有同簇节点相互连接同簇节点相互连接密集密集、异簇节点相互连接、异簇节点相互连接稀疏稀疏的特点。的特点。Nature 2005-100102030-10-5051015)/|(2jiijxxexpaGaussian similarity function（
6、高斯相似度函数）:(Nature 2005)科学家合作网：每个节点表示一个科学家，连接表示科学家之间的合作紧密程度。语义网络:每个节点表示一个英文单词，连接表示词在某个语境下共同出现的频率。Nature 2003Nature 2005(Nature 2005)（芽殖酵母菌）（芽殖酵母菌）的蛋白质交互网的蛋白质交互网络络(Nature 2007)该研究结果发现了维持社会结构稳定性的两个基本原则：该研究结果发现了维持社会结构稳定性的两个基本原则：对于大规模社会机构，其成分的对于大规模社会机构，其成分的动态变化动态变化利于维护该机构的稳定性；利于维护该机构的稳定性；相反的，对于小规模机构，其成分的相
7、反的，对于小规模机构，其成分的固定不变固定不变利于维护该机构的稳定性。利于维护该机构的稳定性。(Nature 2008)该研究提出了一种广义的随机网络模型该研究提出了一种广义的随机网络模型（相对于经典的（相对于经典的ER随机网络模型）：随机网络模型）：（1）具有更强的表达能力，既能刻画）具有更强的表达能力，既能刻画assortative网络又能刻画网络又能刻画disassortative网络；网络；（2）对于给定的网络，该模型能够精）对于给定的网络，该模型能够精确的预测出网络中的未知链接或缺失链确的预测出网络中的未知链接或缺失链接，并能剔除网络中存在的噪音链接。接，并能剔除网络中存在的噪音链接
8、。不同领域的权威国际杂志和不同领域的权威国际杂志和多个重要国际学术会议多次报道这多个重要国际学术会议多次报道这方面的研究工作。方面的研究工作。Complex networks clustering algorithmsOptimization based algorithmsHeuristic algorithmsOthersSpectral MethodsAverage cut Ratio cut Normalized cut Local Search Kernighan-Lin Fast Newman Guimera-AmaralPotts Model with multi-spin st
9、atesMFCGirvan-NewmanHITSWu-HubermanCPMTyler RadicchiSimilarity based methodsHybrid methodsCorrelation coefficientRandom walk based similarityClustering centralityHallDonetti-MunozFEC(Bell System Technical Journal,1970)2002年，格万和纽曼年，格万和纽曼(M.Girvan和和M.E.J.Newman)提出了基于提出了基于反复识别和删除簇间连接策略的复杂网络聚类反复识别和删除簇间连
10、接策略的复杂网络聚类算法算法GN.n GN算法算法的缺点的缺点 GN的最大缺点是计算速度慢，边介数计算的开销过大的最大缺点是计算速度慢，边介数计算的开销过大O(m n)，GN具有很高的时间复杂性具有很高的时间复杂性O(m2n)，只适合处理中小，只适合处理中小规模的网络规模的网络(包含几百个节点的网络包含几百个节点的网络)。n GN算法算法的意义的意义 在复杂网络聚类研究中，在复杂网络聚类研究中，GN算法占有十分重要的地位（该算法占有十分重要的地位（该文被引用超过文被引用超过1000次），格万和纽曼工作的重要意义在于：他次），格万和纽曼工作的重要意义在于：他们首次发现了复杂网络中普遍存在的们首次
11、发现了复杂网络中普遍存在的网络簇结构网络簇结构，启发了其他，启发了其他研究者对这个问题的深入研究，掀起了复杂网络聚类的研究热研究者对这个问题的深入研究，掀起了复杂网络聚类的研究热潮潮。目前，绝大多数算法不考虑目前，绝大多数算法不考虑重叠网络簇结构重叠网络簇结构。但在许多应用中，。但在许多应用中，重叠网络簇结构更具有实际意义。如在语义网中，多义词允许同重叠网络簇结构更具有实际意义。如在语义网中，多义词允许同时出现在多个表示不同词义的网络簇时出现在多个表示不同词义的网络簇 中中.2005年，帕拉年，帕拉(G.Palla)等等在在Nature上发表文章，首次提出了能上发表文章，首次提出了能识别重叠网
12、络簇结构的识别重叠网络簇结构的CPM算法算法.CPM简介简介n CPM的的基本假设基本假设 网络簇由网络簇由多个多个相邻的相邻的k-团团(k-clique)组成，两个组成，两个相邻的相邻的k-团团至少共至少共享享k-1个节点个节点，每个，每个k-团团唯一的唯一的属于某个网络簇，但属于某个网络簇，但属于不同网络属于不同网络簇的簇的k-团团可能会共享某些节点。可能会共享某些节点。nCPM的的缺点缺点 1)实际应用中实际应用中参数参数k难以确定难以确定，选取不同的，选取不同的k值会得到不同的网值会得到不同的网络簇结构。络簇结构。2)计算网络中的全部计算网络中的全部k-团团非常耗时非常耗时，CPM非常
13、慢，其时间复杂非常慢，其时间复杂性近似为性近似为指数阶指数阶。Detect communities from decentralized networksB Yang,J Liu,D Liu.An autonomy-oriented computing approach to community mining in distributed and dynamic networks.Autonomous Agents and Multi-Agent Systems(JAAMAS),2010.Detect web communitiesB Yang,J Liu.Discovering Global
14、 Network Communities Based on Local Centralities.ACM Transactions on the Web(TWEB),2008.Detect communities from signed networksB Yang,WK Cheung,J Liu.Community Mining from Signed Social Networks.IEEE Transactions on Knowledge and Data Engineering(TKDE),2007.Detect communities from dynamic networksB
15、Yang,D Liu.Force-based Incremental Algorithm for Mining Community Structure in Dynamic Network.Journal of Computer Science and Technology(JCST),2006.Spectral analysis for community structures NSFC project(2009-2011)&NLPR Open Project(2009-2010)Novel spectral model and method Spectral analysis for directed networks Spectral analysis for assortative/disassortative networks Statistical relational learning for graph mining NSFC project(2010-2012)Combine inference and learning for networked data Link prediction Collective classificationGeo-spatial dataBiomedical DataClimate DataSensor Networks
