Сортировка данных таблиц / матриц по сообществам (Visual Role Mining)

Question

Я ищу способ сортировки двумерной двоичной матрицы, чтобы мы могли визуально идентифицировать «сообщества» в данных. Мой набор данных основан на членстве в группах (т.е. список людей и групп, к которым они принадлежат). Например:

   G1 G2 G3 G4
P1 1     1  
P2 1     1  
P3    1     1
P4    1     1

Я ищу алгоритм сортировки, который даст мне следующее:

   G1 G3 G2 G4
P1 1  1     
P2 1  1    
P3       1   1
P4       1   1

Еще один пример «отсортированных» данных можно найти здесь: http://mbostock.github.com/protovis/ex/matrix.html В этом примере создатели ссылаются на «алгоритм обнаружения сообщества», используемый для сортировки. Мои данные отличаются, поскольку между измерениями не будет членства (то есть первое измерение (люди) являются членами второго измерения (группы).

Я нашел статью, в которой это подробно обсуждается: http://ricerca.mat.uniroma3.it/users/colanton/docs/visual.pdf (предупреждение: PDF)

Итак, в итоге я беру данные о членстве, пытаюсь найти «сообщества» в данных и представляю их визуально.

Я нашел похожие обсуждения, которые могут быть здесь полезны: Сортировка бинарной 2D матрицы? Существуют ли реализации алгоритмов обнаружения сообщества в графах?

Answer 1

Лучшее решение, которое я видел до сих пор, здесь: http://matthewlincoln.net/2014/12/20/adjacency-matrix-plots-with-r-and-ggplot2.html

Подводя итог подхода:

Одной из хороших альтернатив является визуализация матрицы смежности, кодирующей данные сетевых отношений, где, например, ячейка AB описывает граничный соединительный узел A к узлу B. Майк Босток реализовал это в D3, используя совместно с Les Misérables Жака Бретена Набор сетевых вхождений. Также довольно просто сгенерировать визуализацию матрицы смежности с помощью ggplot2, но для этого нужно, чтобы вы откусили пулю и наконец выяснили, как работать с упорядоченными факторами.

Он может взять матричный график, который выглядит следующим образом:

и сортирует по этому: