Визуализация динамических графов.

Время прочтения: 6 мин.

Графовая аналитика вошла в перечень трендов 2021 года по версии компании Gartner. Одной из интересных особенностей распространенного инструмента графового анализа, платформы Gephi, является возможность визуализации графов, изменяющихся во времени. Анализ динамики дает возможность получить более полное представление о свойствах и поведении исследуемой с помощью графа системы.

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

1. Представить всех студентов и все элементы учебного курса в виде вершин графа.

2. Изобразить факты обращения студентов к элементам курса в виде ребер, при этом толщина ребер должна быть пропорциональной количеству обращений за некоторый промежуток времени.

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

Этому графу соответствуют приведенные ниже списки вершин и ребер.

Теперь представим, что в силу некоторых причин связи между элементами исследуемой системы менялись в течение трех суток следующим образом:

Для построения такого графа в Gephi список ребер необходимо дополнить столбцом timeset,  в котором перечисляются периоды существования ребер.

Рассмотрим пример динамической визуализации с помощью Gephi по информации об обучении студентов Самарского университета на курсе «Анализ данных» в 2019-2020 учебном году. Курс реализуется в системе электронного обучения университета, построенной на платформе Moodle и включает следующие элементы учебного процесса: две самостоятельные работы, девять лабораторных работ и два теста. Все действия пользователей в системе электронного обучения фиксируются и могут быть выгружены в виде лог-файлов. Лог-файл активности студентов содержит несколько полей, из которых для решения нашей задачи будут использоваться три: временная отметка datetime, имя студента student и элемент курса task. Каждая запись в лог-файле соответствует одному обращению студента к какому-либо элементу учебного курса. Отметим, что данные из лог-файла частично обфусцированы: реальные имена случайным образом заменены вымышленными. Фрагмент лог-файла приведен ниже.

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

1. Подготовить данные: трансформировать исходный лог-файл в список вершин и ребер.
2. Импортировать списки вершин и ребер в Gephi.
3. Выполнить настройку визуализации.

Выполним трансформацию лог-файла в списки вершин и ребер помощью скрипта на Python. Импортируем библиотеку pandas и загружаем данные из исходного лог-файла учебного курса.

import pandas as pd
df = pd.read_csv('course_activity_log.csv')

Подсчитываем количество обращений студентов к элементам курса в течение суток.

df['datetime'] = df['datetime'].str.slice(0,10)
df.rename(columns={'datetime': 'date'}, inplace=True)
df_group = df.groupby(['date', 'student', 'task']).size().reset_index().rename(columns={0: 'number'})

Формируем список вершин графа. Поскольку у нас есть два принципиально разных вида вершин — студенты и элементы учебного курса, создаем дополнительный атрибут node_type, принимающий соответственно значения student и task. Результат сохраняем в файл сourse_activity_nodes.csv.

nodes = []
students = df_group['student'].unique().tolist()
nodes.extend([(student, 'student') for student in students])
tasks = df['task'].unique().tolist()
nodes.extend([(task, 'task') for task in tasks])
df_nodes = pd.DataFrame(nodes, columns=['id', 'node_type'])
df_nodes.to_csv('course_activity_nodes.csv', index=False)

Фрагмент списка вершин приведен ниже.

Формируем список ребер, при этом для каждого ребра определяем моменты времени, в которые его нужно отображать. Как и в ранее приведенном примере, периоды времени сохраняются столбце timeset. Также создаем столбец weight, в который записываются веса ребер графа в соответствующие периоды времени. Результат сохраняем в файл course_activity_edges.csv.

df_edges = df_group[['student', 'task']].drop_duplicates()
timestamps = []
weights = []
for _, edge in df_edges.iterrows():
    df_selection = df_group[(df_group['student'] == edge['student']) & (df_group['task'] == edge['task'])][['date', 'number']]
    data = df_selection.values.tolist()
    str_timestamps = '<[' + ', '.join([rec[0] for rec in data]) + ']>'
    str_weights = '<' + '; '.join(['[' + rec[0] + ', ' + str(rec[1]) + ']' for rec in data]) + '>'
    timestamps.append(str_timestamps)
    weights.append(str_weights)
df_edges['timeset'] = timestamps
df_edges['weight'] = weights
df_edges.rename(columns={'student':'source', 'task':'target'}, inplace=True)
df_edges.reset_index(drop=True, inplace=True)
df_edges.index.name = 'id'
df_edges.to_csv('course_activity_edges.csv')

Фрагмент списка вершин приведен ниже.

На этом подготовка данных завершена, и можно переходить к импорту данных в Gephi.

Для импорта списка вершин и ребер выбираем пункт Import spreadsheet из меню File, указываем файлы course_activity_nodes.csv и course_activity_edges.csv.

Далее в настройках импорта выбираем значение TimestampSet для поля timeset, значение TimestampIntegerMap для поля weight.

На последнем шаге импорта необходимо выбрать пункт Merge into new workspace.

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

Переходим к настройкам динамической визуализации графа. Для активации динамической визуализации нажимаем кнопку Enable Timeline в нижней части окна, в результате чего появляется шкала времени. Далее с помощью кнопки, расположенной в левой нижней части окна открываем меню с настройками воспроизведения, выбираем пункт Set time format,  затем в открывшемся окне выбираем вариант Date. После этих действий на шкале времени в нижней части окна появляются подписи месяцев с сентября по январь. Настраиваем ширину ползунка, и, нажав кнопку Play, получаем анимацию графа.

Все использованные в статье материалы приведены в репозитории github.com/mporuchikov/dynamic_graph_visualization.