All
 
|
 
 


Cluster Coefficient in the Spatial Preferred Connection Model
 
PIIS086956520000816-0-1
DOI10.31857/S086956520000041-8
Publication type Article
Status Published
Authors
Lenar Iskhakov 
Affiliation: Moscow Institute of Physics and Technology (State University)
Pawel Pralat
Affiliation: Ryerson University
Address: Toronto, Canada
Bogumil Kaminski
Affiliation: Warsaw School of Economics
Address: Warsaw, Poland
Liudmila Prokhorenkova
Affiliation:
Moscow Institute of Physics and Technology (State University)
Yandex
Maksim Mironov
Affiliation: Moscow Institute of Physics and Technology (State University)
Journal nameDoklady Akademii nauk
EditionVolume 481 Issue 1
Pages10-13
Abstract

  

Keywords
Received09.09.2018
Publication date13.09.2018
Number of characters9047
Cite  
100 rub.
When subscribing to an article or issue, the user can download PDF, evaluate the publication or contact the author. Need to register.
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной

Table of contents

Введение
Модель SPA
Определения
Свойства модели
Кластерный коэффициент
Результаты
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]. Эта модель комбинирует предпочтительное присоединение и структуру метрического пространства, в котором лежат вершины.Достигается это за счет наличия у каждой вершины “сферы влияния”. Параметрами модели являются вероятность создания ребра и две константы , где , , которые отвечают за объем сфер влияния вершин. Вершины в данной модели — это точки -мерного единичного гиперкуба с торической метрикой на нем, индуцированной нормой , т.е.

Number of purchasers: 0, views: 1707

Readers community rating: votes 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

Loading...
Up