Анализ процессов, Графы

Применение алгоритма Косарайю для поиска компонент сильной связности в графах денежных транзакций

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

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

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

Немного теоретических тезисов:

Две вершины ориентированного графа называют сильно связанными, если есть путь из первой вершины во вторую и обратно.

Ориентированный граф можно назвать сильно связным, если каждая пара его вершин является сильно связной.

Так что же такое эта «компонента сильной связности» в графах, которые мы будем исследовать?  Наиболее простой ответ на данный вопрос – «Это сильно связный подграф».

Для поиска компонент сильной связности будем использовать алгоритм Косарайю. Построим тестовый граф, как показано на рисунке:

Для построения графа воспользуемся возможностями библиотек netwotkx и matplotlib, запустив следующий код:

import networkx as nx
import matplotlib.pyplot as plt
%config InlineBackend.figure_format = 'svg'
plt.rcParams['figure.figsize'] = (10,6)
G = nx.DiGraph()
G.add_nodes_from(['1','2','3','4','5','6','7','8','9','10','11','12'])
G.add_edges_from([
    ('1','2'),('2','1'),('3','1'),('3','4'),
    ('4','3'),('4','5'),('4','11'),('5','2'),
    ('5','6'),('5','7'),('6','8'),('7','9'),
    ('8','6'),('9','10'),('9','4'),('10','9'),
    ('10','12'),('12','11')
])
nx.draw(G, with_labels=True, font_weight='bold')

Для полученного графа поиск компонент сильной связности по алгоритму Косарайю будет состоять из трёх шагов:

  1. Выполнить поиск в глубину, пока не будут «помечены» все вершины.
  2. Инвертировать исходный граф (сменить направление всех ребер в графе на противоположные).
  3. Выполнить поиск в глубину в порядке убывания пометок вершин.

Непосредственно код, выполняющий данные шаги:

# Считывание списка смежности вершин из текстового файла

def graph_to_vocab(adress):
    graphs = {}
    with open(adress) as file:
        lines = file.readlines()
        for line in lines:
            line = line[:-1].split(' ')
            graphs[line[0]] = line[1:]
    return graphs
# Поиск пути из одной вершины в другую
def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath:
                    return newpath
        return None
def connect(x1,x2):
    return True if x1 != None and x2 != None else False

# Поиск компонент сильной связности

def Kosarai(graph_file):
    abc = graph_to_vocab(graph_file)
    graphs_list = []
    for i in range(1,len(abc)+1):
        res_graph = []
        for j in range(1,len(abc)+1):
            graph1 = find_path(abc, str(i), str(j))
            graph2 = find_path(abc, str(j), str(i))
            if connect(graph1, graph2):
                if i!=j:
                    res_graph = graph1
        if len(res_graph)>2:
            graphs_list.append(res_graph)
    return graphs_list
if __name__=="__main__":
    print(Kosarai('graph.txt'))

Результат работы данного алгоритма для тестового графа:

Найдем наиболее полные и уникальные списки смежности точек, по которым производятся переводы и отметим их в таблице:

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

Советуем почитать