Кластерный коэффициент в модели пространственного предпочтительного присоединения

 
Код статьиS086956520000816-0-1
DOI10.31857/S086956520000041-8
Тип публикации Статья
Статус публикации Опубликовано
Авторы
Аффилиация: Московский физико-технический институт (государственный университет)
Аффилиация: Университет Райерсона
Адрес: Торонто, Канада
Аффилиация: Варшавская школа экономики
Адрес: Варшава, Польша
Аффилиация:
Московский физико-технический институт (государственный университет)
Яндекс
Аффилиация: Московский физико-технический институт (государственный университет)
Название журналаДоклады Академии наук
ВыпускТом 481 Номер 1
Страницы10-13
Аннотация

  

Ключевые слова
Источник финансированияРабота выполнена при поддержке гранта Президента МК-527.2017.1
Получено09.09.2018
Дата публикации13.09.2018
Кол-во символов9047
Цитировать  
100 руб.
При оформлении подписки на статью или выпуск пользователь получает возможность скачать PDF, оценить публикацию и связаться с автором. Для оформления подписки требуется авторизация.

Оператором распространения коммерческих препринтов является ООО «Интеграция: ОН»

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.
1

Введение

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

2 Так, например, диаметр случайного дистанционного графа частично изучен в работе [3]. Часто также моделирование сложных сетей используют для анализа социальных сетей. В работе [2] представлен результат о времени смешивания марковских цепей при построении искусственных социальных графов.
3 Наиболее изученным свойством сложных сетей является распределение их степеней вершин. Для большинства реальных сетей это распределение хорошо приближается степенным распределением с параметром , который обычно находится в интервале [11]. Другое важное свойство реальных сетей — их кластерная структура. Одним из способов ее измерения является кластерный коэффициент. В некотором смысле его значение есть вероятность для двух соседей одной вершины быть смежными между собой. В литературе предложено два классических определения: средний локальный кластерный коэффициент и глобальный кластерный коэффициент (формальные определения даны в разделе 3). Было показано, что во многих реальных сетях оба этих коэффициента стремятся к положительной константе с увеличением размера сети [10].
4 Предметом данного исследования является кластерная структура модели пространственного предпочтительного присоединения (Spatial Preferential Attachment, сокращенно SPA), которая была предложена в работе [1]. Эта модель естественным образом сочетает в себе предпочтительное присоединение и геометрическую составляющую; формальное определение дано в разделе 2.1. Особенно нас будет интересовать средний локальный кластерный коэффициент как функция от степени вершины. Модель SPA хорошо изучена и было показано, что она схожа с реальными сетями во многих аспектах. Например, в [1] доказан степенной закон распределения степеней вершин (больше деталей в разделе 2.2). Кластерный коэффициент дляэтой модели не был изучен, хотя некоторые кластерные свойства проанализированы в [4]. В работах [4] и [5] доказано, что средний локальный кластерный коэффициент сходится по вероятности к положительной константе если и только если распределение степеней вершин имеет конечную дисперсию.
5

Модель SPA

6

Определения

Как было сказано ранее, основным объектом исследования в данной работе является модель SPA, впервые представленная в работе [1]. Эта модель комбинирует предпочтительное присоединение и структуру метрического пространства, в котором лежат вершины.Достигается это за счет наличия у каждой вершины “сферы влияния”. Параметрами модели являются вероятность создания ребра и две константы , где , , которые отвечают за объем сфер влияния вершин. Вершины в данной модели — это точки -мерного единичного гиперкуба с торической метрикой на нем, индуцированной нормой , т.е.

Всего подписок: 0, всего просмотров: 1555

Оценка читателей: голосов 0

1. Aiello, W., Bonato, A., Cooper, C., Janssen, J., and Pral at, P. (2009). A spatial web graph model with local influence regions. Internet Mathematics, 5:175–196.

2. Avrachenkov, K., Iskhakov, L., and Mironov, M. (2016). On mixing in pairwise markov random fields with application to social networks. In 13th International Workshop, WAW 2016, Montreal, QC, Canada, December 14–15, 2016, Proceedings, pages 127–139. Springer.

3. Iskhakov, L. and Mironov, M. (2017). Diameters of random distance graphs. Journal of Mathematical Sciences, 227(4):407–418.

4. Jacob, E. and Mörters, P. (2013). A spatial preferential attachment model with local clustering. In International Workshop on Algorithms and Models for the Web-Graph, pages 14–25. Springer.

5. Jacob, E., Mörters, P., et al. (2015). Spatial preferential attachment networks: Power laws and clustering coefficients. The Annals of Applied Probability, 25(2):632–662.

6. Janssen, J., Hurshman, M., and Kalyaniwalla, N. (2013a). Model selection for social networks using graphlets. Internet Mathematics, 8(4):338–363.

7. Janssen, J., Pral at, P., and Wilson, R. (2013b). Geometric graph properties of the spatial preferred attachment model. Advances in Applied Mathematics, 50:243–267.

8. Janssen, J., Pral at, P., and Wilson, R. (2016). Non-uniform distribution of nodes in the spatial preferential attachment model. Internet Mathematics, 12(1–2):121–144.

9. Krot, A. and Prokhorenkova, L. O. (2015). Local clustering coefficient in generalized preferential attachment models. In International Workshop on Algorithms and Models for the Web-Graph, pages 15–28. Springer.

10. Newman, M. E. (2003). The structure and function of complex networks. SIAM review, 45(2):167–256.

11. Newman, M. E. (2005). Power laws, pareto distributions and zipf’s law. Contemporary physics, 46(5):323–351.

12. Prokhorenkova,L.O.(2017). Generalresultsonpreferentialattachmentandclustering coefficient. Optimization Letters, 11(2):279–298.

13. Raigorodskii, A. (2017). Small subgraphs in preferential attachment networks. Optimization Letters, 11(2):249–257.

14. Ravasz, E. and Baraba´si, A.-L. (2003). Hierarchical organization in complex networks. Physical Review E, 67(2):026112.

15. Vázquez, A., Pastor-Satorras, R., and Vespignani, A. (2002). Large-scale topological and dynamical properties of the internet. Physical Review E, 65(6):066130.

Система Orphus

Загрузка...
Вверх