基于边权和图连通性的子图提取

Question

给定一个描述连通图的边及其权重的矩阵（见下文）我想根据边的阈值 x 提取子图'权重。在文献中，我读到可以搜索 maximal x，使得导出的子图是连通的。

由于假定初始图是连通的，因此对于任何 x <= x-critical.

，提取的子图必须存在连通的临界阈值 x-critical

我想知道如何在 R 中实现它。例如，我的矩阵 (weights.matrix) 看起来像

| FROM | TO | WEIGHT |
| A    | B  | 0.0042 |
| A    | V  | 0.23   |
| G    | W  | 0.82   |
| ...  | ...| ...    |

我正在创建整个图，使用 igraph 包，例如：

g <- igraph::graph_from_data_frame(weights.matrix, directed = TRUE)

是否有任何方法可以重复检查 - 通过在从 min() 到 max() 的权重中应用不同的阈值 - 如果出现的图是连接的？我在 google 中搜索了 igraph 中的此类功能，但找不到任何有用的信息。

下面是一些用于构建此类图表的代码。

library(igraph)

mat <- expand.grid(LETTERS[1:10], LETTERS[1:10])
mat$Weight <- runif(nrow(mat), 0.01, max = 1)
mat <- mat[mat$Var1!=mat$Var2, ] 

g <- graph_from_data_frame(mat)

另外 here is a paper 在 pdf 的第 15 页，第 5 节第四节中引用了该技术。您可以将边相关性视为此处讨论的边权重。

Answer 1

我在python工作，不是R，所以下面只是伪代码。

我会处理邻接矩阵（不是 igraph 对象），因为这将是最快的。设 A 为邻接矩阵，W 为排序的权重列表，w 为 W 的元素。基本思想是迭代邻接矩阵 A 中的所有权重，每个权重的阈值 A 并检查空行（和列，如果图形是有向的）。

那么定向案例的伪代码是：

function (A) -> w

W = sort(list(A))

for w in W:
    A' = A > w
    for row in A':
        if sum(row) == 0:
            for col in A':
                if sum(column) == 0: 
                     return w

有很多方法可以对此进行优化，但这只是说明了基本思想。 #

最快的方法可能是计算每一行和每一列的最大权重，maxima_rows 和 maxima_columns，找到它们的最小值，min_max_row 和 min_max_col，然后取这两个值中的最大值得到 w。

编辑：

在 python 中，快速方法如下所示：

from numpy import min, max

def find_threshold_that_disjoints_graph(adjacency_matrix):
    """
    For a weighted, fully connected graph, find the weight threshold that results in multiple components.

    Arguments:
    ----------
    adjacency_matrix: (N, N) ndarray of floats

    Returns:
    --------
    threshold: float

    """
    maxima_rows = max(adajacency_matrix, axis=1) # (N, ) vector
    maxima_cols = max(adajacency_matrix, axis=0) # (N, ) vector

    min_max_rows = min(maxima_rows) # float
    min_max_cols = min(maxima_cols) # float

    threshold = max([min_max_rows, min_max_cols])

    return threshold

基于边权和图连通性的子图提取

subgraph extraction based on the edges weights and graph connectivity

r

graph

igraph

threshold

编辑：