Сортировка строк и столбцов матрицы смежности для выявления кликов

Question

Я ищу метод переупорядочения, чтобы объединить связанные компоненты матрицы смежности.

Например, я сделал иллюстрацию с двумя группами, синими и зелеными. Первоначально записи «1» распределяются по строкам и столбцам матрицы. Переупорядочивая строки и столбцы, все «1» могут быть расположены в двух смежных срезах матрицы, более четко отображая синие и зеленые компоненты.

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

Ближайшие хиты, которые я нашел в

1. symrcm перемещает элементы ближе к диагонали, но не делает групп.

2. Is there a way to reorder the rows and columns of matrix to create a dense corner, in R?, которая фокусируется на удалении полностью пустые строки и столбцы

Пожалуйста, либо обеспечить общее название для этой техники, так что я могу Google более эффективно, или мне точку в направлении функции Matlab.

Answer 1

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

Ваш вклад:

>> A 

A = 

0  1  1  0  1 
1  0  0  1  0 
0  1  1  0  1 
1  0  0  1  0 
0  1  1  0  1 

Метод 1

Принимая первую строку и первый столбец, как колонного Mask (maskCol) и Row-Mask (maskRow) соответственно.

Получить маску из которых значений содержит те в обоих первом ряду, и первый столбец

maskRow = A(:,1)==1; 
maskCol = A(1,:)~=1; 

переставить строки (в соответствии с Роу-маской)

out = [A(maskRow,:);A(~maskRow,:)]; 

Дает примерно следующее:

out = 

1  0  0  1  0 
1  0  0  1  0 
0  1  1  0  1 
0  1  1  0  1 
0  1  1  0  1 

Перестановка столбцы (в соответствии с колонной маской)

out = [out(:,maskCol),out(:,~maskCol)] 

дают желаемые результаты:

out = 

1  1  0  0  0 
1  1  0  0  0 
0  0  1  1  1 
0  0  1  1  1 
0  0  1  1  1 

---

Просто проверить, являются ли индексы, где они должны быть или если вы хотите соответствующие переупорядоченные индексы;)

Перед перестановке:

idx = reshape(1:25,5,[]) 

idx = 

1  6 11 16 21 
2  7 12 17 22 
3  8 13 18 23 
4  9 14 19 24 
5 10 15 20 25 

После повторной организации (тот же процесс, который мы делали раньше)

outidx = [idx(maskRow,:);idx(~maskRow,:)]; 
outidx = [outidx(:,maskCol),outidx(:,~maskCol)] 

Выход:

outidx = 

2 17  7 12 22 
4 19  9 14 24 
1 16  6 11 21 
3 18  8 13 23 
5 20 10 15 25 

---

Метод 2

Для Generic случае, если вы заранее не знаете матрицу, здесь процедура, чтобы найти логику maskRow и maskCol

используется:

1. Возьмите первый ряд. Рассмотрим его как маску столбца (maskCol).

2. Для второй строки до последней строки повторяется следующий процесс.

3. Сравните текущую строку с maskCol.

4. Если какое-либо одно значение совпадает с maskCol, а затем найти элемент мудрых логических ИЛИ и обновлять его как новый maskCol

5. Повторите этот процесс до последней строки.

6. Тот же процесс для нахождения maskRow, в то время как столбец используется вместо итераций.

Код:

%// If you have a square matrix, you can combine both these loops into a single loop. 
maskCol = A(1,:); 
for ii = 2:size(A,1) 
    if sum(A(ii,:) & maskCol)>0 
     maskCol = maskCol | A(ii,:); 
    end 
end 

maskCol = ~maskCol; 

maskRow = A(:,1); 
for ii = 2:size(A,2) 
    if sum(A(:,ii) & maskRow)>0 
     maskRow = maskRow | A(:,ii); 
    end 
end 

Вот пример, чтобы попробовать, что:

%// Here I removed some 'ones' from first, last rows and columns. 
%// Compare it with the original example. 
A = [0  0  1  0  1 
    0  0  0  1  0 
    0  1  1  0  0 
    1  0  0  1  0 
    0  1  0  0  1]; 

Затем повторите процедуру, а затем перед:

out = [A(maskRow,:);A(~maskRow,:)];  %// same code used 
out = [out(:,maskCol),out(:,~maskCol)]; %// same code used 

Вот результат:

>> out 

out = 

0  1  0  0  0 
1  1  0  0  0 
0  0  0  1  1 
0  0  1  1  0 
0  0  1  0  1 

Примечание: Этот подход может работать в большинстве случаев, но все еще может потерпеть неудачу в некоторых редких случаях.

Здесь пример:

%// this works well. 
A = [0  0  1  0  1 0 
    1  0  0  1  0 0 
    0  1  0  0  0 1 
    1  0  0  1  0 0 
    0  0  1  0  1 0 
    0  1  0  0  1 1]; 

%// This may not 
%// Second col, last row changed to zero from one 
A = [0  0  1  0  1 0 
    1  0  0  1  0 0 
    0  1  0  0  0 1 
    1  0  0  1  0 0 
    0  0  1  0  1 0 
    0  0  0  0  1 1]; 

Почему не получится?

Как Переберите каждую строку (чтобы найти маску столбца), в течение, например, когда мы переходим к 3-й ряду, ни один из перевалов не соответствует первой строке (текущего maskCol). Таким образом, теряется единственная информация, переносимая третьей строкой (2-й элемент).

Это может быть редкий случай, поскольку некоторые другие строки могут содержать одну и ту же информацию. См. Первый пример. Также ни один из элементов третьей строки не совпадает с первой строкой, но поскольку последняя строка имеет одинаковую информацию (1 на 2-м элементе), она дала правильные результаты. Только в редких случаях подобное может произойти. Тем не менее, хорошо знать этот недостаток.

Метод 3

Это одна перебором альтернатива. Может применяться, если вы считаете, что предыдущий случай может завершиться неудачей. Здесь мы используем while loop для запуска предыдущего кода (поиск строки и кол-маски) количество раз с обновленным maskCol, чтобы он нашел правильную маску.

Процедура:

maskCol = A(1,:); 
count = 1; 
while(count<3) 
    for ii = 2:size(A,1) 
     if sum(A(ii,:) & maskCol)>0 
      maskCol = maskCol | A(ii,:); 
     end 
    end 
    count = count+1; 
end 

Предыдущий пример взят (где предыдущий метод не) и запускается с и без while-loop

без грубой силы:

>> out 

out = 

1  0  1  0  0  0 
1  0  1  0  0  0 
0  0  0  1  1  0 
0  1  0  0  0  1 
0  0  0  1  1  0 
0  0  0  0  1  1 

С Грубым незначащими во время цикла:

>> out 

out = 

1  1  0  0  0  0 
1  1  0  0  0  0 
0  0  0  1  1  0 
0  0  1  0  0  1 
0  0  0  1  1  0 
0  0  0  0  1  1 

Числа итераций, необходимых для получения правильных результатов могут отличаться. Но безопасно иметь хорошее число.

Удачи!