跳到内容

图或两个顶点的顶点连通性,最近也称为群体凝聚力。

用法

vertex_connectivity(graph, source = NULL, target = NULL, checks = TRUE)

vertex_disjoint_paths(graph, source = NULL, target = NULL)

# S3 method for class 'igraph'
cohesion(x, checks = TRUE, ...)

参数

graph, x

输入图。

source

源顶点的ID,对于 vertex_connectivity() 它可以是 NULL,请参见下面的详细信息。

target

目标顶点的ID,对于 vertex_connectivity() 它可以是 NULL,请参见下面的详细信息。

checks

逻辑常量。是否检查图是否连通以及顶点的度。如果图不是(强)连通的,那么连通性显然为零。否则,如果最小度为 1,则顶点连通性也为 1。执行这些检查是个好主意,因为与连通性计算本身相比,它们可以快速完成。Peter McMahan 提出了这些建议,谢谢 Peter。

...

传递给方法的其他参数。vertex_connectivity() 不直接使用,但可以被实现 cohesion() 的其他方法使用。

一个标量实数值。

详细信息

图中两个顶点(sourcetarget)的顶点连通性是必须删除的最小顶点数,以消除从 sourcetarget 的所有(有向)路径。如果给出了 sourcetarget 参数并且它们不是 NULL,则 vertex_connectivity() 会计算此数量。

一对顶点的顶点连通性与从源到目标的不同(即节点独立)路径的数量相同,假设它们之间没有直接边。

图的顶点连通性是图中所有(有序)顶点对的最小顶点连通性。换句话说,这是使图不是强连通的所需移除的最小顶点数。(如果图不是强连通的,则此值为零。)如果没有给出 sourcetarget 参数,则 vertex_connectivity() 会计算此数量。(即它们都是 NULL。)

sourcevertex 的一组顶点不相交的有向路径是一组它们之间的有向路径,这些路径的顶点不包含公共顶点(除了 sourcetarget)。两个顶点之间的最大顶点不相交路径数在大多数情况下与它们的顶点连通性相同(如果两个顶点没有通过边连接)。

图的凝聚力(由 White 和 Harary 定义,请参阅参考文献)是图的顶点连通性。这是由 cohesion() 计算的。

这三个函数本质上计算相同的度量,更准确地说,vertex_connectivity() 是最通用的,其他两个函数仅为了便于使用更具描述性的函数名称而包含在内。

参考文献

White, Douglas R and Frank Harary 2001. The Cohesiveness of Blocks In Social Networks: Node Connectivity and Conditional Density. Sociological Methodology 31 (1) : 305-359.

作者

Gabor Csardi csardi.gabor@gmail.com

示例


g <- sample_pa(100, m = 1)
g <- delete_edges(g, E(g)[100 %--% 1])
g2 <- sample_pa(100, m = 5)
g2 <- delete_edges(g2, E(g2)[100 %--% 1])
vertex_connectivity(g, 100, 1)
#> [1] 1
vertex_connectivity(g2, 100, 1)
#> [1] 5
vertex_disjoint_paths(g2, 100, 1)
#> [1] 5

g <- sample_gnp(50, 5 / 50)
g <- as_directed(g)
g <- induced_subgraph(g, subcomponent(g, 1))
cohesion(g)
#> [1] 2