【大数据分析】图的连通度（门格尔定理）

门格尔定理（menger’s theorem）

定理一，点连通度定理

设顶点 $s$ 和顶点 $t$ 为图 $G$ 中两个不相邻的顶点，则顶点 $s$ 和顶点 $t$ 分别属于不同的连通片所需取出的顶点的最少数目等于连接顶点 $s$ 和顶点 $t$ 的独立的简单路径的最大数目。

定理二，边连通度定理

设顶点 $s$ 和顶点 $t$ 为图 $G$ 中不同的顶点，则使顶点 $s$ 和顶点 $t$ 分别属于不同的连通片所需去除的边的最少数目等于连接顶点 $s$ 和 顶点$t$ 的不相交的简单路径的最大数目。

如下图所示：

（1）不相邻的两个顶点。即这两个顶点没有边直接相连。如果顶点 $s$ 和 $t$ 为相邻顶点，那么即使把上图 $G$ 中的所有其他的顶点都去除也无法使这两个顶点分别属于不同的连通片，所以定理一中要求两个顶点 $s$ 和 $t$ 不相邻。
（2）$s$ 和 $t$ 的两条简单路径相互独立。是指两条路径的公共顶点只有 $s$ 和 $t$。
（3）$s$ 和 $t$ 的两条简单路径不相交。指这两条路径没有经过一条相同的边(但可以有共同顶点)。
（4）点割集（Vertex cutset）。使得一对顶点分属于不同连通片所需去除的一组顶点称为这对顶点的点割集（Vertex cutset）。
（5）边割集（Vertex cutset）。使得一对顶点分属于不同连通片所需去除的一组边称为这对顶点的边割集（Edge cutset）。
（6）极小割集（Minimum cutset）。包含顶点数或边数最少的割集称为极小割集。根据门格尔定理，为了计算使顶点s和顶点t分离所需要去除的顶点的最少数目，只需要求出顶点s和顶点t之间所有的简单路径。

图的点连通度代码解析

图的点连通度计算包含三个步骤：
（1）找出图中拥有最小出度的点 $source$。
（2）找出 $source$ 与其他非相邻节点的最短路径，求出这些路径各自的连通度，并取它们的最小值$k_1$。
（3）找出 $source$ 的相邻节点中任意两个彼此不相邻节点之间的最短路径，求出这些路径各自的连通度，并取它们的最小值$k_2$（注意这两个节点不能是相邻的，即，假设相邻节点为 $a$，$b$ 都是 $source$ 的相邻节点，$a$ 和 $b$ 不能相邻 ）。
（4）取 $k_1$ 和 $k_2$ 中的更小的那个值。

package com.edata.bigdata.algorithm.networks

import org.apache.spark.graphx.{EdgeDirection, EdgeTriplet, Graph,  VertexId}
import spire.ClassTag

/**
 * @author: Alan Sword
 * @link: https://blog.csdn.net/sword_csdn/article/details/126461322
 * @deprecated
 */
object NodeConnectivity extends Serializable {

  def run[VD, ED: ClassTag](graph: Graph[VD, ED]): Int = {
    //You can not use 'graph' variable directly，because errors will occur
    val NCGraph = graph.mapVertices { (vid, attr) =>
    }
    //find the vertex s that has minimum out degree
    val source = NCGraph.outDegrees.min()
    //find the neighbor vertexs of s
    val neighbor_ids_out = NCGraph.collectNeighborIds(EdgeDirection.Out).filter(_._1 == source._1).collect()(0)
    val neighbor_ids_in = NCGraph.collectNeighborIds(EdgeDirection.In).filter(_._1 == source._1).collect()(0)
    //combine source vertex id and its' neighbor ids together
    val source_and_neighbor_ids = (neighbor_ids_in._2 ++ neighbor_ids_out._2).toSet + neighbor_ids_out._1
    //find the vertexs that does not contain source and its neighbors
    val not_source_and_neighbor_ids = NCGraph.vertices.filter(vertex => {
      !source_and_neighbor_ids.contains(vertex._1)
    }).map(vertex => vertex._1).collect().toSet
    //find the neighbors' ids of source vertex
    val neighbor_ids = (neighbor_ids_in._2 ++ neighbor_ids_out._2).toSeq
    //find all the ids of vertex
    val all_ids = NCGraph.vertices.map(vertex => vertex._1).collect().toSeq
    val resultGraph = AllPairNodeConnectivity.run(graph, all_ids)

    //calculate the source's connectivity with all non-neighbors nodes and find the minimum
    val k_1 = resultGraph.vertices.filter(_._1 == source._1).collect()(0)._2.filter(data => {
      not_source_and_neighbor_ids.contains(data._1)
    }).min._2
    //calculate the connectivity of non adjacent pairs of neighbors of source
    val k_2 = resultGraph.vertices.filter(vertex => {
      neighbor_ids.contains(vertex._1)
    }).map(x => {
      val v = x._2.filter(y => {
        y._2 != 0 && y._2 != 1
      })
      val k = x._1
      (k, v)
    }).filter(x => {
      !x._2.isEmpty
    }).mapValues(x => x.min._2).map(x => {
      x._2
    }).collect().min
    if (k_1 >= k_2) k_2 else k_1
  }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56