Как проредить сеть, не порвав её экспресс
Густая сеть знакомств: каждый связан почти с каждым, и в этой паутине трудно понять, кто действительно важен. Слишком много нитей — компьютер задыхается, моделирование буксует. Учёные придумали, как прореживать такие сети, не теряя главного.
Идея в том, чтобы убирать связи, которые не участвуют в кратчайших путях. Как если бы в городе оставили только те улицы, по которым реально ездят, а тупики и лишние переулки снесли. Такой «скелет» сети сохраняет все важные маршруты, а заодно — структуру сообществ и динамику распространения информации или болезни.
Проверили на реальных сетях социальных контактов — из школ, больниц, рабочих мест. Оказалось, что лучше всего сохраняет ранги важности людей и динамику распространения вариант, где путь измеряется по формуле g(x,y) = (\sqrt[3]{x}+\sqrt[3]{y})^3. Такой скелет убирает больше половины связей, а сеть продолжает работать как надо.
В итоге получается не просто урезанная копия, а точная карта самых нагруженных путей. Это помогает быстрее считать модели эпидемий, находить ключевых игроков в социальных графах и понимать, где тонко — там и рвётся.
В некоторых реальных сетях после прореживания оставалось меньше половины связей, но кратчайшие пути между всеми парами узлов сохранялись полностью.