Найти соседей соседей в графе, используя MATLAB

Question

У меня есть матрица A, которая представляет собой отношение окрестности.

A=[1 2 
    1 4 
    2 6 
    4 5 
    6 7 
    6 8] 

Строки A сортируется, а это означает [1 2] и [2 1] рассматриваются как же отношения соседства и ряды A сортируются в порядке возрастания лексикографического порядка.

В нашем примере матрицы, узел 1 является соседом узла 2 и 4 узел 2 является соседом 6, узел 4 является соседом 5, и так далее. Я хочу вычислить матрицу B, которая представляет отношение соседей соседа (NON). Два узла NON друг от друга, если оба они имеют некоторый узел, они оба являются соседями. Это означает, что 1 является NON из 5 (через 4) и 6 (через 2) и т.д.

B=[1 5 
    1 6 
    2 4 
    2 7 
    2 8 
    7 8] 

Как я могу вычислить матрицу B?

Answer 1

Назовем ваш график G. Вы можете вычислить соседей по соседству с G, используя graph powerG^k для k=2, который представляет собой график, который имеет те же узлы, но в котором две вершины смежны, когда их расстояние в G не превышает k.

Вы можете прочитать подробную информацию о статье википедии, но самая важная часть:

Если A является матрица смежности для графа, модифицирован, чтобы иметь отличные от нуля записи на главной диагонали, то ненулевые записи A^k дают матрицу смежности k-й степени графика.

(Для нашего случая k=2 мы не будем нуждаться ненулевые элементы на диагонали, так как нам необходимы расстояние ровно два, а не расстояние меньше или равно два, что установка по диагонали к ненулевым элементам для.)

Таким образом, вы просто построить свою матрицу смежности A по:

edges = A; 
n = max(edges(:)); 
A = sparse(edges(:,1),edges(:,2),1,n,n) + ... 
    sparse(edges(:,2),edges(:,1),1,n,n); % Make graph undirected via symmetry. 

Вам будет генерировать матрицу смежности G^2 через A*A или A^2, который затем использовать find дальше, чтобы получить края:

[I,J] = find(A^2); % Edges of A^2 

Вы можете построить B, удаляя элементы, которые вы не хотите там (как оригинальные соединения или само-соединений)

B = setdiff(sort([I,J],2), [edges; [(1:n).',(1:n).'], 'rows')