Граф музыкальных коллабораций.

В качестве источника дыннх мною был выбран сервис Яндекс.Музыка, которые предоставляет доступ к большому числу исполнителей и их трекам.

Граф формируется следующим образом:

Вершины -- уникальные исполнители
У вершин есть аттрибуты: название жанров в которых, согласно сервису выступает артист.
Ребро соеденияет две вершины, если у артистов есть совместная композиция
Колличество совместных композиций -- вес ребра

Сбор данных

Я ограничил круг собираемых данных только артистами, представленными в жанре "Иностранный рэп и хип-хоп". (https://music.yandex.ru/genre/иностранный%20рэп%20и%20хип-хоп/artists). Алгоритм сбора данных:

Для каждого исполнителя в списке открывалась страница его альбомов (напрмиер https://music.yandex.ru/artist/611169/albums)
а) Если на странице альбомов исполнителя представлен сингл, то сразу смотрится кто исполнители.

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

Сбор данных происходит при помощи библиотеки Scrapy.

Код паука в папке './yandexmusic/yandexmusic/spiders/spider.py'.

После данные с помощью библиотеки py2neo и отправляются в граф Neo4j ('./yandexmusic/yandexmusic/pipelines.py').

Чтобы уменьшить размер данных, из графа убираются артисты, которые имеют совместные композиции только с одним другим музыкантом. С помощью запроса в Neo4j MATCH (a) where size((a)-[]-())=1 MATCH (a)-[f]-(b) DELETE f, a

Итоги сбора данных:

Число исполнителей	Число связей	Число жанров
4255	17466	47

1	2

3	4

Алгоритм визуализации.

В качестве алгоритма для визуализации графа я выбрал Fruchterman-Reingold. Его основная идея состоит в предположении, что на любую вершину воздействуют две силы: сила притяжения - пртиягивающая соседние вершины и сила отталкивания, которая рассеивает все вершины. То есть во время работы алгоритм пытается минимизировать расстояния между соседними вершинами и максимизировать расстояние вершинами не соедененными ребром.

Алгоритм (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.8444&rep=rep1&type=pdf): Я добавил несколько изменений к описанному выше алгоритму:

W = L = 1.
После каждого подсчета |/delta| пришлось сравнивать его с 0, так как инчае часто происходило деление на ноль.
Начальныое значение температуры равно 0.1 * W
Убрал два последних ограничения на выход за границы поля (Просто стало выглядеть красивее, часть точек больше не примыкает к краям изображения).

Результаты на стандартных графах:

Karate club

Моя реализация	Networkx

Wheel graph

Моя реализация	Networkx

Hierarchically constructed Dorogovtsev-Goltsev-Mendes graph

Моя реализация	Networkx

Единственный явный недостаток алгоритма - скорость работы. На небольших данных (< 100 вершин) он хорошо справляется, однако в исходной задаче более 4000 вершин. Поэтому для конкретной задачи я немного модернизировал алгоритм.

Новый алгоритм выглядит слежующим образом:

Граф разбивается на сообщества
Избалвяемся от слишком маленьких (< 100 вершин), объеденяя их в одно
К каждому подграфу состоящему из элементов входящих в одно сообщество применяется исходный алгоритм. Это делается в несколько потоков, поэтому времени тратиться в k раз меньше.
С помощью исходного алгоритма строится layout для полного графа на N вершинах, где N = кол-во выявленных на 2 шаге сообществ. Таким образом получая координаты, которые можно исполььзовать для пропорциональной рисовки финального графа.
Координаты каждой точки из i-го сообщества сдвигаются на 10*(координаты i-й вершины в полном графе).

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