R igraph: кратчайшее извлечение пути

Question

Это первый раз, когда я работаю с графиками и Rigraph пакетом, и мне нужна помощь в обработке объектов графа.

То, что я хочу добиться:
Из данной контактной матрицы экстракте кратчайшее уверенно пути между узлами. Я уверен, что вес кромки выше соседних краев.

Примеры:

m <- read.table(row.names = 1, header = TRUE, text = 
    " A B C D E F 
    A 0 1 1 1 1 5 
    B 1 0 1 1e2 1e2 1 
    C 1 1 0 1 1 1 
    D 1 1e2 1 0 1e2 1 
    E 1 1e2 1 1e2 0 1 
    F 5 1 1 1 1 0") 
m <- as.matrix(m) 
ig <- graph.adjacency(m, mode = "undirected", weighted = TRUE, diag = FALSE) 
sp <- shortest.paths(ig, algorithm = "dijkstra") 

В матрице m есть один кластер (клика?) Между B-D-E (т.е. EGDE вес между этими узлами является высоким.). Однако, поскольку есть вес между A и F, я также получаю кластер, хотя вес края низкий (всего 5).
Вопрос: Как извлечь только те кластеры, которые имеют большой вес кромки? Я могу преобразовать эти контакты в 0 с m[which(m <= 5)] <- 0, но я надеюсь, что для этого в пакете igraph есть более «мати».

Б

m <- read.table(row.names = 1, header = TRUE, text = 
    " A B C D E F 
    A 0 1 1 5 1 1 
    B 1 0 1 1e2 1e2 1 
    C 1 1 0 1 1 1 
    D 5 1e2 1 0 1e2 1 
    E 1 1e2 1 1e2 0 1 
    F 1 1 1 1 1 0") 
m <- as.matrix(m) 
ig <- graph.adjacency(m, mode = "undirected", weighted = TRUE, diag = FALSE) 
sp <- shortest.paths(ig, algorithm = "dijkstra") 

В матрице m есть кластер между B-D-E, но так как есть низкий вес между A и B - A также подключен к этой группе.
Вопрос B: Как не назначать узлы кластеру, если вес края низкий?

Это мой первый вопрос здесь, если вам нужны разъяснения или лучшие примеры, я улучшу свои вопросы.

Answer 1

Во-первых, это хорошо, чтобы знать, что при поиске путей, igraph понимает веса, как затраты, т.е. по краям с большим весом он стоит больше путешествовать, поэтому рассмотрим более короткие пути с меньшим весом суммы. Легко превратить это в противоположное, просто возьмите обратно свои веса (1/E(ig)$weight). Между двумя вершинами может быть только один короткий путь, но иногда есть более одинаковые короткие пути. Вы можете просмотреть все из них (all_shortest_paths) или сообщить igraph, чтобы вернуть только один из кратчайших для каждой пары вершин (shortest_paths). Каждый вызов этих методов возвращает пути из одной выбранной вершины, чтобы иметь пути между всеми парами, вам нужно вызвать их один раз для каждой вершины (ok, на неориентированном графике, достаточно вызвать половину вершин). Для того, чтобы сформулировать то, что я не объяснил до этого момента:

spaths <- lapply(V(ig), 
       function(v){ 
        all_shortest_paths(ig, v, 
             weight = 1/E(ig)$weight 
        ) 
       } 
      ) 

Здесь spaths будет список списков, доступ к пути от C всех вершин, как это:

spaths$C$res 

[[1]] 
+ 2/6 vertices, named: 
[1] C A 
[[2]] 
+ 2/6 vertices, named: 
[1] C B 
[[3]] 
+ 1/6 vertex, named: 
[1] C 
[[4]] 
+ 2/6 vertices, named: 
[1] C D 
[[5]] 
+ 2/6 vertices, named: 
[1] C E 
[[6]] 
+ 2/6 vertices, named: 
[1] C F 

spaths$C$res[[2]] # this is the path from `C` to `B`, 
        # a vector of 2 vertices 

Отметим, что третий элемент является на самом деле от C к себе, вы можете либо игнорировать его, либо предоставить вектор всех других вершин для параметра toall_shortest_paths.Кроме того, в вашем примере все кратчайшие пути будут иметь длину 1, но если я установил, например, вес B--E на 1 вместо 100, мы увидим, что этот метод работает, а от B до E кратчайший путь будет B-D-E.

Что касается вашего второго вопроса, здесь не совсем понятно, чего вы хотите достичь, особенно, как вы получаете эти кластеры? Если вы хотите найти сообщества, т. Е. Более тесно связанную группу вершин, принимая во внимание также веса ребер, для этого существует множество методов, все имена которых называются cluster_[...] или community.[...] в igraph. Например, если мы запустим fastgreedy метод на вашем графике, он обнаружит кластер, вы упомянули:

fg <- fastgreedy.community(ig, weights = E(ig)$weight) 

IGRAPH clustering fast greedy, groups: 2, mod: 0.059 
+ groups: 
$`1` 
[1] "A" "C" "F" 
$`2` 
[1] "B" "D" "E" 

Итак, мы имеем B, D, E кластер, что связано с более высокими краями веса. Если мы запускаем один и тот же метод без весов, все вершины будут принадлежать одной группе (fastgreedy.community(ig, weights = NULL)). Обратите внимание, что при обнаружении сообщества igraph понимает веса как strength,, поэтому вершины, связанные с более высокими границами веса, с большей вероятностью объединяются вместе, это выглядит как противоположное, как это работает при вычислении путей.