High degree vertices in the power of choice model combined with preferential attachment

В работе найдена ассимптотика первых $k$ максимумов распределения степеней в графе для модели предпочтительного присоединения с выбором. В данной модели на каждом шаге добавляется одна вершина. Затем мы случайным образом выбираем $d$ $(d>2)$ вершин, и проводим ребро из новой вершины в вершину с наибольшей (из выбранных вершин) степенью. Известно, что в данной модели максимальная степень вершины в графе растет линейно относительно общего числа вершин, в то время как в моделях предпочтительного присоединения без выбора первые $k$ максимумов распределения степеней вершин растут сублинейно с одинаковым показателем. Доказано, что степени $k$-ых по величине степени вершин растут сублинейно относительно размера графа. Доказательство использует существование в графе выделенных вершин и мартингальную технику.