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

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

Представим, что мы рассматриваем некий процесс. Например, он содержит в себе информацию о переходах заявки между рабочими группами. Для обеспечения отказоустойчивости процесса, нам необходимо понимать, какие из рабочих групп подвержены наибольшей нагрузке. Этот автоинсайт можно получить при использовании метрик ранжирования ребер в графе, например, betweenes centrality. Основная идея в том, что мы задаем важность вершины, основываясь на частоте прохождения через нее.

Данная метрика реализована в библиотеке языка python networkx. Давайте визуализируем данные и получим автоинсайт о степени важности вершин. Для примера я буду использовать данные из открытого набора о персонажах к\ф «Звездные войны». В нем содержатся номера эпизодов и персонажи-участники сцены.

Сначала импортируем необходимые библиотеки, загружаем данные и преобразуем их в графовое представление.

import json
import requests
from networkx.readwrite import json_graph
import networkx as nx
from collections import Counter
import numpy as np
from networkx.algorithms import community
data = json.loads(requests.get('https://raw.githubusercontent.com/evelinag/StarWars-social-network/master/networks/starwars-full-interactions.json').content)
Graph = json_graph.node_link_graph(data)

Используем нашу метрику для выделения наиболее важных вершин.

b_c = nx.betweenness_centrality(Graph)
b_c_counts = Counter(b_c)

Отрисовываем граф связности с использованием полученных при подсчете с помощью betweenness centrality данных.

threshold = b_c_counts.most_common(20)[-1][1]
nx.draw_random(
    Graph, 
    node_color=clrs, 
    with_labels=True, 
    alpha=0.7, 
    labels={n[0]: n[1]['name'] for n in Graph.nodes.data() if b_c[n[0]] > threshold}, 
    node_size=np.array(b_c.values()) * 100000,
    linewidths=0.1,
)


 

Полученный при визуализации наиболее значимых героев результат меня удивил, среди самых важных персонажей оказался робот C-3PO! А я всегда думала, что он просто один из второстепенных персонажей. Вот такой инсайт удалось мне извлечь при использовании метрики важности вершины betweenes centrality.