Почему матрица Лапласа не симметрична? - PullRequest
Новая
       43

Почему матрица Лапласа не симметрична?

1 голос
/ 13 апреля 2019

Я наткнулся на почему-матрица лапласиана-нужна-нормализация-и-как-то-получилось-матрица степени .

У меня есть взвешенная матрица смежности adjm (файл data.csv на Google Диске).Матрица adjm является несимметричной.Я построил ориентированный граф graph, а затем удалил петли и несколько ребер.Приведенный график связен и прост.Я использовал функцию graph.laplacian() из пакета igraph.Я ожидал получить симметричную матрицу, но матрица L_matrix не является симметричной. 

library(igraph)

# read from file    
adjm = as.matrix(read.csv("data.csv", sep=",", row.names = 1))

isSymmetric(adjm) # FALSE

graph <- graph_from_adjacency_matrix(adjm, weighted=TRUE)

table(count_multiple(graph))

# remove loops and multiple edges
graph <- simplify(graph) 

is_connected(graph) # TRUE

L_matrix <- graph.laplacian(graph, norm=TRUE, 
                            weights = E(graph)$weight, 
                            sparse=FALSE)

isSymmetric(L_matrix) # FALSE

Редактировать. Я пытался изменить допуск tol от 0,1 до 0,0001, норезультат - FALSE. 

isSymmetric(L_matrix, tol = 0.01) # FALSE

* L_matrix - квадрат 104 на 104 матрице.Я нашел разницу между первым рядом и первым столбцом.Затем я подсчитал количество нулей, оно меньше 104. 

test0 <- L_matrix[1,] - L_matrix[,1]
test0 <- test0[test0 == 0]
length(test0[test0 == 0])
[1] 90

Редактировать 2.

Я хочу сделать спектральную кластеризацию.

Вопрос. Почему матрица Лапласа не симметрична?

1 Ответ

1 голос
/ 14 апреля 2019

"Полученный граф связен и прост" не прав: граф все еще направлен, а матрица смежности не симметрична.Например, 

as_adjacency_matrix(graph)[1:5, 1:5]
# 5 x 5 sparse Matrix of class "dgCMatrix"
#      dddd dddD ddDd ddDD dDdd
# dddd    .    .    .    .    .
# dddD    .    .    .    .    .
# ddDd    .    .    .    .    .
# ddDD    .    .    .    .    .
# dDdd    .    1    .    .    .

Таким образом, в результате лапласиан также не будет симметричным.

Редактировать: , чтобы сделать график ненаправленным, мы можем использовать 

adjm <- pmax(adjm, t(adjm))
all(adjm == t(adjm))
# [1] TRUE

Таким образом, оба элемента (i, j) и (j, i) заменяются на большее из двух.Интересно, что это все равно не делает симметрию Лапласа симметричной: 

L_matrix[1:5, 1:5]
#      dddd        dddD ddDd ddDD       dDdd
# dddd    1  0.00000000    0    0  0.0000000
# dddD    0  1.00000000    0    0 -0.0703125
# ddDd    0  0.00000000    1    0  0.0000000
# ddDD    0  0.00000000    0    1  0.0000000
# dDdd    0 -0.06575342    0    0  1.0000000

Проблема заключается в том, как работает normalized = TRUE (похоже, ошибка; по крайней мере, это противоречит документации).Делая шаг нормализации вручную, мы имеем 

L_matrix <- graph.laplacian(graph, norm = FALSE, 
                            weights = E(graph)$weight,
                            sparse = FALSE)
L_matrix <- diag(1 / sqrt(diag(L_matrix))) %*% L_matrix %*% diag(1 / sqrt(diag(L_matrix)))
isSymmetric(L_matrix)
# [1] TRUE
L_matrix[1:5, 1:5]
#      [,1]        [,2] [,3] [,4]        [,5]
# [1,]    1  0.00000000    0    0  0.00000000
# [2,]    0  1.00000000    0    0 -0.06799476
# [3,]    0  0.00000000    1    0  0.00000000
# [4,]    0  0.00000000    0    1  0.00000000
# [5,]    0 -0.06799476    0    0  1.00000000
...