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

Торопов Борис Андреевич кандидат технических наук доцент, Академия управления МВД России 125171, Россия, г. Москва, ул. З. и А. Космодемьянских, 8 Toropov Boris Andreevich PhD in Technical Science Associate Professor at the IT Department of the Academy of Management of the Ministry of Internal Affairs of the Russian Federation 125171, Russia, g. Moscow, ul. Z.i A. Kosmodem'yanskikh, 8 torbor@mail.ru Другие публикации этого автора

1. Введение

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

На современном этапе развития информационных систем и технологий такая деятельность сопряжена с формированием и обработкой крупномасштабных электронных таблиц на основе информационных массивов различных баз данных, содержащих сведения о лицах, транспорте, активности мобильных устройств связи, приобретенных и использованных проездных документах и т.п. При этом большой объем данных, подлежащих анализу, не позволяет анализировать их «в ручную» и требует применения автоматизированной обработки, а также новых технологических подходов к ее осуществлению. В свою очередь, автоматизация чего-бы то ни было, предполагает некоторый уровень формализации задач, подлежащих решению без вмешательства человека. И чем меньше предполагается вмешательство человека, тем соответственно выше достигается уровень автоматизации и тем полнее должна быть формализация.

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

2. Способы изображения графа и формальная постановка задачи выявления лица с наибольшим количеством связей

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

Граф ‒ это абстрактный математический объект G (V, E), который состоит из множества элементов, именуемых вершинами V и связей между этими элементами, именуемых ребрами E^[1].

На рис.1 приведем три различных представления, характеризующие один и тот же граф. Этот граф является нумерованным, поскольку его вершины имеют уникальные индексы V = {1, …, 5}.

		1 2 3 4 5 1 0 1 1 0 0 2 1 0 1 1 1 3 1 1 0 1 1 4 0 1 1 0 1 5 0 1 1 1 0
а)	б)	в)

Рис.1. Пример изображения графа, состоящего из 5 вершин.

Важно, что на рисунке 1.а. приведено именно изображение некоторого графа. Это не сам граф. Его можно изобразить и иначе, например, так, как показано на рис.1.б. Все связи в новом изображении сохранились, хотя местоположение вершин и поменялось относительно друг друга.

Также граф можно записать в виде таблицы рис. 1.в. Приведенная таблица вновь отображает тот же самый граф. Иначе она называется матрицей сопряженности ^[2]G ={g}^N×N. Матрица сопряженности G квадратная и имеет размерность N×N, где N – количество вершин графа. Матрица показывает между какими вершинами графа имеются ребра, а между какими ‒ нет.

Столбцы и строки этой таблицы пронумерованы и соответствуют вершинам графа. Если на пересечении, например, строки 1 и столбца 2 в таблице выставлена единица, то это означает, что между вершинами 1 и 2 имеется ребро. Если же, например, на пересечении строки 4 и столбца 1 выставлен 0, то между вершинами 1 и 4 нет ребра. Как видно диагональ таблицы содержит только нули ‒ в нашем графе вершины не могут быть связаны сами с собой. Как видно матрица сопряженности для рассматриваемого графа симметрична относительно диагонали, так как если вершина 1 связана с вершиной 2, то верно и обратное: вершина 2 связана с вершиной 1. Эти связи симметричны.

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

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

3. Орграф и анализ телефонных переговоров

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

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

Ориентированный граф ^[1] ‒ граф, в котором ребра имеют ориентацию (направление). Изображаются ориентированные ребра со стрелочками на окончаниях (рис.2.а). Иногда именуется также орграфом.

	1 2 3 4 5 6 7 1 0 1 1 1 0 0 0 2 0 0 0 0 1 0 0 3 0 0 0 0 1 1 0 4 0 0 0 0 0 1 0 5 0 0 1 0 0 0 1 6 0 0 0 0 0 0 1 7 1 0 0 0 0 0 0
а)	б)

Рис.2. Ориентированный граф

Диагональ матрицы рис.2.б. вновь нулевая, однако симметрии относительно диагонали больше не наблюдается. В каждой строке теперь единицы выставлены в тех столбцах с которыми у соответствующей вершины имеются исходящие ребра. Если в строке 1 единицы находятся в столбцах 2, 3 и 4, то значит из вершины 1 имеются исходящие ребра к вершинам 2, 3 и 4. В каждом столбце единицы выставлены в тех строках, с которыми у соответствующей вершины имеются входящие ребра. Если в столбце 1 единица расположена только в строке 7, то значит к вершине 1 проложено входящее ребро из вершины 7. Заметим, что связи между вершинами 3 и 5 имеются в обоих направлениях. Этим связям соответствуют два ребра, что также отражено в матрице сопряженности.

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

В этом случае идет поиск такого столбца в матрице сопряженности, сумма элементов в котором максимальна. Для приведенной схемы такими вершинами окажутся 5, 6 и 7.

Аналогично (1) происходит поиск лица с наибольшим количество исходящих соединений.

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

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

4. Двудольный граф и анализ связей между разнородными объектами

Двудольный граф ^[3] ‒ граф, состоящий из вершин двух типов, причем его ребра могут соединять только вершины разных типов.

На рис.3 приведен пример такого графа, где отображены связи 20 людей (вершины первого типа) с 3 адресами (вершины второго типа). Адреса изображены треугольниками и нумерованы как а1, а2 и а3.

	а1 а1 а3 1 1 0 0 2 1 0 0 … … … … 7 1 1 1 8 1 1 0 … … … … 19 0 0 1 20 0 0 1
а)	б)

Рис.3. Пример двудольного графа

Матрица сопряженности для этого графа рис.3.б. не будет квадратной. По ее срокам будут размещены вершины одного типа (например, люди), по столбцам ‒ второго типа (соответственно ‒ адреса).

Если перед аналитиком стоит задача определить тех людей, которые побывали во всех трех адресах, то необходимо в рассмотренном графе найти все вершины первого типа с количеством ребер равным 3. В приведенном примере такая вершина только одна ‒ это вершина № 7. Формальная постановка задачи похожа на выражение (1), с той лишь разницей, что матрица сопряженности имеет размерность не N×N, а N×M, то есть количество столбцов M не равно количеству строк N.

5. Случай ориентированного двудольного графа

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

Рис.4. Ориентированный двудольный граф

Матрица сопряженности такого графа устроена несколько более сложно, чем приведенные выше. Она как в случае рассмотренном на рис.3 не симметрична, но размерности N×M для описания графа уже не хватит, поскольку тогда не ясно будет чему соответствует единица в такой матрице ‒ вкладу или кредиту. Матрица сопряженности будет трехмерной, с размерностью N×M×2, где ячейки g_ij1 будут отображать один тип связи (например, вклады), а ячейки g_ij2 ‒ второй (соответственно, кредиты).

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

Если же установлению подлежит лицо имеющее наибольшее количество отношений обоих типов в наибольшем количестве банков, то выражение (5) примет вид:

6. Маршруты в графах и задача поиска опосредованных связей между объектами анализа

Маршрутом в графе называется чередующаяся последовательность вершин и ребер графа v₀, e₀, v₁, e₁, … e_k-1, v_k, в которой любые два соседних элемента связаны, и которая таким образом устанавливает связь между двумя вершинами v₀ и v_k. Длина маршрута определяется количеством ребер, входящих в него.

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

Пусть, например, необходимо найти всех лиц, которые в одни и те же даты, пусть это будут M разных дат совершения серии преступлений, приезжали из г. Твери на Ленинградский вокзал г. Москвы. Такая схема будет описываться двудольным графом, один класс вершин которого ‒ это даты прибытия на Ленинградский вокзал, другой класс вершин ‒ паспортные данные лиц, прибывших в г. Москву на Ленинградский вокзал из г. Твери.

Формальная постановка задачи будет выглядеть следующим образом:

То есть необходимо найти все пары вершин ij, для которых , количество маршрутов длины 2 между ними равняется M.

Пусть имеется всего N = 5 пассажиров, среди которых необходимо определить приезжавших во все M = 3 даты.

	а1 а2 а3 1 1 0 0 2 1 1 1 3 1 1 1 4 0 1 1 5 0 0 1
а)	б)

Рис. 5. Двудольный граф: 5 пассажиров и 3 даты

Здесь на помощь аналитику может прийти одно замечательное свойство матрицы сопряженности. Будучи возведенной в степень q, она показывает, сколько существует маршрутов длины qмежду вершинами i и j^[4]. Искомое число находится на пересечении строки i и столбца j. Прямоугольную матрицу сопряженности, такую как в рассматриваемом случае, в квадрат возвести нельзя, однако ее можно умножить на транспонированную матрицу и получить результат G×G^T ‒ матрицу, содержащую в ячейках количество маршрутов длины 2 между вершинами первого типа (лицами). Заметим, что такой способ годится именно для нахождения количества маршрутов длины 2. Маршруты нечетной длины между вершинами одного типа в двудольном графе отсутствуют, маршруты другой четной длины могут быть найдены, но в этой задаче они не представляют интереса.

Результат умножения матрицы G, представленной на рисунке 5.б на транспонированную G^T приведен на рисунке 6.

Рис.6. Матрица сопряженности G умноженная на G^T

Из нее видно, что между вершинами 2 и 3 имеется по три маршрута длины 2. Также видно, что по 3 маршрута длины 2 имеется между вершиной 2 и вершиной 2, а также между вершиной 3 и вершиной 3, пусть этот факт не смущает читателя, поскольку он лишь характеризует наличие 3 примыкающих к этим вершинам ребер. Важно здесь, что в результате проделанных вычислений выявлена пара вершин (2 и 3), которые удовлетворяют поставленной задаче (7).

7. Cпециализированные программные средства, позволяющие решать формализованные теоретико-графовые задачи

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

- IBM I2 Analyst’s Notebook ^[5] ‒ распространяется на основе платной лицензии, достаточно требовательна к производительности компьютера, однако предлагает широкий спектр аналитических инструментов и позволяет решать практически все предложенные выше задачи. Имеет удобный пользовательский интерфейс и широкие возможности по наглядной визуализации найденных решений. Имеет русифицированную версию;

- Gephi ^[6], Pajek ^[7] ‒ бесплатно или условно бесплатно распространяемые программные продукты. Не так требовательны к производительности компьютера. Не обладают таким дружественным интерфейсом, как названная выше IBM I2 Analyst’s Notebook. Требуют знания английского языка;

- NodeXL ^[8] ‒ надстройка к Microsoft Excel. Обладает характеристиками схожими с указанными выше Gephi и Pajek. Требует наличия на компьютере Microsoft Excel и обязательного подключения к Интернету;

- Специализированные пользовательские библиотеки Networkx и igraph для языков программирования Python и R, соответственно. Требуют знания указанных языков программирования. Являются чрезвычайно гибкими инструментами анализа графов.

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

8. Заключение

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

Безусловно, процесс раскрытия преступлений не ограничивается приведенными выше задачами, являясь нетривиальной комплексной деятельностью, немыслимой на сегодняшнем этапе без участия человека. Однако при этом предложенные теоретико-графовые подходы к решению отдельных задач анализа данных способны повысить общий уровень этой деятельности в различных сферах противодействия преступности, чему посвящены работы отдельных авторов из системы МВД России. Так в работе ^[9] подобные модели приводятся применительно к анализу телефонных переговоров и установлению фактов одновременного нахождения фигурантов преступлений в определенных географических локациях. Подобные модели анализа данных могут применяться и в деятельности по противодействию экстремизму, необходимости методического обеспечения которой посвящена, например, работа ^[10]. Вопросы анализа пространственно-соотнесенных данных в геоинформационных системах органов внутренних дел рассматриваются в ^[11]. Наконец, возможность заложения подобных сетевых структур данных в уже существующие и проектируемые информационные системы органов внутренних дел рассматривается в ^[12].