西安电子科技大学：《复杂网络与群体智能》课程教学课件（复杂网络）第七讲 最小生成树社区检测

历华毛子代枝大” 第八讲：最小生成树-社区检测 XIDIAN UNIVERSITY >最小生成树 >基于最小生成树的社区检测 2

最小生成树 基于最小生成树的社区检测 第八讲：最小生成树-社区检测 2

历些毛子种枝大票 最小生成树 XIDIAN UNIVERSITY 1. 什么是最小生成树(minimum spanning tree)? 所谓最小生成树，就是在一个具有N个顶点的加权连通图G 中，如果存在某个树形子图T,其包含了图G中的所有项点和 一部分边，且不形成回路，并且子图T的各边权值（距离）之 和最小，则称T为图G的最小生成树。 0.55 0.5」 0.5 12 15 12 15 0.43 0.5\0.55 0.5 0.43 0.75 0.75 0.43 0.55 0.5 0.43 /0.46 0.46 0.46 0.43 13 10 0.55 0.460.75 0.43 八14/0.43 0.46 0.75 0.6 > 0.43 75 0.55 0.75 0.60.75 0.75 0.75 0.55 .75 0.75 图1.一个网络与它的最小生成树 3

1. 什么是最小生成树（minimum spanning tree ）？ 所谓最小生成树，就是在一个具有N个顶点的加权连通图G 中，如果存在某个树形子图T，其包含了图G中的所有顶点和 一部分边，且不形成回路，并且子图T的各边权值（距离）之 和最小，则称T为图G的最小生成树。 最小生成树 3 0.55 0.55 0.75 0.75 0.6 0.46 0.46 0.43 0.46 0.6 0.5 0.5 0.43 0.75 0.75 0.75 0.75 0.43 0.5 0.55 0.5 0.43 0.55 0.55 0.55 0.43 10 9 11 14 12 15 7 3 5 2 1 6 4 a 8 0.75 13 0.43 0.75 0.6 0.46 0.46 0.43 0.75 0.75 0.5 0.43 0.5 0.43 0.55 0.75 10 9 11 13 14 12 15 5 1 6 2 7 4 3 8 b 图1. 一个网络与它的最小生成树

历安毛子代枚大等 最小生成树 XIDIAN UNIVERSITY 2.最小生成树的特性 > 无环，不能有回路 节点数和网络节点数相等 > 边数比节点数少一个 > 最小生成树可能有一个，也可能有多个 0.55 0.5 0.5 15 12 0.43 4 0.5 0.5 0.55 4 0.43 0.75 0.75/ 0.43 0.43 0.55 0.46 0.43 13 /0.46 0.46 10 0.55 0.460.75 0.43 5 0.46 > 0.75 0.55八14 0.43 0.55 0.75 0.6 0.43 0.75 0.6 0.75 0.75 0.6 0.75 0.75 0.55 11 f 0.75 图1.一个网络与它的最小生成树 4

2. 最小生成树的特性  无环，不能有回路  节点数和网络节点数相等  边数比节点数少一个  最小生成树可能有一个，也可能有多个 最小生成树 4 0.55 0.55 0.75 0.75 0.6 0.46 0.46 0.43 0.46 0.6 0.5 0.5 0.43 0.75 0.75 0.75 0.75 0.43 0.5 0.55 0.5 0.43 0.55 0.55 0.55 0.43 10 9 11 14 12 15 7 3 5 2 1 6 4 a 8 0.75 13 0.43 0.75 0.6 0.46 0.46 0.43 0.75 0.75 0.5 0.43 0.5 0.43 0.55 0.75 10 9 11 13 14 12 15 5 1 6 2 7 4 3 8 b 图1. 一个网络与它的最小生成树

历安毛子代枚大” 最小生成树 XIDIAN UNIVERSITY 3. 最小生成树算法 > 无环，不能有回路 节点数和网络节点数相等 > 边数比节点数少一个 最小生成树可能有一个，也可能有多个 0.55 0.5 0.5 12 12 15 0.43 4 0.5 0.55 0.43 0.43 .5 0.75 0.43 0.43 0.75 0.55 0.46 0.46 0.46 0.43 0.43 10 5 0.55八14 /0.43 0.55 .460.75 0.46 0.75 0.55 0.75 0.6 7 0.43 0. 0.75 0.6 0.75 0.75 0.55 0.75 图1.一个网络与它的最小生成树 5

3. 最小生成树算法  无环，不能有回路  节点数和网络节点数相等  边数比节点数少一个  最小生成树可能有一个，也可能有多个 最小生成树 5 0.55 0.55 0.75 0.75 0.6 0.46 0.46 0.43 0.46 0.6 0.5 0.5 0.43 0.75 0.75 0.75 0.75 0.43 0.5 0.55 0.5 0.43 0.55 0.55 0.55 0.43 10 9 11 14 12 15 7 3 5 2 1 6 4 a 8 0.75 13 0.43 0.75 0.6 0.46 0.46 0.43 0.75 0.75 0.5 0.43 0.5 0.43 0.55 0.75 10 9 11 13 14 12 15 5 1 6 2 7 4 3 8 b 图1. 一个网络与它的最小生成树

历安毛子代枚大等 最小生成树 XIDIAN UNIVERSITY 3.克鲁斯卡尔算法(Kruskal Algorithm) 第一步：在带权连通图中，将边的权值排序； 第二步：从权值最小的边开始，判断是否需要选择这条边。判断 的依据是边的两个顶点是否已连通，如果连通则继续下一条；如 果不连通，那么就选择使其连通。 连通时，要做如下判断：这两个点是否在己找到点的集合中 出现过？①.如果两个点都没有出现过，那么将这两个点都加入已 找到点的集合中；②如果其中一个点在集合中出现过，那么将另 一个没有出现过的点加入到集合中；③如果这两个点都出现过， 则不用加入到集合中。 第三步：循环第二步，直到图中所有的顶点都在子图中，即得到 最小生成树。 6

3. 克鲁斯卡尔算法(Kruskal Algorithm) 第一步：在带权连通图中，将边的权值排序； 第二步：从权值最小的边开始，判断是否需要选择这条边。判断 的依据是边的两个顶点是否已连通，如果连通则继续下一条；如 果不连通，那么就选择使其连通。 连通时，要做如下判断： 这两个点是否在已找到点的集合中 出现过？ ①.如果两个点都没有出现过，那么将这两个点都加入已 找到点的集合中；②.如果其中一个点在集合中出现过，那么将另 一个没有出现过的点加入到集合中；③.如果这两个点都出现过， 则不用加入到集合中。 第三步：循环第二步，直到图中所有的顶点都在子图中，即得到 最小生成树。 最小生成树 6