代码之家 › 专栏 › 技术社区 › J. Doe

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

threshold igraph graph r

2

J. Doe · 技术社区 · 7 年前

给定一个描述连通图的边及其权值的矩阵(见下文),我想基于一个阈值提取一个子图十边缘的重量。在文学方面,我读到人们可以寻找 最大x ,从而使所诱导的子图是连接的。

因为初始图假设是连通的,所以必须有一个临界阈值 x-critical 所提取的子图与 x <= x-critical 是的。

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

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

我正在创建整个图形,使用i graph包,比如:

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节第4节中提到了这种技术。可以将边缘相关性视为此处讨论的边缘权重。

1 回复 | 直到 6 年前

1

Paul Brodersen 7 年前

我在python中工作,而不是r,所以下面只是伪代码。

我将研究邻接矩阵(不是igraph对象),因为这将是最快的。让 A 是邻接矩阵, W 重量和 w 元素 西 是的。基本思想是迭代邻接矩阵中的所有权重。 一个 ,阈值 一个 在每个权重处,检查是否有空行(和列,如果图是有方向的)。

则定向情况的伪代码为:

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 然后取这两个值的最大值 西 是的。

编辑:

在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