GN 算法介绍 哈尔滨工业大学

复杂网络简介报告人：于杨哈尔滨工业大学智能技术与自然语言处理研究室2010-10复杂网络定义

复杂网络(comlexnetwork):

是由规模巨大的节点和链接关系错综复杂的边而构成的网络结构。复杂网络表现结构复杂：表现在节点数目巨大，网络结构呈现多种不同特征。节点复杂性：复杂网络中的节点可以代表任何事物。各种复杂因互相互影响：多重复杂性相互影响，导致更为难以预料的结果。复杂网络特征节点、边关联与邻接度k、平均度节点的度分布p(k)最短路径与平均路径长度（Dijkstra算法）集聚系数C节点的度分布是指网络（图）中度为的节点的概率随节点度的变化规律。 两点之间的最短路径：从指定始点到指定终点的所有路径中长度最小的一条路径。网络平均路径长度：所有点对之间的最短路径的算术平均值。集聚系数复杂网络的静态结构研究小世界(Smallworld)，尺度无关（Scalefree)，聚类特性

(Clustering)

的确切数学模型。

社团结构(CommunityStructure)…………小世界效应

小世界效应指的是网络节点间的平均距离较小，平均聚集系数较大。从图中可以看出，在蛋白质相互作用网络中，度高的节点很少直接连接在一起，而是通过其它度低的节点连到一起的。无标度性质（Scalefree）

网络中节点一个最重要的特征就是节点的度。网络构成的无向图而言，网络中存在许多度较低的顶点和少量的度较高的顶点，顶点度的分度服从幂律分布，这个性质称为无标度性质。

这意味着一个具有k个度的节点个数分布服从幂指函数，其中c和r是常数。社区性

首先，是研究的局部邻接点，也就是聚类系数。其次，社区内节点之间可能存在较长的路径。许多真实的网络，如蛋白质相互作用网络呈现出很强的社区性，此特点主要是通过这些图的聚类系数要比同规模的随机网的要高的事实得到很好的证明。社区发现一般意义上，社区结构是大规模网络中普遍存在的基本结构，即：一个网络是由大量内部连接“紧密”、外部连接“稀疏”的子团组成，这些具有统计显著性的子团结构成为一个网络的社区结构信息网络中，社区通常对应着功能相同、性质相近或者关系密切的节点集合社会关系网络中的朋友圈子Web网络中的相近主题的页面集合蛋白质交互网络中，功能相近的蛋白质集合GN算法介绍2002年，由Girvan和Newman提出GN算法基本思想：不断的从网络中移除介数最大的边。边介数：网络中经过每条边的最短路径的数目。基本流程计算网络中所有边的介数找到介数最高的边并将它从网络中移除重复第二步，直每个节点就是一个退化的社团为止。GN算法存在的问题社区结构没有定量的定义哪一步终止17衡量网络模块化的指标Q值

设网络为N=（V，E）,Pk={(V1,E1),…,(Vk,Ek)}为一个分划。Eij表示网络中连接两个不同社区点的边在所有边中所占的比例，这两点节点分别位于第i个社区和第j个社区。定义每行（或者列）中各元素之和为ai=Newman和Girvan提出一种衡量网络社区结构的指标Q值

物理意义：网络中连接两个同种类型的节点的边的比例，减去在同样的社团结构下任意连接这两个节点的边的比例的期望值。

Q值越接近1，社团结构越明显。实际应用中通常在0.3－0.7之间。GN算法是分裂法，可以用树状图来表示算法过程。当沿着树状图逐步下移时，每移一步就对该截取位置对应的网络结构对就的Q值，并找到局部峰值，既是对应着的比较好的截取位置。

图为64个节点生所随机图中划分的社区此图为美国一所大学中的空手道俱乐部成员间的相互社会关系.参考文献NewmanME,GirvanM.Findingandevaluatingcommunitystructurein