Недавно мы разбирали, чем внутренне устройство графовых баз данных отличается от реляционных. Поэтому именно графовые базы целесообразно использовать для анализа больших графовов. Однако, на малых датасетах вполне можно обойтись и Python-библиотекой Networkx, что мы и рассмотрим далее на примере анализа банковских транзакций.
Python-скрипт поиска сообществ в графе с библиотекой Networkx
В прошлый раз я показывала, как написать Python-приложение, которое генерирует граф знаний в графовой базе данных Neo4j, развернутой на облачной платформе Aura DB. В качестве примера рассматривался кейс анализа банковских транзакций. Сегодня решим аналогичную задачу встроенными методами Python-библиотеки Networkx, которая содержит множество графовых алгоритмов, от поиска путей до выявления сообществ. Некоторые из сценариев использования этих алгоритмов я разбирала здесь и здесь.
Предположим, необходимо выявить группы (сообщества) среди клиентов банка по сведениям о выполненных транзакциях. А также показать возможные пути передачи денег от одного клиента к другому по проведенным транзакциям. Для этого надо построить направленный граф и воспользоваться алгоритмами поиска сообществ и поиска путей.
Как обычно, я буду писать и запускать Python-код в интерактивной среде Google Colab. Сперва установим библиотеки и импортируем необходимые для работы модули:
####################################ячейка в Google Colab №1 - установка и импорт библиотек########################################### #установка библиотек !pip install Faker #импорт модулей import networkx as nx import matplotlib.pyplot as plt import pandas as pd import random from faker import Faker from faker.providers.address.ru_RU import Provider
Далее напишем скрипт создания графа и применения к нему аналитических операций.
####################################ячейка в Google Colab №2 - создание и анализ графа ###########################################
#Импорт и настройка генератора случайных данных Faker.
fake = Faker('ru_RU')
fake.add_provider(Provider)
#Генерация данных и создание датафрейма вершин.
# создаем пустой список для хранения сгенерированных данных
data1 = []
# генерируем данные и добавляем их в список
for i in range(20):
k=random.randint(0, 1)
if k==1 :
name = fake.company()
else :
name = fake.name()
bank_account = fake.checking_account()
data1.append((i, name, bank_account))
# создаем датафрейм вершин из списка данных
v = pd.DataFrame(data1, columns=['id', 'Client', 'Bank Account'])
print("\nКлиенты")
print(v)
# создаем пустой список для хранения сгенерированных данных
data2 = []
# генерируем данные и добавляем их в список
for i in range(40):
src = random.randint(0, 19)
dst = random.randint(0, 19)
summa = random.randint(0, 10000)
data2.append((src, dst, summa))
# создаем датафрейм связей из списка данных
e = pd.DataFrame(data2, columns=['src', 'dst', 'summa'])
print("\nТранзакции")
print(e)
# генерируем цвета для каждой точки
colors = [fake.color() for i in range(nx_g.number_of_nodes())]
# рисуем граф
pos = nx.spring_layout(nx_g)
nx.draw(nx_g, pos, with_labels=True, node_size=600, node_color=colors, font_size=6)
nx.draw_networkx_labels(nx_g, pos, label_dict, font_size=6)
# добавляем метки к ребрам графа
edge_labels = {(row['src'], row['dst']): row['summa'] for index, row in e.iterrows()}
nx.draw_networkx_edge_labels(nx_g, pos, edge_labels=edge_labels, font_size=6)
#вывод графа
plt.show()
# Находим сообщества в графе методом Girvan–Newman
communities_generator = nx.community.girvan_newman(nx_g)
top_level_communities = next(communities_generator)
next_level_communities = next(communities_generator)
# Выводим сообщества в алфавитном порядке
print("\nВ эом наборе клиентов найдены следующие сообщества:")
for next_level_community in next_level_communities:
print(next_level_community)
# Находим случайные вершины и пути между ними
src = random.randint(0, 19)
dst = random.randint(0, 19)
paths = list(nx.shortest_simple_paths(nx_g, src, dst))
# Выводим найденные пути
print("\nМежду клиентом", src, "и клиентом", dst, "найдены пути проведения денег:")
for path in paths:
print(path)
Результаты выполнения скрипта:
В этом скрипте для поиска сообществ использовался алгоритм Гирвана-Ньюмана (Girvan–Newman), применяемый для обнаружения и анализа структуры сообщества. Этот иерархический метод для обнаружения структур сообществ в сложных системах основан на итеративном исключении ребер, которые имеют наибольшее количество кратчайших путей между узлами, проходящими через них. Удаляя ребра из графа одно за другим, граф разбивается на более мелкие части, т.е. сообщества.
Идея алгоритма в том, чтобы найти, какие ребра графа чаще всего встречаются между парами узлов в зависимости от степени центральности ребер между ними. Ребра, соединяющие сообщества, будут иметь высокую степень посредничества. Степень посредничества вершин показывает высокую центральность узла графа и определяется как число кратчайших маршрутов между парами узлов, которые проходят через эту вершину. Алгоритм Гирвана-Ньюмана расширяет определение степени посредничества на случай рёбер, определяя степень посредничества рёбер как число кратчайших путей между парами узлов, которые проходят через это ребро. Суть алгоритм Гирвана-Ньюмена сводится к выполнению 4-х этапов:
- для каждого ребра в графе вычисляется степень посредничества;
- ребро с наивысшей степенью посредничества удаляется;
- для каждого оставшегося ребра повторно вычисляется степень посредничества;
- шаги 2-3 повторяются до тех пор, пока в графе не останется ни одного ребра.
Существует множество библиотек графовых алгоритмов с собственными реализациями алгоритма Гирвана-Ньюмана. Помимо Python-библиотеки NetworkX, есть и более быстрые реализации на языке C++, например, MAGE – библиотека графовых алгоритмов в графовой базе данных Memgraph, о которой мы писали здесь и здесь.
Узнайте больше про методы и средства работы с графами для эффективного применения в реальных проектах аналитики больших данных на специализированных курсах нашего лицензированного учебного центра обучения и повышения квалификации для разработчиков, менеджеров, архитекторов, инженеров, администраторов, Data Scientist’ов и аналитиков Big Data в Москве:
Источники
