Сортировка строк и столбцов матрицы смежности для выявления кликов
Я ищу способ переупорядочения для группировки связанных компонентов матрицы смежности вместе.
Например, я сделал иллюстрацию с двумя группами, синим и зеленым. Первоначально записи "1" распределяются по строкам и столбцам матрицы. Переупорядочив строки и столбцы, все "1" могут быть расположены в двух смежных частях матрицы, более четко раскрывая синие и зеленые компоненты.
Я не могу вспомнить, как называется этот метод переупорядочения. Я искал много комбинаций матрицы смежности, клика, сортировки и переупорядочения.
Самые близкие хиты, которые я нашел, являются
symrcmперемещает элементы ближе к диагонали, но не делает группы.Есть ли способ изменить порядок строк и столбцов матрицы, чтобы создать плотный угол, в R? которая направлена на удаление полностью пустых строк и столбцов
Пожалуйста, укажите общее название для этого метода, чтобы я мог более эффективно использовать Google, или укажите мне направление в функцию Matlab.
2 ответа
Я не знаю, есть ли лучшая альтернатива, которая должна дать вам прямые результаты, но вот один из подходов, который может служить вашей цели.
Ваш вклад:
>> 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
Принимая первый ряд и первый столбец как маску столбца (
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
Для общего случая, если вы не знаете матрицу заранее, вот процедура, чтобы найти maskRow а также maskCol
Используемая логика:
Возьми первый ряд. Считайте это маской столбца (
maskCol).Для 2-й строки до последней строки, следующий процесс повторяется.
Сравните текущую строку с
maskCol,Если какое-либо одно значение совпадает с
maskCol, затем найдите элемент логического ИЛИ и обновите его как новыйmaskColПовторите этот процесс до последнего ряда.
Тот же процесс поиска
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). Таким образом, единственная информация, переносимая 3-й строкой (2-й элемент), теряется.Это может быть редким случаем, потому что некоторые другие строки могут по-прежнему содержать ту же информацию. Смотрите первый пример. Там также нет ни одного из элементов третьей строки, совпадающих с 1-й строкой, но, поскольку последняя строка имеет ту же информацию (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
С помощью цикла Brute-Forceing:
>> 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
Количество итераций, необходимых для получения правильных результатов, может варьироваться. Но иметь хороший номер безопасно.
Удачи!
Есть статья, которая близко подходит к вопросу:Behrisch et al. 2016 г.
(Я знаю, что такие типы ответов обычно не приветствуются в SO. Но я предполагаю, что эта статья дает отправную точку для вопроса, на который есть несколько возможных ответов. Возможно, я позже добавлю какой-нибудь код.)
РЕДАКТИРОВАТЬ: Связанный вопрос о scicomp