Обработка графов

Граф в математике представляет собой коллекцию вершин (verteх) или узлов (node), соединённых друг с другом рёбрами (edge). Граф может быть направленным (directed graph) и ненаправленным (undirected graph) в зависимости от того, отношение связности действует в одну сторону или всегда в обе. Также граф может быть взвешенным (weighted graph), когда каждому ребру ставится в соответствие сила связи. Также ребрам можно ставить в соответствие и дискретные категории (тип связи) и вещественные признаки. Пример графа (источник):

Графы часто возникают на практике. Ниже приведены примеры данных, которые можно представить в виде графа:

• социальная сеть, где узлами выступают люди, а связи - добавил ли человек другого человека в друзья или писал ли ему сообщения;

• интернет, где узлами выступают веб-страницы, а связи отражают ссылки одних веб-страниц на другие;

• научные публикации, где узлами выступают статьи, а рёбра проводятся, если одна статья ссылается на другую;

• компьютерная сеть, где узлами выступают компьютеры и сетевые устройства, а ребра проводятся, если устройства соединены и посылают друг другу данные;

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

• вещества, где узлами выступают молекулы, а связями - их химические соединения (источник):

Решаются следующие задачи на графе:

Классификация графа. Например, по химическому соединению лекарства предсказать, будет ли оно обладать лечебным эффектом. Также можно решать и задачу регрессии, например, по виду химического соединения определить его температуру плавления.

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

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

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

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

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