
Математики из Австралии и Малайзии создали алгоритм анализа социальных графов, который позволяет выделять небольшие «подсети» связей между подозреваемыми в преступлении по их электронной переписке. Новый метод протестировали на базе электронной почты корпорации Enron, обанкротившейся в 2001 году. Также авторы продемонстрировали преимущество своего алгоритма по сравнению с другими известными подходами к этой задаче. Преприт работы выложен  на сайте arxiv.org.Предложенный алгоритм (SPNSA: shortest paths network search algorithm) использует следующий подход: выделяют список ключевых адресов (в него входят или подозреваемые или просто определенный круг людей, например, только финансовые-менеджеры или только топ-менеджеры); для каждого адреса строится «эго-сеть», то есть граф всех его корреспондентов. В рамках этого графа выделяется адрес-посредник (Middle Man, MM, по критерию наибольшей центральности по посредничеству) и самый влиятельный адрес (Most Influential, MI, с самой большой центральностью собственного вектора). Далее выбираются кратчайшие связи между «эго», MM, MI и другими адресами из первого списка. После проведения такой процедуры для каждого адреса из первого списка авторы строят подграф, содержащий все отобранные связи.Ученые начинали свой анализ с очистки базы электронных писем от «лишних» адресов: @amazon.com, @aircanada.com и т.п. Они удаляли ящики для автоматической рассылки, адреса с цифрами вида 235643@... и так далее. После этого они делили базу на две группы по наличию в письмах скрытой копии (bcc:). Авторы аргументируют этот шаг тем, что подобные письма часто содержат наиболее важную или приватную информацию, поэтому их анализ позволяет лучше проследить, насколько тесна связь между адресатами.По двум группам — со скрытой копией (BCC) и без (TO&CC) — авторы строили графы связей между почтовыми адресами: с учетом «направления» писем (ориентированный граф) и без (неориентированный граф). На полученных четырех графах строили дальнейший анализ. Расматривали 3 возможных сценария: 1) аналитик знает личности преступников или хотя бы ключевых подозреваемых; 2) известны все преступники, кроме одного; 3) личности преступников неизвестны. Во всех случаях авторы использовали свой алгоритм и сравнивали его с другими популярными методами. Полученные подграфы анализировали по количеству вершин (чем их меньше, тем проще дальнейший «ручной анализ») и наличию в них наибольшего числа известных преступников (из списка обвиненных по делу Enron).Во всех случаях оказалось, что подграфы, полученные при помощи SPNSA, содержали меньше вершин, но больше преступников из первого списка (семь из десяти или больше). Авторы делают вывод, что их алгоритм позволяет значительно упростить процедуру анализа социальных связей при расследовании преступлений, совершенных группой лиц. Поскольку новый метод не анализирует сам текст письма, он также оказывается одним из самых быстрых алгоритмов на сегодняшний день.
