|
Теория вероятностей и математическая статистика
High degree vertices in the power of choice model combined with preferential attachment
[Вершины с наибольшими степенями в модели предпочтительного присоединения с выбором]
Yu. Malyshkin Tver State University, Tver
Аннотация:
В работе найдена ассимптотика первых $k$ максимумов распределения степеней в графе для модели предпочтительного присоединения с выбором. В данной модели на каждом шаге добавляется одна вершина. Затем мы случайным образом выбираем $d$ $(d>2)$ вершин, и проводим ребро из новой вершины в вершину с наибольшей (из выбранных вершин) степенью. Известно, что в данной модели максимальная степень вершины в графе растет линейно относительно общего числа вершин, в то время как в моделях предпочтительного присоединения без выбора первые $k$ максимумов распределения степеней вершин растут сублинейно с одинаковым показателем. Доказано, что степени $k$-ых по величине степени вершин растут сублинейно относительно размера графа. Доказательство использует существование в графе выделенных вершин и мартингальную технику.
Ключевые слова:
случайные графы, предпочтительное присоединение, выбор.
Поступила в редакцию: 30.08.2016 Исправленный вариант: 17.03.2017
Образец цитирования:
Yu. Malyshkin, “High degree vertices in the power of choice model combined with preferential attachment”, Вестник ТвГУ. Серия: Прикладная математика, 2017, no. 1, 31–43
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vtpmk121 https://www.mathnet.ru/rus/vtpmk/y2017/i1/p31
|
Статистика просмотров: |
Страница аннотации: | 228 | PDF полного текста: | 149 | Список литературы: | 29 |
|