извлечение подграфа на основе весов ребер и связности графа - PullRequest
Новая
       6

извлечение подграфа на основе весов ребер и связности графа

0 голосов
/ 02 июля 2018

Учитывая матрицу, которая описывает ребра и их веса связного графа (см. Ниже), я хочу извлечь подграф на основе порогового значения x для весов ребер. В литературе я читал, что можно искать максимум x , так что индуцированный подграф связан.

Поскольку исходный граф предполагается подключенным, должен быть критический порог x-critical, что извлеченный подграф подключен для любого x <= 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)

Также вот статья , ссылающаяся на эту технику на странице 15 в pdf, раздел 5 четвертый. Вы можете рассматривать релевантность края как вес края, обсужденный здесь.

1 Ответ

0 голосов
/ 03 июля 2018

Я работаю в 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.

EDIT:

В 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
...