Аннотация:
В работе найдена ассимптотика первых k максимумов распределения степеней в графе для модели предпочтительного присоединения с выбором. В данной модели на каждом шаге добавляется одна вершина. Затем мы случайным образом выбираем d(d>2) вершин, и проводим ребро из новой вершины в вершину с наибольшей (из выбранных вершин) степенью. Известно, что в данной модели максимальная степень вершины в графе растет линейно относительно общего числа вершин, в то время как в моделях предпочтительного присоединения без выбора первые k максимумов распределения степеней вершин растут сублинейно с одинаковым показателем. Доказано, что степени k-ых по величине степени вершин растут сублинейно относительно размера графа. Доказательство использует существование в графе выделенных вершин и мартингальную технику.
Поступила в редакцию: 30.08.2016 Исправленный вариант: 17.03.2017
Реферативные базы данных:
Тип публикации:
Статья
УДК:519.17
Язык публикации: английский
Образец цитирования:
Yu. Malyshkin, “High degree vertices in the power of choice model combined with preferential attachment”, Вестник ТвГУ. Серия: Прикладная математика, 2017, no. 1, 31–43
\RBibitem{Mal17}
\by Yu.~Malyshkin
\paper High degree vertices in the power of choice model combined with preferential attachment
\jour Вестник ТвГУ. Серия: Прикладная математика
\yr 2017
\issue 1
\pages 31--43
\mathnet{http://mi.mathnet.ru/vtpmk121}
\crossref{https://doi.org/10.26456/vtpmk121}
\elib{https://elibrary.ru/item.asp?id=28786645}