Аннотация:
Свяжем с каждой вершиной случайного графа неотрицательную случайную величину, которую назовем «весом». Предполагается, что все веса независимы и одинаково распределены, причем их распределения имеют «тяжелые хвосты» (описываемые правильно меняющимися функциями). Берутся суммы весов по вершине и ее ближайшим соседям. Нас интересуют условия, при которых максимум случайных сумм растет асимптотически так же, как и максимум весов без суммирования. Мы используем различные модели этих графов: классические, исследование которых восходит к работам Эрдёша и Реньи, и степенные (безмасштабные), активное исследование которых в последнее десятилетие было инициировано Барабаши. Для классических графов асимптотическая эквивалентность максимумов оказывается верна всегда. Для степенных графов возникают некоторые ограничения в форме неравенств.
|