格文-纽曼算法

✍ dations ◷ 2025-07-07 14:19:08 #格文-纽曼算法

格文-纽曼算法（得名于米歇尔·格文（英语：Michelle Girvan）和马克·纽曼（英语：Mark Newman））是复杂系统启发式社区发现算法。

格文-纽曼算法通过不断地删除网络中的边来检测网络中的社区。在最终剩余的网络中的连通分量也就是社区。格文-纽曼算法并不是去测量哪些边具有最高的中心度，而是去关注哪些最有可能连接着社区。

顶点介数是一种反应网络中顶点的中心度的指标。对于一个顶点i，顶点介数是指网络中经过该顶点的所有最短路径的数量。

格文-纽曼算法将介数扩展到了边。类似地，一条边的边介数是指网络中经过该边的最短路径的数量。如果一个网络所包含的社区之间是由少量的边连接的，那么经由不同社区的最短路径都需要从这些边上经过，因此这些边的边介数会非常高。通过移除这些边，各个社区之间将会被分割开来，从而可以发现这些社区。

格文-纽曼算法的步骤如下：

重新计算剩余每条边的边介数需要不少计算时间，然而，并没有较好的办法省去这些开销。当一条边被删除了之后，网络的结构发生了变化，举个例子来说，假设两个社区之间有不止一条边连接，那么并不是每条边都会有较高的边介数，我们只能逐渐地删除这些边，在这个过程中会发现至少有一条边会有较高的边介数。

格文-纽曼算法的结果是一个树状图。这个树状图自顶向下地描绘了社区的结构。树状图的叶子则是图的每个结点。

相关

格里菲斯实验格里菲斯实验（Griffith's experiment），又称格里菲斯转型实验，是由弗雷德里克·格里菲斯（Frederick Griffith）在1928年利用肺炎链球菌与老鼠所进行的一系列生物学实验。实验结果显
王崇愚王崇愚（1932年10月12日－），满族，物理学家，中国科学院院士。主要研究领域为计算凝聚态物理及计算材料物理，在金属合金领域作出重大贡献，是中国多尺度研究领域的开拓者。王崇愚1950年秋
二氯一氟乙烷1,1-二氯-1-氟乙烷是一种卤代烷，化学式为C2H3Cl2F。它是二氯氟乙烷的三种同分异构体之一。1,1-二氯-1-氟乙烷的主要用途是用作制冷剂，又被称为R-141b或HCFC-141b。
美国海军特种作战开发组海豹部队第六分队紧急狂暴行动贝鲁特人质危机阿基莱·劳伦号事件美国海军特种作战开发组（英语：United States Naval Special Warfare Development Group，缩写：NSWDG，常用缩
藤川优里藤川优里（1980年3月8日－）是日本一位女性政治家，现任青森县八户市市议会议员。藤川是一位无派别的自由民主党党员，但加入了属于保守派系的“自由民主会”。藤川是日本政坛内少有的
马奎斯·丹尼尔斯马奎斯·丹尼尔斯（英语：Marquis Daniels，1981年1月7日－），生于美国佛罗里达州，NBA前职业篮球运动员。2009年夏天，为了夺取总冠军，丹尼尔斯加盟波士顿。2011年2月6日，凯尔特人与奥兰多魔
奥斯曼尼耶奥斯曼尼耶（土耳其语：Osmaniye）是土耳其奥斯曼尼耶省的城市，也是该省的首府，邻近叙利亚西北部边境，全县面积约746平方公里，海拔高度125米。奥斯曼尼耶受地中海气候影响，每年平均降雨量874毫米。2012年奥斯曼尼耶市区人口为209,255。
滑藤滑藤（学名：）为萝藦科滑藤属下的一个种。
波德里查区波德里查区（黑山语：），是黑山的24个行政区之一。
5+2产业创新计划5+2产业创新计划是蔡英文政府为了加速台湾产业升级与产业结构转型，由行政院推出振兴经济措施，追求永续发展的经济新模式。包含“智慧机械”、“亚洲硅谷”、“绿能科技”、“生医产业”、“国防产业”、“新农业”及“循环经济”等领域之发展。