Как Связать Несвязанное

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

Если вы присмотритесь, то увидите, что таких связей вокруг нас очень много.

Сотрудники и проекты.

Связь сотрудника с проектом отражает степень его вовлеченности в проект. Разные сотрудники могут быть связаны с разными проектами (да, многие-ко-многим).

Исходя из того, кто в каких проектах участвует, можно определить объем общения между сотрудниками.

Очевидно, что сотрудники, участвующие в одних и тех же проектах, должны быть более тесно связаны.

Посты и комментарии.

В социальных сетях люди пишут посты и комментируют их.

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

Товары в накладных.

Определить близость товаров можно на основании их включения в одну накладную (или квитанцию).

Чем чаще продукты встречаются вместе, тем ближе они друг к другу.

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

Слова и документы.

Чем больше одинаковых слов в двух документах, тем ближе эти документы.

Работает и наоборот — чем чаще два слова встречаются в одном документе, тем они ближе.

Буквы и слова.

Чем чаще буквы встречаются в одном слове, тем более связаны эти буквы.

Люди и фотографии.

Чем чаще люди встречаются на общей фотографии, тем они ближе.

Думаю, примеров достаточно.

Все примеры содержат элементы двух наборов разных типов.

В этом случае элементы каждого множества можно считать независимыми (несвязанными друг с другом).

Сотрудники явно не связаны с другими сотрудниками, документы явно не связаны с другими документами.

Это некоторое упрощение, но оно не критично.

Поскольку связи есть, то очевидно, что будут и графики.

И действительно, ввиду распространенности таких связей, образуемые ими графы имеют особое название – двудольный .

Две части графа представляют собой два независимых множества, связанных друг с другом.

Часто (но не обязательно) размер одной акции (набора) во много раз превышает размер другой.

Например, если количество сотрудников исчисляется десятками, то количество документов, в которых они отмечены, может исчисляться сотнями и тысячами.

В русском алфавите 33 буквы, но из них состоят тысячи слов.

Очевидно, что чем больше элементов в графе, тем сложнее его анализировать.

Поэтому возникает проблема «свертки связей» — необходимо преобразовать двудольный граф в однодольный (однородный), оставив только один набор элементов (обычно меньшей дроби).

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

Но как выполнить развал галстука? наиболее оправданно с математической точки зрения? Здесь нам нужно углубиться в метрические пространства.

Поэтому этот раздел отмечен звездочкой – он для любопытных.

Обычно графы преподаются в рамках дискретной математики, а понятие пространств — в линейной алгебре.

В результате в голове графики в одном месте, а пробелы в другом.

Требуется немного усилий, чтобы понять, что графы — это не только комбинаторика и алгоритмы.

Граф (здесь и далее для простоты будем считать, что графы связны и неориентированы) определяет метрическое пространство.

Вершины графа являются элементами базиса данного пространства.

Расстояния между элементами (наличие которых отличает метрические пространства от других) можно определить на основе связей вершин графа друг с другом.

На графике данные о расстоянии обычно называются резистивный .

Почему «резистивный».

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

Чем больше расстояние, тем больше сопротивление.

Это кажется логичным.

Математически резистивные расстояния соответствуют квадратам обычных (геометрических) расстояний.

Величины связей и резистивные расстояния взаимно обратны.

Вы можете определять расстояния по связям вершин или наоборот — величину связей между элементами по расстояниям между ними.

Вернемся к акциям.

В связном графе можно вычислить расстояния между любыми его вершинами.

А раз так, то можно выбрать из графа произвольное подмножество его вершин и найти такие связи между вершинами, которые обеспечивали бы такие же расстояния между ними, как и в исходном графе.

Математически это преобразование означает переход от пространства к подпространству с сохранением скалярного произведения на элементах подпространства.

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

Логика такова: Исходный двудольный граф -> (наборы) -> Расстояния между элементами разбиения -> (по которым можно рассчитать) -> Требуемый однодольный граф .

На самом деле, нет необходимости считать сами расстояния.

Вам просто нужно найти преобразование графа в подграф, при котором резистивные расстояния между элементами подграфа не изменяются.

Это классическая задача отображения пространства в подпространство.

Отметим, например, что известное Преобразование треугольник-звезда является частным (и упрощенным) случаем такого преобразования.

«Определить» в данном случае означает построить матрица смежности подграф на основе матрицы смежности исходного графа.

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

Поскольку внутри каждой доли нет связей, из всех блоков остаются только два взаимно симметричных — соединение элементов одной доли с элементами другой.

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

Вместо матриц лучше сразу использовать термин «тензоры» — это ближе к реляционным таблицам и базам данных, которые обычно содержат исходные данные.

Тензор двусмежности — это просто таблица с двумя измерениями (индексами) «Откуда», «Откуда» и одним ресурсом — «Вес связи».

Для графа на рисунке тензор двусмежности будет:



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

В конечном итоге все сводится к операциям реляционной алгебры.

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



(И



), и весь набор такой



.

Для элементов дополнительного множества (части) будем использовать символы



(И



).

Это могут быть документы, в которых сотрудники оставляют комментарии, или счета-фактуры, если мы ищем связи между товарами.

Тензор связей (матрица двусмежности) между множествами



считается данным.

Для каждого объекта (вершины графа) можно определить его степень.

Это количество соединений данного объекта.

Например, для документов степенью является количество ссылок на них (сколько всего комментариев или товаров); для слова — это его длина (количество букв).

Обозначим степени дополнительной дроби



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



:



Здесь



— свертка тензора по размерности



.

Ээквивалент матричного произведения



к кортежу из единиц



.

Учтем это, введя матрицу связей (смежности)



.

Если граф двудольный, то данные связи (и их матрица) равны нулю.

Искомая матрица результирующих связей между элементами множества (долей)



давайте обозначим это как



.

Тогда верно следующее утверждение (лемма): Величина результирующих связей между элементами множества



равен сумме исходных



и индуцировал



связи :



В этом случае матрица индуцированных связей имеет следующий квадратичный вид (это основная формула статьи):



Здесь



- фундаментальная матрица, которая определяется как обратная минорной матрице Матрица Лапласа :



Все приведенные выше формулы справедливы для любого (неориентированного) графа, двудольного или нет. Они следуют из формул обращения блочных матриц.

Хитрость двудольных графов заключается в том, что минор лапласиана



для доли графа — это диагональная матрица, составленная из степеней элементов



(поскольку связи между элементами отсутствуют).

Поэтому инверсия этого минора просто сводится к обратным значениям степеней



:



В результате вместо дорогостоящей процедуры обращения матрицы мы имеем дело с обычным делением.

Если речь идет о тысячах элементов, то этот нюанс имеет значение.

Собственно, именно ради того, чтобы подчеркнуть это, мы и написали эту статью.

Подставив обратные степени в (3), получим формулу преобразования матрицы двусмежности в матрицу смежности заданной доли:



Если тензор двусмежности задан в виде реляционной таблицы, то преобразование (6) можно выполнить одним SQL-запросом.

Ну, в таких библиотеках, как Python Pandas, это преобразование можно записать в одну строку действий над объектом фрейма данных.

Соответственно, диагональ фундаментальной матрицы будет равна обратной величине:



.

Подставив его в формулу (6), получим тензор индуцированных связей (для удобства приведем целые значения):



Вот и все.

В следующая статья Давайте рассмотрим, зачем все это нужно, и какую полезную информацию можно извлечь из полученного подграфа.

Приведена более подробная математика преобразования графового пространства в подпространство.

Здесь .