Комментарии 5
Что-то вы тут усложняете.
Так вы теряете связи между участниками, которые, например, никогда не ходили на одно и то же мероприятие, но зато всегда ходят с одними и теми же людьми. То есть очевидно, что между ними связь есть.
Поэтому связи считаются иначе. Участники уже связаны с мероприятиями. Эти связи образуют исходный граф. Его особенность в том, что он двудольный. Одна доля — участники, другая — мероприятия. В данном графе узлы одной доли между собой не связаны, что на руку.
На основании данного графа можно построить граф связанности для одной из долей. В статье вы строите граф для участников, но можно было бы посмотреть и на граф связанности мероприятий — они же тоже связаны между собой через участников.
Как построить граф связанности для узлов одной доли? Примерная схема такая.
Используется понятие (резистивных) расстояний. Исходный граф уже задал такие расстояния и при построении графа для доли мы требуем, чтобы все расстояния исходного графа (между участниками, если строим для них) сохранились. То есть мы ищем матрицу смежности для участников на основании матрицы резистивных расстояний между ними.
Слов много, но на деле — все сводится к одной матричной формуле (квадратичная форма). Используется обращение матрицы степеней (здесь — степени мероприятий). В двудольном графе данная матрица диагональна, поэтому ее обращение тривиально.
В полученной матрице смежности связи будут почти между всеми элементами, но можно отфильтровать шум, установив порог значимости для величины связи.
Как превратить данные о том, что участники 1, 2, 5 и 23 посетили одно мероприятие, в ребра? Необходимо создать шесть строк и отметить связь каждого участника с каждым: 1 и 2, 1 и 5, 1 и 23, 2 и 5, 2 и 23, 5 и 23
Так вы теряете связи между участниками, которые, например, никогда не ходили на одно и то же мероприятие, но зато всегда ходят с одними и теми же людьми. То есть очевидно, что между ними связь есть.
Поэтому связи считаются иначе. Участники уже связаны с мероприятиями. Эти связи образуют исходный граф. Его особенность в том, что он двудольный. Одна доля — участники, другая — мероприятия. В данном графе узлы одной доли между собой не связаны, что на руку.
На основании данного графа можно построить граф связанности для одной из долей. В статье вы строите граф для участников, но можно было бы посмотреть и на граф связанности мероприятий — они же тоже связаны между собой через участников.
Как построить граф связанности для узлов одной доли? Примерная схема такая.
Используется понятие (резистивных) расстояний. Исходный граф уже задал такие расстояния и при построении графа для доли мы требуем, чтобы все расстояния исходного графа (между участниками, если строим для них) сохранились. То есть мы ищем матрицу смежности для участников на основании матрицы резистивных расстояний между ними.
Слов много, но на деле — все сводится к одной матричной формуле (квадратичная форма). Используется обращение матрицы степеней (здесь — степени мероприятий). В двудольном графе данная матрица диагональна, поэтому ее обращение тривиально.
В полученной матрице смежности связи будут почти между всеми элементами, но можно отфильтровать шум, установив порог значимости для величины связи.
Дмитрий, спасибо за отличный комментарий и совет. Можете ли Вы подсказать далёким от математики читателям, как и на что необходимо «нажать», чтобы построить граф связанности для узлов одной доли (или двудольный граф)?
Я не до конца понял про резистивные расстояния (точнее кажется там граф получится уж слишком плотным, а подбор порога это дело не тривиальное в этом случае), но мы делали подобные задачи так. Из теории информации мы знаем, что более частые события менее информативны. Если сравнить два мероприятия, на одном было 1000 людей, на другом 100, то кажется совместное посещение двумя участниками первого мероприятия говорит нам меньше, чем совместное посещение второго. Это можно учесть, например так: мы строим не просто граф, а взвешенный граф: сначала мы строим лист ребер для каждой связи участник-мероприятие; затем мы каждую такую связь «нормируем» на количество участников мероприятия (т.е. делим на нее, а еще лучше на логарифм этого количества). Получили таблицу вида: participant_id, event_id, weight. Дальше мы выполняем проекцию биграфа на участников (умножаем матрицу смежности на себя транспонированную), а по простому делаем join таблицы саму на себя с условием event_id_left = event_id_right и participant_id_left > participant_id_right. Операция тяжелая, но необходимая. Дальше получили таблицу вида: participant_1_id, participant_2_id, weight_1, weight_2. Суммируем веса weight_1 и weight_2. Далее объединяем все связи participant_1, participant_2 в одну (группировкой), также суммируя веса. Все, мы получили лист рёбер взвешенного графа участник-участник.
В Gephi, который вы используете есть возможность учесть веса при построении (раздел edge weight в оригинальной статье про их Force Atlas 2).
Обычно еще потом хорошо «проредить» граф по некоторому порогу веса ребер.
В Gephi, который вы используете есть возможность учесть веса при построении (раздел edge weight в оригинальной статье про их Force Atlas 2).
Обычно еще потом хорошо «проредить» граф по некоторому порогу веса ребер.
Куда «нажать» не знаю ), но наверное можно запланировать статью о методике преобразования двудольных графов в «однодольные», если эта тема интересна.
Может кому будет полезно, если gephi не запускается с сообщением «Cannot find java 1.8 and higher» нужно:
1. установить свежую версию java java.com/ru/download
2. прописать путь в файле gephi.conf (C:\Program Files\Gephi-0.9.2\etc):
jdkhome=«C:/Program Files (x86)/Java/jre1.8.0_XXX» (вместо XXX ваш номер скачанного обновления Java.
1. установить свежую версию java java.com/ru/download
2. прописать путь в файле gephi.conf (C:\Program Files\Gephi-0.9.2\etc):
jdkhome=«C:/Program Files (x86)/Java/jre1.8.0_XXX» (вместо XXX ваш номер скачанного обновления Java.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Построение графов для чайников: пошаговый гайд