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

Торопов Борис Андреевич кандидат технических наук доцент, Академия управления МВД России 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 Издательство О нас Наши реквизиты Наши партнеры Контактная информация Политика конфиденциальности   Авторам Договоры Авторская зона   Услуги Институт рецензирования   Разное Как написать статью? Журналы в перечне ВАК Мобильное приложение Вопрос - ответ   Наши сайты Aurora group s.r.o. © 1998 – 2024 Nota Bene. Publishing Technologies. NB-Media Ltd.