Теория двудольных графов - найти попарное перекрытие (общее ребро) из двудольной матрицы смежности

У меня есть двудольный граф, хранящийся в матрице смежности A (100*1900), 100 строк, 1900 столбцов. Просто я обозначаю 100 строк, представляющих фактор А, и 1900 столбцов, представляющих фактор Б. График показывает связь между 100 факторами А и 1900 факторами В, поэтому это двудольный граф.

Таким образом, матрица имеет вид |factorA|*|factorB|, размерность матрицы 100*1900.

Мне нужно найти попарное перекрытие между factorB. Способ сделать это — получить A и транспонировать A, обозначить как Т(А).

Затем получите A' = T(A)*A, так что A' будет матрицей 100*100, тогда элементы A'[i, j] соответствует количеству factorB, общих для factorA i и factorA j.

Почему приведенный выше алгоритм работает? Можно привести любую справочную публикацию или математическое доказательство?


algorithm graph-theory graph-algorithm adjacency-matrix discrete-mathematics
person ToBeGeek    schedule 14.02.2014    source источник
comment
Можете подробнее описать, чем вы занимаетесь? Прямо сейчас я понятия не имею, что такое T(A), как вы его вычислили, почему вы пытались это сделать или даже что значит работать. Это кажется интересной проблемой, но без более подробной информации я не думаю, что вы сможете получить хорошие ответы.   -  person templatetypedef    schedule 15.02.2014
comment
Кроме того, матрицы смежности обычно квадратные. Вы имеете в виду матрицу инцидентности вершины-ребра? Или это матрица смежности двудольного графа?   -  person Timothy Shields    schedule 15.02.2014
comment
Транспонирование матрицы смежности. Вы знаете транспонирование матрицы?   -  person ToBeGeek    schedule 15.02.2014
comment
@TimothyShields Да, я имею в виду двудольный граф. Края находятся между 100 факторами А и 1900 факторами В.   -  person ToBeGeek    schedule 15.02.2014
comment
@TimothyShields Я просто хочу знать, почему это работает, ссылка или математическое доказательство были бы очень полезны.   -  person ToBeGeek    schedule 15.02.2014

Ответы (1)


arrow_upward
0
arrow_downward

Пусть A' = A * транспонировать (A).

A'[i,j] является скалярным произведением i-й строки A и j-й строки A. Предположим, что эти две строки выглядят следующим образом:

строка(A,i) = [0, 0, 1, 0, 1, 1, 0, 1]
строка(A,j) = [1, 0, 1, 1, 0, 1, 1, 0 ]

Поэлементное произведение этих двух

строка(A,i).* строка(A,j) = [0, 0, 1, 0, 0, 1, 0, 0]

Внутренний продукт двух строк представляет собой сумму этих значений, 2. Это интуитивное объяснение того, почему A'[i,j] является количеством общих соединений между строками i и строками j.

Если вы посмотрите на транспонирование (A) * A, вы также сможете найти общие связи между столбцами.

person Timothy Shields    schedule 14.02.2014
comment
Итак, T(A)*A действительно дает A', где A'[i,j] означает фактор B, общий для factorA i и j? не могли бы вы дать доказательство или ссылку в ссылке? - person ToBeGeek; 15.02.2014
comment
@ToBeGeek В основном это было доказательством. Как это не достаточно? У меня нет для вас справки или ссылки - это действительно очень простая линейная алгебра. - person Timothy Shields; 15.02.2014
comment
А должно быть 100*100, верно? Я хотел бы иметь официальную письменную работу, если вы можете. @Тимоти Шилдс - person ToBeGeek; 15.02.2014
comment
@ToBeGeek A' = A * транспонировать (A). A равно 100 на 1900. Transpose(A) равно 1900 на 100. Следовательно, A' равно 100 на 100. -- Если у вас все еще возникают трудности, я думаю, вы, возможно, не в себе. Опять же, это простая линейная алгебра. en.wikipedia.org/wiki/Matrix_(mathematics)#Basic_operations - person Timothy Shields; 15.02.2014
comment
Большое спасибо, я подумаю о том, чтобы написать официально. @Тимоти Шилдс - person ToBeGeek; 15.02.2014
comment
@ToBeGeek Кстати, в Stack Overflow вы должны пометить ответ как решение, если вы решите, что это так. Решил, что скажу тебе, потому что ты здесь новенький. - person Timothy Shields; 15.02.2014