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

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

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

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

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

2. а) Если на странице альбомов исполнителя представлен сингл, то сразу смотрится кто исполнители.

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

Сбор данных происходит при помощи библиотеки 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

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

1	2
3	4

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

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

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

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

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

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

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

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

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

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

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

Алгоритм в файле visualization.py