Геометрические функционалы от случайных множеств и случайных графов тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Московский государственный университет им. М. В. Ломоносова Механико-математический факультет

На правах рукописи УДК 519.21

МУСИН Максим Маратович

ГЕОМЕТРИЧЕСКИЕ ФУНКЦИОНАЛЫ ОТ СЛУЧАЙНЫХ МНОЖЕСТВ И СЛУЧАЙНЫХ ГРАФОВ

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

□□3489479

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2009

003489479

Работа выполнена на кафедре теории вероятностей механико-математического факультета Московского государственного университета им. М. В. Ломоносова

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор

Александр Вадимович Булинский

доктор физико-математических

наук, профессор

Валентин Федорович Колчин

доктор физико-математических наук

Андрей Михайлович Райгородский

Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН

Защита диссертации состоится 25 декабря 2009 г. в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 в Московском государственном университете им. М. В. Ломоносова по адресу: 119991, ГСП-1: Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 16-24.

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

Автореферат разослан 24 ноября 2009 г.

Ученый секретарь диссертационного совета Д 501.001.85 в МГУ, доктор физико-математических наук, профессор

И.Н. Сергеев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Точечный случайный процесс, называемый также иногда точечным потоком, позволяет описывать конфигурации случайных точек в Rd. Формально точечные процессы задаются дискретной случайной мерой. Точечные процессы - широко исследуемая область, имеющая приложения в теории массового обслуживания, распознавании образов, статистической физике, науках о материалах, пространственной статистике и др. В развитие теории точечных процессов внесли вклад такие ученые, как Барбур, Бачелли, Бремо, Вир-Джонс, Добрушин, Дуб, Дэ-ли, Жакод, Калленберг, Керстан, Кокс, Кэмпбелл, Ласт, Маттес, Ньюмен, Пальм, Пенроуз, Сливняк, Юкич, Яглом и другие. Основы теории точечных случайных процессов изложены в ряде фундаментальных книг, среди которых следует упомянуть монографии Калленберга1, Дэли и Вир-Джонса2,3, Мекке, Керстана и Маттеса4. В диссертации исследуются модели, порожденные классическим пуассоновским точечным процессом, а также случайные множества и функционалы от точечных потоков.

Другим объектом исследований данной диссертации являются негеометрические случайные графы. В развитие теории случайных графов внесли свой вклад такие ученые, как Болобаш, Дюрретт, Кол-чин, Реньи, Риордан, Эрдёш и другие. Изложение основ данной теории можно найти, например, в книгах Болобаша5, Колчина6 и Дюррет-

Ю. Kallenberg, Random Measures, 4th ed., N.Y., Academic Press, 1986.

2D. Daley, D. Vere-Jones, An Introduction to the Theory of Point Processes Vol. I:

Elementary Theory sind Methods. 2ed., Springer, 2003

3D. Daley, D. Vere-Jones An Introduction to the Theory of Point Processes Vol. II: General Theory and Structure. 2ed., Springer, 2008.

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

5B.Bollobas, Random Graphs, 2nd ed., Cambridge University Press, 2001.

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

та7. В последнее десятилетие внимание большого числа исследователей приковано к так называемым степенным законам. Такие законы распределения степеней вершин некоторых эмпирически наблюдаемых графов породили бурный рост исследований моделей, отличающихся от классического графа Эрдёша-Реньи. В диссертации изучается одна из основных моделей данного типа - граф преимущественного присоединения.

Следует отметить и другие направления исследования случайных графов, в частности, закономерности в раскрасках и хроматические числа, вклад в это направление внесен такими учеными, как Болобаш8, Райгородский9 и другие.

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

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

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

7R. Durrett, Random graph dynamics, Cambridge University Press, 2007.

8B.Bollobas, The chromatic number of random graphs, Combinatorica, 1988, 8, 4956.

9A.M. Райгородский, Раскраски пространств и случайные графы, Фундамент, и прикл. адатем., 2005, 11(6), 131-141.

а также ряд задач радиобиологии, вовлекающих пространственные соображения (см., напр., Булинский и Хренников10).

Граф к-го ближайшего соседа, порожденный точками пуассонов-ского потока, был рассмотрен Аврамом и Бертсимасом наряду с мозаикой Вороного и триангуляцией Делоне. Ими был предложен общий метод11 доказательства центральных предельных теорем для аналогичный задач комбинаторной оптимизации, основанный на локализации структуры зависимости. Рассмотренное нами случайное множество, как показано автором, также обладает локальной структурой зависимости, что позволило доказать закон повторного логарифма для последовательности его объемов, попавших в растущий куб. С незначительными изменениями доказательство может быть модифицировано для целого ряда аналогичных структур. Учитывая этот факт, в диссертации особое внимание было обращено на понятие экспоненциально стабилизирующихся функционалов.

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

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

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

10A. Bulinski, A. Khrennikov, Generalization of the critical volume NTCP model in radiobiology, Université Paris-6 Pierre et Marie Curie, CNRS U.M.R. 7599, 2005, Probabilities et Modèles Aléatoires. 1-13.

UF. Avram, D.Bertsimas, On central limit theorems in geometric probability, Ann.

Appl. Probab., 1993, 3, 1033-1046.

12M.D. Penrose, J.E. Yukich, Central limit theorems for some graphs in computational

geometry, Ann. Appl. Probab., 2001, 11(4), 1005-1041.

функционалов: длина графа к-то ближайшего соседа, длина и размер ячейки мозаики Вороного, или триангуляции Делоне, модель последовательной парковки и др.

В диссертации рассматриваются суммы экспоненциально стабилизирующихся функционалов от пуассоновского точечного потока в Rd постоянной интенсивности А = 1. Для исследования предельного поведения данных сумм было использовано случайное поле, порожденное частными суммами функционалов по точкам потока, попавшим в единичные кубы Qi — [0, l)d + i, i € Zd. Для описанного случайного поля получена экспоненциальная оценка коэффициента сильного перемешивания a(u,ü,r).

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

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

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

13М. Faloutsos, P. Faloutsos, С. Faloutsos, On power law relationship of the Internet

topology, ACM Сотр. Comm. Review, 1999, 29(4)

UA.-L.Barabasi and R.Albert, Emergence of scaling in random networks, Science,

1999, 286, 509-512.

15 A.-L. Barabasi, R.Albert, H.Jeong, G. В i anconi, Power-Law Distribution of the World Wide Web, Science, 2000, 287, 2115.

В работе Болобаша, Риордана, Спенсера и Тушнади16 было строго доказано, что граф преимущественного присоединения имеет асимптотически степенное распределение степеней вершин.

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

В диссертации для графа преимущественного присоединения оценена вероятность локализации диаметра, а также получены оценки вероятности для каплинга данного графа и графа Эрдёша-Реньи.

Вопрос адекватности моделей случайных графов реальным данным был затронут в более поздних работах Митценмахера, Виллингера, Альдерсона, Дойля, Ли и др. Митценмахер17 отмечает, что бурный рост исследований степенного закона породил большое количество интерпретаций непроверенных данных. Виллингер и др.18 подвергли сомнениям способ исследований интернета, примененный Фалуцосами, Альберт и Барабаши. Набор исходных дынных, который, по мнению Альберт и Барабаши, представлял из себя граф Интернета, на самом деле не являлся таковыми. Причиной этого стала многослойная структура сети Интернет. Митценмахер в свою очередь отмечает в своей работе, что акцент в исследованиях графов интернет-типа должен быть смещен от интерпретации необработанных данных и создания новых моделей из эмпирических предположений к верификации имеющихся. В русле этого подхода в диссертации построен статистический тест для проверки адекватности модели графа преимущественного присо-

I6B.Bollobas, О.Riordan, J.Spencer, G.Tusnady, The Degree Sequence of a Scale-Free Random Graph Process, Random Struct. Algorithm., 2001, 18(3), 279-290.

l7M. Mitzenmacher, Editorial: The Future of Power Law Research, Internet Math.,

2006, 2(4), 552-534.

18W.Willinger, D.Alderson, J.C.Doyle, Mathematics and the Internet: A Source of Enormous Confusion and Great Potential, Not. AMS, 2009, 56(5), 586-599.

единения. На базе полученных результатов о локализации диаметра была оценена ошибка первого рода для данного теста.

Цель работы

Настоящая диссертация посвящена исследованию случайных потоков и случайных графов. Её основные задачи - получить предельные теоремы для параметров описываемых моделей.

Научная новизна

Основные результаты работы являются новыми и состоят в следующем.

1. Установлен закон повторного логарифма для последовательности объёмов случайного множества.

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

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

4. Оценена вероятность локализации диаметра случайного графа преимущественного присоединения.

5. Получена оценка ошибки первого рода для статистического теста адекватности данного графа модели преимущественного присоединения.

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

Методы исследования

В работе применены методы исследования точечных процессов -формула Кэмпбелла-Сливняка, методы анализа случайных полей, в том числе моментные неравенства для сумм мультииндексированных

случайных величин, техника Вишуры доказательства максимальных неравенств, аппарат анализа случайных графов. Кроме того, использованы предельные теоремы для слабо зависимых случайных величин.

Теоретическая и прикладная ценность

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

Апробация работы

Результаты диссертации неоднократно докладывались автором на семинаре "Асимптотический анализ случайных процессов и полей" (мехмат МГУ, 2005-2008 гг., руководители - профессор A.B. Булинский и доцент А.П. Шашкин), на Большом семинаре кафедры теории вероятностей (мехмат МГУ, 2009 г., руководитель - член-корреспондент РАН А.Н. Ширяев), научно-исследовательском семинаре кафедры анализа данных (ФИВТ МФТИ, 2009 г., руководитель - профессор A.M. Райгородский), городском семинаре по теории вероятностей и математической статистике (ПОМИ РАН, 2009 г., руководитель - академик РАН И.А. Ибрагимов), семинаре института стохастики (Университет Ульма, Германия, 2009 г., руководители профессор Е. Сподарев и профессор Ф. Шмидт), международной конференции SGSIA (Блаубой-рен, Германия, 2009 г.), международной конференции SARD (Львов, Украина, 2009 г.), XXVIII конференции молодых ученых механико-математического факультета МГУ (Москва, 2006 г.).

Публикации

Результаты диссертации опубликованы в 5 работах, список которых приведен в конце автореферата.

Структура диссертации

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении излагается история вопроса, формулируются основные определения и описывается структура работы.

Введем основные определения. Пусть |Л| обозначает число элементов конечного множества Л, или меру Лебега для континуальных подмножеств Rd. Положим р(х, у) = supi=lj d |Xi - уг|, ж, у € РА Обозначим Вг{х) = [у 6 Rd : р(х,у) < г} замкнутый шар радиуса г > 0 с центром в точке х € Rd. Пусть loga; = Inх V 1 для х G R.

Точечный процесс задается локально конечной случайной мерой. Для процесса П, задающего конфигурацию точек {я;}^, выполняется равенство

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

Функционалом от точечного процессса назовем измеримое отображение из пространства локально конечных мер в R. Определим понятие радиуса стабилизации для данного функционала, введенное Пен-роузом и Юкичем.

Определение 1.2.1. Для любого локально конечного множества X с Rd и любого х е Rd назовем радиусом стабилизации функционала ф = ф{х, X) величину R = R(x, X) > 0 такую, что для любого натурального числа г > R выполняются равенства

ф (х, {я} U X П Вг{х)) = ф {х, {a:} U X).

Если такого конечного R не существует, то положим R — оо. Определение 1.2.2. Семейство функционалов ф — ф(х, •), х € Rd, экспоненциально стабилизируется, если его радиус стабилизации п.н. конечен, причем для всех t > 0 и некоторых положительных постоянных С и с справедливо неравенство

r(í) := sup Р (Л(х, {х} U П) > *) < С ехр{—cí}.

x£Rd

Сформулируем олределние графа преимущественного присоединения, введенное Болобашем и Риорданом.

Определение 2.1.1. Пусть т - натуральное число. Для т = 1 зададим граф преимущественного присоединения по индукции. Для тг = 1 пусть С} состоит из одной вершины и одной петли. Граф С?" получается из графа С"-1 добавлением вершины номер п и ребра между ней и вершиной со случайным номером £„, имеющим распределение

Р (Ъ = 1)

где сф обозначает степень вершины номер I в графе С1™-1.

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

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

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

Для последовательности объемов = |Г> П [—п, п)^| данного случайного множества получен закон повторного логарифма.

Теорема 1.1.1. Пусть для некоторых и,ц > 0 выполнено условие

V < 6г( ^ V п-н-1 х% € П.

Тогда справедливы соотношения

5П Е5П

1 п.н.

Пт т£

п->со r(2<í+1n<iloglogn)1/2

1 П.Н.

где г - некоторая постоянная, не зависящая от п.

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

Вторая часть первой главы посвящена исследованию сумм экспоненциально стабилизирующихся функционалов от точечного потока. Исследуются суммы функционалов от точечного потока вида ф(х, Л!), где х е К'1, X - произвольное локально конечное множество на

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

В работе изучаются функционалы, обладающие следующими свойствами.

(А1) трансляционно инвариантен; (А2) £ - экспоненциально стабилизируется; (АЗ) ЕХ0 = 0;

(А4) Е |Х0|2+<5 < оо для некоторого Ь <Е (0,1].

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

ХбППС?4

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

Напомним определение коэффициента сильного перемешивания для случайного поля. Для сг-алгебр Л, В а Т обозначим а (А, В) = эиРлеА.ВеВ 1Р (Ав) ~ Р (А) Р О8)!- Для г > 0, е N и {оо} и случайного поля X = € определим коэффициенты сильного перемешивания

где верхняя грань берется по всем конечным множествам 1,3 С Ъ* таким, что р(1, .7) > г, |/| < и, 17| < V.

Теорема 1.2.1. Пусть функционал £ удовлетворяет условиям (А1) и (А2). Тогда коэффициенты перемешивания поля X = {Х^] € 1?} допускают оценку

где положительные постоянные С и с не зависят от и, V и г; А обозначает минимум из двух чисел.

Доказательство этого факта потребовало использования формулы Кэмпбелла-Сливняка. Напомним, что упомянутая формула является следствием свойств меры Кемпбелла для точечных процессов и распределения Пальма для пуассоновского процесса. Пусть В с ограниченное борелевское, / - ограниченная измеримая функция на произведении множеств М^ и пространства локально-конечных дискретных мер, П - пуассоновский процесс в постоянной интенсивности 1. Тогда выполняется соотношение

яьш ш

Формулировка закона повторного логарифма для случайного поля X потребует некоторых вспомогательных обозначений. Для фиксированного г > 0 рассмотрим множество

а(г, и, и) — вир а (а {X,-, г 6 1}, ст {X] Е 7})

а(г, и, у) < С(и А ь)е

,—СТ

= < п = (пх,..., щ) е : щ > Пп^, г = 1,..., <1

I т

Далее запись п —* оо будет обозначать, что щ —» оо, г = 1, ..., d. Теорема 1.2.2. Пусть функционал £ обладает свойствами (А1)-(А4) и выполняется условие

а2 := cov Xi) > 0. i6 zd

Тогда справедливо предельное соотношение

Ei<,<„*

limsup . . :■ = = 1 п.н., n-+co, neGT \j2da2 (n) log log (n)

где (n) = rii.. .-nd.

Для доказательства закона повторного логарифма потребовались моментные неравенства, центральная предельная теорема с оценкой скорости сходимости и максимальное неравенство.

Моментные оценки были получены за счет известных результатов для сильно перемешивающихся случайных полей (см., напр., книгу Дукана19).

Существует множество вариантов центральной предельной теоремы для случайных полей с перемешиванием. Данные результаты были установлены Булинским, Бенткусом, Дедекером, Сунклодасом и др. В диссертации использовался следующий результат Сунклодаса. Лемма 1.2.420. Пусть центрированное случайное поле X = {Xi,i €

0~сг

Ъ6-} таково, что Ь :— вир^- Е ]Х,-| < оо и а(г, и, у) < (и + у)ре р > 0. Пусть Z С - произвольное конечное множество, ¿>(£) = Х^ег Тогда для некоторой постоянной С, значение которой зависит от величины р и не зависит от множества Z, верна оценка

sup

iSR

<с

р( SW Г e-^dt

\y/VarS{Z) ~ J J-oo

_-Jill_logd(1+i) \Zl + bV{2+5) w1+W+2i) \Z\

(VaxS(Z))1+s^2 11 VaxS{Z) ^

< 1/2

19P. Doukhan, Mixing. Properties and examples, N.Y., Springer-Verlag, 1994.

20Й. Сунклодас, Оценка скорости сходимости в центральной предельной теореме

для слабозависимых случайных полей, Литовск. мат. сборн., 1985, 26(3), 541-559.

Максимальное неравенство для данного случайного поля было получено при помощи техники Вишуры21.

Лемма 1.2.7. Пусть последовательности (ßi)ien, таковы,

что а; ~ (1 + е) \/2a2dl log log Z, для некоторого е £ (О,1); ßi = о (а/); l/ßf —> О, Z —> ос, / € N. Тогда при всех достаточно больших п Е GT и некотором и > 0 справедливо следующее максимальное неравенство.

Р (max |Sm| > a(n)) < 2dP (|5„| > a(n) - 2 dß{n]) + С (n)~v,

где С не зависит от п.

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

Теорема 2.1.1. Пусть последовательность тп У оо, тп < п. Для любого 0 < г] < 1/2 существует такое вероятностное пространство и определенные на нем графы и G (п, т]^-), что

Р (|с („, ¿Ь) \ аЦ > ml+«— + д.) < "K + g^-"'),

где Вп - произвольная последовательность положительных чисел.

Для доказательства данного результата применен последовательный каплинг. Граф Эрдёша-Реньи рассматрен как эволюционный граф, к которому на каждом шаге добавляется одна новая вершина и случайное количество новых ребер. На каждом шаге построено совместное распределение добавляемых ребер, произведена оценка математического ожидания и дисперсии количества получившихся на данном шаге лишних ребер в графе Эрдёша-Реньи. Суммарное количество таких ребер оценено с помощью неравенства Маркова.

21М. J. Wichura, Inequalities with applications to the weak convergence of random processes with multi-dimensional time parameters, Ann. Math. Statist., 1969, 40, 681— 687.

Во второй части главы 2 оценивается вероятность локализации диаметра случайного графа преимущественного присоединения. Теорема 2.2.1. Пусть т > 2 фиксировано и 0 < е < 1/4. Тогда

Р (\diamlog log п/ log n - 1| > e) < nTe/2

при всех достаточно больших п.

Для доказательства данного результата потребовалось применить линеаризованную диаграмму хорд, введенную Болобашем и Риорда-ном.

Введем набор Х\,...,Х2n независимых случайных величин, равномерно распределенных на (0,1). Пусть Y{ = X2i-1 A X^i, Zi = 1 V X2i, i = 1,..., N. Рассмотрим вариационный ряд случайных величин Zi. Обозначим Ri = Z^ правые и L,- = Yf. Zj = Z^ - соответствующие левые концы интервалов.

Рассмотрим случайные величины Wo := О, W,к := Ящк, к = 1,... ,п и Wk := Wk — Wk-i- Для каждого к — 1,... ,п введем набор случайных величин Ik,и • • • 1 h,m по правилу

{h,i = J'j = {Wj-i < Lm{k-i)+i < Щ}, Э = 1, ■ • •, к, i = 1,..., т.

Пусть граф состоит из п вершин, и из каждой вершины г проведены ребера к вершинам с номерами kд, ..., Болобаш и Риордан показали, что следующий граф является графом преимущественного присоединения G'^. Весом вершины г € мы будем называть случайную величину иг,.

При доказательстве верхней оценки показано, что расстояние от некоторой случайной вершины до произвольной вершины графа не превосходит величины (1/2 -f е/2) log п/ log log п.

В ходе доказательства было использовано введенное Болобашем и Риорданом понятие полезной вершины.

Определение 2.2.1. Вершина г называется полезной тогда и только тогда, когда её вес Wi > (logп)2/п и г < n/(logn)5.

При доказательстве верхней оценки было показано, что с вероятностью 1 — 0(п_3£/'4) расстояние от произвольной вершины графа G™ до некоторой полезной вершины не превосходит 6 log log п, а рассто-

яние от прозвольной полезной вершины до некоторой случайной вершины £„, не превосходит (1/2 + е/3) к^п/к^к^п. Существование £п устанавливается в следующей лемме.

Лемма 2.2.3. Пусть константа С > 0 фиксирована. Пусть выполняется вспомогательное событие Е\. Тогда для некоторой постоянной 7 существует г такое, что и){ > С/(\/пlogп).

Третья глава диссертации посвящена моделированию случайных графов и их статистическому исследованию. В первой части третьей главы получен статистический тест адекватности модели случайного графа. Применено понятие среднего диаметра, использованное в работе Кумара и др.22 для исследования социальных сетей РНскг и УаЬоо!360.

Определение 3.1.1. Средним диаметром AvgDiam(G) называется случайная величина, равная расстоянию между двумя случайно и равномерно выбранными вершинами графа С.

Теорема 3.1.1. Пусть Щ - гипотеза о соответствии графа С распределению графа (3™. Для т,п> 3 и уровня значимости а имеет место следующая оценка

Р (АуёШат(С) < , 1ов" - Ь(т,п,а)|Я0 ) < а, V к^к^п 1 )

где

,, , loglogn + ^Mlogn-21ogf

b(m,n,a) = — -

log log n + 2 log (4m) Вероятность ошибки первого рода удалось оценить при помощи техники, аналогичной той, которую мы применили при выводе нижней оценки в теореме о локализации диаметра случайного графа преимущественного присоединения (теорема 2.2.1).

Во второй части главы 3 прозведено моделирование некоторых случайных графов. Для этого был использован пакет igraph 0.5.2, разработанный Габуром Чарди. Пакет написан на языке С, но имеет импле-ментацию для языка анализа статистической информации R. В данном

22R. Kumar, J. Novak, A. Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining, 2006, 611-617.

пакете имеются средства моделирования некоторых известных случайных графов. В диссертации представлены результаты моделирования графов Эрдёша-Реньи, Уоттса-Строгатца и графа преимущественного присоединения (модель Альберт-Барабаши). Для всех графов был вычислен диаметр и средний диаметр.

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

Работы автора по теме диссертации

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

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

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

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

[5] М. Musin, Diameter localization probability bound for random graph, Lviv, Abstracts of International. Conference SARD, 2009, 172-173.

Подписано в печать 23. //, 03 Формат 60x90 1/16. Усл. печ. л. 4,25 Тираж {00 экз. Заказ ¿6

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М. В. Ломоносова

Введение

Глава 1. Геометрические функционалы от точечных потоков

1.1 Закон повторного логарифма для последовательности объемов случайных множеств.

1.2 Закон повторного логарифма для сумм экспоненциально стабилизирующихся функционалов.

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

2.1 Каплинг случайного графа преимущественного присоединения и случайного графа Эрдёша-Реньи.

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

Глава 3. Статистическое исследование случайных графов.

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

3.2 Компьютерное моделирование некоторых случайных графов

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

Точечный случайный процесс, иногда называемый также иногда точечным потоком, позволяет описывать конфигурации случайных точек в 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 пусть T\j = а {Х{, 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.