Новые препринты в arXiv’е
Thresholds for virus spread on networks
Authors: M.Draief; A.Ganesh; L.Massoulie
We study how the spread of computer viruses, worms, and other self-replicating malware is affected by the logical topology of the network over which they propagate. We consider a model in which each host can be in one of 3 possible states - susceptible, infected or removed (cured, and no longer susceptible to infection). We characterise how the size of the population that eventually becomes infected depends on the network topology. Specifically, we show that if the ratio of cure to infection rates is larger than the spectral radius of the graph, and the initial infected population is small, then the final infected population is also small in a sense that can be made precise. Conversely, if this ratio is smaller than the spectral radius, then we show in some graph models of practical interest (including power law random graphs) that the final infected population is large. These results yield insights into what the critical parameters are in determining virus spread in networks.
Интересно, как в этой в общем-то частной задаче важная роль оказывается отведённой значению спектрального зазора в графе, на котором распространяется “инфекция”. Связь спектральных свойств с геометрией графов обсуждается на физическом уровне строгости в препринте Донетти, Нери и Муньоса с игривым названием “Optimal network topologies: Expanders, Cages, Ramanujan graphs, Entangled networks and all that“. Кроме спектрального анализа, этот предмет связан и с комбинаторной оптимизацией, поскольку “изопериметрическая константа”, оценивающая спектральный зазор снизу, в свою очередь может быть оценена через решение задачи о потоках и разрезах. Интересная континуальная переформулировка этого дискретного результата есть в препринте Д. Гризера The first eigenvalue of the Laplacian, isoperimetric constants, and the Max Flow Min Cut Theorem.
Во-вторых, вот интересная историческая статья об источниках и составных частях колмогоровской формулировки теории вероятностей:
The Sources of Kolmogorov’s Grundbegriffe
Authors: Glenn Shafer, Vladimir Vovk
Andrei Kolmogorov’s Grundbegriffe der Wahrscheinlichkeits-rechnung put probability’s modern mathematical formalism in place. It also provided a philosophy of probability–an explanation of how the formalism can be connected to the world of experience. In this article, we examine the sources of these two aspects of the Grundbegriffe–the work of the earlier scholars whose ideas Kolmogorov synthesized.
