Команда исследователей из Швейцарского федерального технологического института в Лозанне (EPFL) объявила об успешной разработке некоего алгоритма, который, по их утверждению, позволяет добираться до источников эпидемии любого рода, включая информационные. То есть, если возникла эпидемия опасного заболевания, на основе очень ограниченного объёма данных алгоритм способен выявлять наиболее вероятный первоисточник таковой. Точно так же, если начинает расползаться какой-нибудь небезобидный слух, можно выяснить, кто первым его пустил, и так далее.
«Информационные» эпидемии, конечно, распутывать проще: данных о времени размещения того или иного сообщения обычно находится предостаточно, так что отследить, откуда пошёл слух, относительно несложно.
С эпидемиями болезней всё куда сложнее. Но и там есть сходства в том, что касается распространения. Совершенно, кстати, очевидные: заражение происходит по «сетевому» принципу, от одного больного к нескольким здоровым, которые, в свою очередь, заражают ещё несколько здоровых людей, и так далее.
Швейцарские исследователи во главе с Педро Пинто исходили именно из такой «сетевой» модели, где каждый условный заражённый индивидуум представлен в виде узла, соединённого с несколькими другими линиями (обозначающими взаимодействие). По сценарию Пинто, изначально все узлы являются «чистыми», затем один источник начинает распространять инфекцию, причём каждое заражение происходит с произвольной задержкой. В итоге каждый «узел» оказывается заражённым — и запоминает время, и персональный источник заражения.
Эпидемиологи в своих попытках выявить источники массовых заболеваний обычно вынуждены опираться на очень ограниченные объёмы данных. Алгоритм Пинто, получивший название Sparse Interference Algorithm (алгоритм разрежённой интерференции), как раз и разработан с тем, чтобы выявлять потенциальный источник заразы при дефиците исходных данных.
В принципе, ничего нового они и не придумали, просто приспособили к делу метод триангуляции физического положения пользователя телефона, использующийся в сотовых сетях: когда три или более базовые станции получают сигнал от одного аппарата, его местонахождение вычисляется, исходя из временных различий в поступлении сигнала.
Так же и в алгоритме Пинто время «поступления информации» (или инфицирования) узлов-наблюдателей используется для расчёта предположительного источника эпидемии. Другое дело, что в «сети заражения» временные различия могут быть связаны с тем, что до каждого наблюдателя инфекция доходит разными путями, и временные промежутки между эпизодами заражения могут значительно различаться. С другой стороны, исследователи исходили из того факта, что при распространении эпидемии её источник должен принадлежать к некоему ограниченному набору узлов.
Свой алгоритм его создатели испытывали с использованием четырёх разных моделей сетевых структур и с использованием сразу двух разных методов отбора узлов-наблюдателей. Каждая модель сетевой структуры отличается тем, как в ней определяется количество соединений между узлами. Для каждой такой модели отбор узлов-наблюдателей осуществлялся либо вообще по случайному принципу, либо из числа узлов с наибольшим количеством связей. Второй метод оказался более эффективным: если в первом случае для выявления первоисточника с 90-процентной вероятностью в «наблюдатели» пришлось записать 25 процентов всех узлов, то во втором случае тот же уровень достоверности удалось получить, опираясь на «наблюдения» только 5 процентов узлов.
Для тестирования алгоритма использовались и куда более конкретные данные: в 2000 году в Южной Африке произошла вспышка холеры. Вектором распространения заражения оказались реки, в качестве «узлов» исследователи рассматривали пострадавшие селения, связанные отрезками рек. И даже когда использовался метод случайного отбора «наблюдателей», с помощью данных из 20 процентов пострадавших селений исследователям удалось предсказать реальный источник эпидемии с относительно небольшой погрешностью.
Как утверждают исследователи, алгоритм пригоден не только для отслеживания источников эпидемий, но и для выявления источников слухов в каких-либо социальных сетях, определения источников появления вирусов в интернете и даже для профилактики терроризма (алгоритм был протестирован на данных, полученных в ходе расследования атак 11 сентября 2001 года, в частности).
Немаловажно и то, что алгоритм пригоден для использования при наличии сразу нескольких очагов эпидемии (будь то опасное заболевание или информационная «волна»).
Полный текст исследования доступен здесь.