Геометрические функционалы от случайных множеств и случайных графов

В диссертации расматриваются два основных тина случайных объектов: точечные процессы и случайные графы.

Точечный случайный процесс, иногда называемый также иногда точечным потоком, позволяет описывать конфигурации случайных точек в Md. Формально точечные процессы задаются дискретной случайной мерой. Данная область широко исследуется и имеет обширные приложения в теории массового обслуживания, распознавании образов, пространственной статистике, различных задачах подсчета и др. В развитие теории точечных процессов весомый вклад внесли такие ученые, как Барбур, Бачел-ли, Бремо, Вир-Джонс, Добрушин, Дуб, Дэли, Жакод, Калленберг, Кер-стан, Кокс, Кэмнбелл, Ласт, Маттес, Матерон, Ньюмен, Пальм, Пенроуз, Сливняк, Юкич, Яглом и другие. Теория точечных случайных процессов изложена в ряде фундаментальных книг. Достаточно упомянуть монографии Калленберга ([50]), Дэли и Вир-Джонса ([41, 42]), Мекке, Керстана и Маттеса ([5]). В диссертации исследуются модели, порожденные классическим пуассоновским точечным процессом, а также случайные множества и функционалы от точечных потоков.

Другим объектом исследований данной диссертации являются негеометрические случайные графы. В развитие теории случайных графов внесли свой вклад такие ученые, как Болобаш, Дюрретт, Колчин, Реньи, Риордап, Хохлов, Эрдёш и другие. Изложение основ данной теории можно найти, например, в книгах Болобаша [27], Колчина [3] и Дюрретта [47]. В последнее десятилетие внимание большого числа исследователей приковано к так называемым степенным законам. Степенные законы распределения степеней вершин некоторых эмпирически наблюдаемых графов породили бурный рост исследований моделей, отличающихся от классического графа Эрдёша-Реньи. В этом направлении работали такие исследователи, как Болобаш, Риордан, Спенсер, Тушнади [30], Лебедев [4], Уотте, Строгатц [82], Павлов [11], Степанов [12] и многие другие. В диссертации изучается одна из основных моделей данного типа — граф преимущественного присоединения.

Следует отметить и другие направления исследования случайных графов, в частности, закономерности в раскрасках и хроматические числа, вклад в это направление внесен такими учеными, как Боллобаш ([28]), Рай-городский ([14, ?]) и другие.

Остановимся подробнее на исследуемых в диссертации объектах. Точечный процесс задается локально конечной случайной мерой. Для процесса П, определяющего конфигурацию случайных точек выполняется равенство.

П (В) —? I (Xi е В), ггеп где В есть ограниченное борелевское подмножество R (i. Точечные процессы рассматриваются и как случайные меры, и как конфигурации точек, что не вызывает путаницы.

В первой части главы 1 изучаются замкнутые случайные множества. Основоположниками теории случайных множеств можно считать Кендел-ла [53] и Матерона [61]. Теория замкнутых случайных множеств широко развита, кроме уже упомянутых исследователей, достаточно отметить вклад Амбарцумяна [17], Молчанова [64], Штояна, Мекке [78] и других.

Случайным множеством называется случайный элемент в пространстве Т всевозможных замкнутых подмножеств снабженном топологией попадание-промах (hit-or-miss topology). Рассмотрим следующие подмножества Т {F <е Т: F п x — 0}, X с Rd] fx = {F g T: F п x ^ 0}, X с Rd.

Топология попадание-промах порождается множествами вида где К с Ж'1 есть произвольное компактное подмножество, G, ., Gnпроизвольные открытые подмножества v > 0 целое. Пространство Т, снабженное топологией попадание-промах, является компактным, сепара-бельным и хаусдорфовым ([61]).

Важным примером точечного потока является пуассоновский процесс с постоянной интенсивностью Л. Семейство П (В.ы), В с Ш1 борелевское, to Е ^ называется пуассоновским потоком интенсивности Л, если выполняются следующие три условия:

1) для любого элементарного исхода и), функция множеств П (-. и) является дискретнной локально конечной мерой на.

2) для любого замкнутого множества В с 1РА функция П (В, •) является нуассоновской случайной величиной с параметром Л В;

3) для любого набора непересекающихся множеств В2, .Вп случайные величины Yl (Bi), ЩВ2), .Т1(Вп) независимы в совокупности.

Активно исследуются маркированные точечные потоки. Этот тип потоков позволяет сопоставлять каждой точке из данной конфигурации некоторую случайную величину, что существенно увеличивает класс моделей, доступных для описания. Маркировки могут быть случайными элементами со значениями в любом сепарабельном пространстве. Маркированный точечный ноток на W1 (см., напр., [41], стр. 194) является точечным потоком в произведении пространств W1 х X, где X — пространство, в котором берутся случайные элементы — маркировки.

В первой части главы 1 рассмотрен пуассоновский точечный поток, маркированный замкнутыми случайными множествами. Случайные маркировки возникают как окрестности ребер графа ближайших соседей, имеющие случайный радиус. Мотивацией к изучению данной модели послужило наличие локальной структуры зависимости в данном множестве. Для аналогичных комбинаторных структур Аврамом и Бертсимасом была получена центральная предельная теорема. Кроме того, предпосылкой к изучению подобного случайного множества послужил ряд задач радиобиологии, вовлекающих пространственные структуры, см., напр., [52, 79, 80].

Применение различных видов облучения при лечении раковых опухолей порождает сложные задачи характеризации уровня повреждений, наноснмых опухоли и органу (ткани) при данном лечении. Разнообразные модели лучевой терапии широко исследуются. По утверждению Белломо и Пре-циози ([25]), раковые опухоли являются одним из наиболее загадочных и сложных объектов современности. Поэтому их целесообразно изучать как с биологической, так и с математической точек зрения. Действительно, огромное множество математических моделей используются для анализа поведения раковых опухолей. Такие модели опухолей необходимы радио-билогии для эффективного и безопасного лечения.

В радиобиологии применяется понятие TCP (Tumor Control Probability) — вероятность обезвреживания опухоли и NTCP (Normal Tissue Complications Probability) — вероятность повреждения здоровых тканей после облучения. Вычисление TCP и NTCP выполняется при помощи вероятностных методов. Ряд исследователей заняты разработкой алгоритмов и пакетов программ для вычисления этих вероятностей см., напр., работы Ставрева и др. [81].

Вероятность осложнений (NTCP) может зависеть от структуры органа. Для печени или легкого осложнения возникают, если при облучении поражен некоторый процент от общего объема органа. Для описания такого случая применяется модель критического объема, введенная в работах [49, 68]. Наоборот, для таких органов, как спинной мозг, повреждение одного элемента приводит к дисфункции всего органа. Такие органы описываются моделью критического элемента. Для исследования подобных структурных различий используются модели функциональных единиц FSU (Functional Subunit). Отдельная функциональная единица может быть клеткой или группой клеток. Модель широко изучается как с прикладной, так и с теоретической точек зрения см., напр., [79, 81]. Биологические параметры отдельных единиц сказываются только на свойствах данной функциональной единицы. Орган можно рассматривать как объединенные в некоторую структуру FSU. Существуют более сложные модели объединения единиц, см., напр., [52], где орган (например, мышечная ткань) рассматривается как набор параллельных взаимодействующих цепей.

Многие модели не вовлекают формализм функциональных единиц. В работе [60] исследуется модель с различным разбиением исследуемого органа на кластеры, клетки опухоли объединяются в сферические кластеры с меньшим радиусом, здоровые — в кластеры с большим радиусом. Имеется также ряд моделей [54, 59, 76], учитывающих, например, миграцию клеток опухоли и другие эффекты, не описываемые формализмом функциональных единиц.

В статьях Тэмса и др. [79, 80] было обращено внимание на пространственное размещение пораженных клеток. Это интересное прикладное исследование, включающее сопоставление с клиническими данными.

Учет связей между частями опухоли — это важный фактор, требующий всестороннего изучения. В работе Булинского и Хренникова [35] впервые были исследованы зависимые FSU, см. также [36].

Рассматриваемые в главе 1 данной диссертации объекты могут служить основой для создания модели пораженной при облучении ткани, так как позволяют описывать образование случайных структур достаточно общего.

Рис. 1. Mo-заика Вороного и двойственная ей триангуляция Делоне.

Аврам и Бертсимас ([18]) расмотрели граф £—го ближайшего соседа, мозаику Вороного и триангуляцию Делоне, порожденные точками пуассонов-ского точечного потока. Ими был предложен общий путь доказательства центральной предельной теоремы для случайных величин, возникающих в задачах комбинаторной оптимизации. Речь идет о методе, основанном на локализации структуры зависимости. Для различных комбинаторных задач интересные асимптотические результаты были установлены, например, Кимом, Ли, Лином [51] и другими.

Как показано автором, рассмотренные в данной работе случайные множества также обладают локальной структурой зависимости. Это позволило доказать закон повторного логарифма для последовательности Sn = D П [— п, n) d объемов исследуемого случайного множества, попавших в растущие кубы.

В ходе доказательства для нормированной последовательности Sn были получены моментное и максимальное неравенства, оценка скорости сходимости к нормальному закону. Все результаты раздела 1 главы 1 могут быть с незначительными изменениями в доказательстве установлены для различных моделей случайных множеств, основанных на графе k-vo ближайшего соседа, мозаике Вороного или триангуляции Делоне. Ввиду этого факта, в диссертации особое внимание было обращено на понятие экспоненциально стабилизирующихся функционалов.

Такие функционалы были впервые рассмотрены Пенроузом и Юкичем в [71, 72] и изучались далее ими, а также Айхельсбахером, Барышниковым, Шрайбером [23], Щерабковым [70] и другими.

Идея стабилизации состоит в том, что для каждой точки потока найдется такой круг случайного радиуса, что изменение конфигурации точек потока вне данного круга не влияет на значение функционала в рассматриваемой точке. Экспоненциально стабилизирующимся называется функционал, для которого хвост радиуса стабилизации убывает экспоненциально быстро.

Определение 1 ([69]). Для любого локально конечного множества X с Rd и любого х? Ш.'1 назовем радиусом стабилизации функционала ф = ф (х, X) величину R = R.(x. X) > 0 такую, что для каждого натурального числа г > R выполняется равенство ф (х, {j-} и X П Вг (х)) = ф (х, {х} U X), где Вг{х) обозначает замкнутый круг радиуса г в Md. Если такого конечного R не существует, то полагаем R = оо.

Определение 2 ([69]), Семейство функционалов ф = ф (х, •), х е М'7, экспоненциально стабилизируется, если его радиус стабилизации п.н. конечен, и для всех t > 0 и некоторых положительных постоянных С и с справедливо неравенство r{t) := sup Р (В,(х, {х} U II) >t)< Cc~ct. xeRd.

Примерами таких функционалов являются расстояние до ближайшего соседа, площадь и периметр ячейки мозаики Вороного в R2 и многие другие, см., напр., [73].

Для сумм экспоненциально стабилизирующихся функционалов установлен ряд важных предельных теорем. Пенроуз и Юкич доказали слабый закон больших чисел ([71]) и центральную предельную теорему ([69, 73]). Юкичем и Барышниковым были установлены функциональные предельные теоремы для нестационарного пуассоновского потока ([24]). Барышниковым, Шрайбером, Юкичем и другими также были исследованы большие уклонения для сумм упомянутых функционалов ([23]).

В диссертации исследуются суммы экспоненциально стабилизирующихся функционалов, берущихся от пуассоновского точечного потока в R'7 постоянной интенсивности, А = 1. Для изучения предельного поведения суммы данных функционалов рассматривается вспомогательное случайное иоле, порожденное частными суммами функционалов на единичных кубах Qi = [0, l) d + г, г € Элементы этого случайного поля имеют вид.

Xi= ]Г ф{х, п п), iezd.

Для данного ноля X — г? Zd} в работе получена экспоненциальная оценка коэффициента сильного перемешивания а (и, v, r).

Напомним определение такого коэффициента для случайного поля на решетке 7Ld. Определим коэффициент сильного перемешивания (или перемешивания по Розенблату) для двух ст-алгебр Л, В с J7: а (Л. В)= sup |Р (Л)Р (Б) — Р (ЛВ).

АеЛ, ВеВ.

Для подмножества U с Zd пусть Tj = а {Х{, i е U} обозначает а-алгебру, порожденную элементами Xi: i е U ноля X. Тогда (см., напр., [40]) а (и, v, r) = sup {а {Ти-, 3~v) ¦ U < и, V < v, p (U, V) > ?¦} .

Напомним, что коэффициент сильного перемешивания аявляется самым слабым из всех коэффициентов перемешивания. Более подробно о данном виде зависимости случайных полей см., напр., Дукан [40], где дается обзор развитой теории перемешивания как для случайных последовательностей, так и для случайных полей. Следует также отметить недавнюю обзорную работу Брэдли [34], посвященную различным коэффициентам перемешивания.

Имеются различные оценки скорости слабой сходимости к нормальному закону для случайного ноля с перемешиванием, например работы Булин-ского [1], Сунклодаса [16], Дедекера [43]. В работе использованы момёнтные неравенства для случайного ноля с сильным перемешиванием (см., напр. [40]) и ЦПТ Сунклодаса [16].

В ходе доказательства закона повторного логарифма установлено максимальное неравенство для случайного поля X. Для доказательства этого утверждения применена техника Вишуры ([83]).

Вторая глава диссертации посвящена исследованию негеометрического случайного графа преимущественного присоединения.

В работах Фалуцосов [48], Барабаши и Альберт [21, 22] был исследован граф сети Интернет. Веб-сайты рассматривались как вершины графа, а гиперссылки между сайтами — как ребра. Данными авторами было обнаружено. что в таком графе степени вершин распределены по степенному закону. В этих же работах было предложено для описания подобных структур использовать модель графа преимущественного присоединения. Позднее различными авторами было обнаружено множество эмпирических графов, обладающих степенным законом в описанном выше смысле. Среди таких графов социальные сети, графы совместной работы ученых, нейронные сети человеческого мозга, сети электроснабжения.

Одной из основных теоретических моделей для данных графов стал граф преимущественного присоединения. Суть модели графа преимущественного присоединения в том, что вершина, уже имеющая большую степень, имеет больше шансов получить новые ребра, что очень естественно для сети интернет, социальных сетей и других структур, где уже набранный вес вершины играет существенную роль в получении новых ребер.

Введем определение графа преимущественного присоединения G]'n. Определение 3 ([33]). Пусть га — натуральное число. Для т — 1 зададим граф преимущественного присоединения G™n по индукции. Для я = 1 пусть G состоит из одной вершины и одной петли. Граф G" получается из графа С?" -1 добавлением вершины номер п и ребра между ней и вершиной со случайным номером имеющим распределение.

Для т > 1 граф G™ получается из графа G'{" отождествлением вервершину 2 и т. д.

История исследования графа преимущественного присоединения восходи к работам начала ([85]) и середины ([77]) прошлого века. В контексте современных исследований следует отметить работу Альберт и Бараба-ши [22], где граф преимущественного присоединения был впервые предложен как модель интернета. Следует отметить, что в этой же работе, исходя из эвристических соображений, было показано, что данный граф должен обладать степенным законом.

В работе Болобаша, Риордана, Спенсера и Тушнади [30] было строго доказано, что граф преимущественного присоединения имеет асимитотигде cl? обозначает степень вершины номер I в графе G" 1. шин с номерами 1. т в вершину 1 графа, вершин га + 1., 2 т в чески степенное распределение степеней вершин. Отметим, что Мори ([65]) установил данный результат независимо.

Граф преимущественного присоединения активно исследовался последнее десятилетие, для него получено множество результатов, в частности, оценка размера гигантской компоненты, оценка асимптотического поведения диаметра [33], исследованы максимальные степени вершин [66]. Имеются различные модификации данного случайного графа. В работе Рудаса, Тота и Валько ([75]) рассмотрен вариант графа преимущественного присоединения с произвольной весовой функцией. Атрея, Гош и Сетурамап ([19]) рассмотрели определение этого объекта через непрерывный случайный процесс, позволяющее добавлять случайное количество ребер на каждом шаге. Дейджфен, Ескер, Ховсгад и Хугхимстра рассмотрели модель графа преимущественного присоединения, начинающегося на некотором шаге со случайного графа, имеющего другую структуру [44].

Болобаш и Риордан изучили ([31]) сходство и различие между графом преимущественного присоединения и классической моделью Эрдёша-Рсньи. В первой части главы 2 диссертации получена оценка вероятноегп для канлинга двух данных графов при параметре т = тп (числа ребер графа, добавляемых на каждом шаге), зависящем ori п. Эта оценка усиливает один из результатов, полученный Волобашем и Риорданом.

Во второй части главы 2 оценена вероятность локализации диаметра в случайном графе преимущественного присоединения. Для доказательства данного результата потребовалось применение техники Болобаша и Рпор-дапа, использованной в [33]. Важным приемом, позволяющим работать со структурой зависимости графа преимущественного присоединения является применение линеаризованной диаграммы хорд. Этот хорошо известный математический объект был впервые применен для описания графа преимущественного присоединения Болобашем и Риорданом.

Различные графы, обладающие отличной от модели Эрдёша-Реньи структурой, активно исследовались в последнее десятилетие такими авторами как Уотте, Строгатц [82, 81], Чанг, Лу [38], Кугюр, Фрези [39] и многие другие. Обнаруженное Строгатцем и Уоттсом ([82]) резкое уменьшение диаметра графа при добавлении небольшого процента хаоса в регулярный граф было популяризовано и породило повсеместно известную концепцию шести степеней отчуждения (six degrees of separation), в соответствии с которой любые два человека на планете связаны не более чем через шесть рукопожатий.

Существует множество различных случайных графов, предлагаемых как модели описанных выше эмпирически наблюдаемых графов. Приведем примеры некоторых из них.

• Модель «маленького мира» Уоттса-Строгатца [82]. В 1998 году Уотте и Строгатц предположили рассматривать модель графа, обладающего определенными свойствами некоторых наблюдаемых сетей. Они изучили нейронные сети, электрические сети запада США и сеть совместной работы актеров в фильмах. Было обнаружено, что добавление небольшой доли случайности в построение регулярного графа ведет к резкому уменьшению диаметра данного графа. Уоттсом и Строгатцем была разработана модель случайного графа, получающаяся за счет случайного изменения некоторых регулярных графов. Данный граф обладает экспоненциальным распределением степеней вершин.

• Модель Чанга-Jly. Чанг и Лу [38] рассмотрели граф с заданным средним распределением вершин. Для данной последовательности степеней вершин w = (wi,., wn) рассматривается граф, в котором наличие ребра между любыми двумя вершинами есть независимое случайное событие с вероятностью рг] = wlwJ/ vikДля данного графа математическое ожидание степени вершины i равно w,.

• Модель Бакли-Остхауса. Две группы исследователей: Дороговцев, Мендес и Самухин [45] в 2000 и Дриня, Иначеску и Митценмахер [46] в 2001 рассмотрели вариант модели Барабаши и Альберт, в которой каждая вершина имеет параметр изначальной привлекательности. Вероятность того, что новая вершина соединится с одной из предыдущих вершин, пропорциональна степени последней, сложенной с изначальной привлекательностью вершины.

• Модель копирования. Группа из шести авторов [55] предложила рассматривать модель, в которой новая вершина появляется как результат копирования ребер некоторой уже существующей вершины. Часть ребер проводится к тем же вершинам, что и у исходной вершины, часть — равномерно случайно выбирается из общего набора ребер.

• Модель Купера-Фрези. Купер и Фрези [39] рассмотрели модификацию графа преимущественного присоединения, допускающую широкие возможности выбора параметров процесса эволюции графа. В работе рассматривается несколько типов процессов, которые могут происходить на каждом шаге: возникновение ребра от одной из старых вершин, появление новой вершины, возникновение ребер у новой вершины, исходя из равномерного распределения, или — из закона, преимущественного присоединения.

• Модели ориентированных графов. Болобаш, Борге, Чаес и Риор-дан [29] рассмотрели модель ориентированного графа, допускающую, как и в модели Купера и Фрези, различные процессы на каждом шаге выбора параметров течения эволюции графа, в соответствии с реальными процессами в сетях.

Обзоры работ, посвященные данным исследованиям, можно найти в статьях Митценмахера [62, 63] и Болобаша и Риордана [32].

Вопрос адекватности моделей случайных графов реальным данным был затронут в более поздних работах Митценмахера ([63]), Виллингера, Аль-дерсона, Дойля, Ли ([58, 84]) и других. Митценмахер [63] в 2006 году критически оценил будущее исследований степенного закона, сводящихся к интерпретации сырых статистических данных и построению моделей исходя из эвристических соображений. Он призвал сместить фокус внимания сообщества к проверке уже имеющихся моделей. В этом ключе следует обратить внимание на работу Виллингера, Альдерсона и Дойля [84]. подвергающую сомнению качество данных, на которых основывали свои выводы Барабаши и Альберт. Виллингер и др. обратили внимание на мно-гослойность сети интернет, в частности, на способ объединения IP адресов, который кардинально меняет наблюдаемую картину. Виллингером и др. была предложена своя модель сети, основанная частично на инженерных соображениях, точнее отражающая фактическую ситуацию, но значительно менее удобная с теоретической точки зрения.

В третье главе диссертации разработан статистический тест адекватности модели графа преимущественного присоединения эмпирическим данным. Статистический тест использует понятие среднего диаметра. Средний диаметр вычисляется как расстояние между двумя равномерно выбранными вершинами графа. Этот тип диаметра графа был применен Ку-маром, Новаком и Томкисом ([56]) для анализа социальных сетей Flickr и Yahoo!360. Данная величина значительно выгоднее с точки зрения вычисления статистик по эмпирическим данным, так как требует меньших затрат вычислительной мощности.

Статистический тест получен на базе оценки вероятности локализации диаметра графа преимущественного присоединения. Для случайных графов Уоттса и Строгатца, Эрдёша и Реньи, Альберт и Барабаши произведено численное моделирование с вычислением среднего дамегра. Моделирование производилось при помощи имплементации пакета igraph 0.5.2 для языка анализа статистических данных R. Построены реализации случайных графов с числом вершин до 105, числом ребер до 10° и широким диапазоном значений параметров.

Благодарности: Автор благодарен профессору А. В. Булинскому за постановку задач и неоценимую помощь в научной работе, а также за его безграничное терпение. Автор признателен доценту А. П. Шашкпну и аспиранту П. А. Яськову за полезные замечания и стимулирующие обсуждения ряда проблем.

1. А. В. Булинский, Предельные теоремы в условиях слабой зависимости. М., Изд-во МГУ, 1989.

2. А. В. Булинский, А. Н. Ширяев, Теория случайных процессов. М., Физматлит, 2003.

3. В. Ф. Колчин, Случайные графы. 2-е изд. М., Физматлит, 2004.

4. А. В. Лебедев, Максимумы активности в случайных сетях в случае тяжелых хвостов, Пробл. передачи информ., 2008, 44(2), 96−100.

5. Й. Мекке, Й. Керстан, К. Маттес, Безгранично делимые точечные процессы. М., Наука, 1982.

6. М. М. Мусин, Закон повторного логарифма для последовательности объемов случайных множеств, Труды XXVIII Конференции молодых ученых механико-математического факультета МГУ, Часть II. М., изд-во ЦПИ мехмата МГУ, 2006, стр. 147−150.

7. М. М. Мусин, Закон повторного логарифма для сумм экспоненциально стабилизирующихся функционалов, Матем. заметки., 2009, 85(2), 234−245.

8. М. М. Мусин, Оценка каплинга случайного графа преимущественного присоединения и графа Эрдёша-Реньи, Обозр. Прикл. и Пром. Мат., 2009, 16(3), 546−547.

9. М. М. Мусин, Статистический тест для случайного графа преимущественного присоединения, Обозр. Прикл. и Пром. Мат., 2009, 16(4), 684.

10. М. М. Мусин, Оценка вероятности локализации диаметра случайного графа преимущественного присоединения, Дискрет, математика, to appear. 2009.

11. Ю. Л. Павлов, Предельное распределение объема гигантской компоненты в случайном графе Интернет-типа, Дискрет, матем., 2007, 19(3), 22−34.

12. Ю. Л. Павлов, М. М. Степанов, Об асимптотических свойствах случайных графов интернет-типа, Обозр. Прикл. и Пром. Мат., 2005, 12(3), 677.