Extreme Value Statistics for Evolving Random Networks
Our objective is to survey recent results concerning the evolution of random networks and related extreme value statistics, which are a subject of interest due to numerous applications. Our survey concerns the statistical methodology but not the structure of random networks. We focus on the problems...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-05-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/11/9/2171 |
| _version_ | 1797602200020582400 |
|---|---|
| author | Natalia Markovich Marijus Vaičiulis |
| author_facet | Natalia Markovich Marijus Vaičiulis |
| author_sort | Natalia Markovich |
| collection | DOAJ |
| description | Our objective is to survey recent results concerning the evolution of random networks and related extreme value statistics, which are a subject of interest due to numerous applications. Our survey concerns the statistical methodology but not the structure of random networks. We focus on the problems arising in evolving networks mainly due to the heavy-tailed nature of node indices. Tail and extremal indices of the node influence characteristics like in-degrees, out-degrees, PageRanks, and Max-linear models arising in the evolving random networks are discussed. Related topics like preferential and clustering attachments, community detection, stationarity and dependence of graphs, information spreading, finding the most influential leading nodes and communities, and related methods are surveyed. This survey tries to propose possible solutions to unsolved problems, like testing the stationarity and dependence of random graphs using known results obtained for random sequences. We provide a discussion of unsolved or insufficiently developed problems like the distribution of triangle and circle counts in evolving networks, or the clustering attachment and the local dependence of the modularity, the impact of node or edge deletion at each step of evolution on extreme value statistics, among many others. Considering existing techniques of community detection, we pay attention to such related topics as coloring graphs and anomaly detection by machine learning algorithms based on extreme value theory. In order to understand how one can compute tail and extremal indices on random graphs, we provide a structured and comprehensive review of their estimators obtained for random sequences. Methods to calculate the PageRank and PageRank vector are shortly presented. This survey aims to provide a better understanding of the directions in which the study of random networks has been done and how extreme value analysis developed for random sequences can be applied to random networks. |
| first_indexed | 2024-03-11T04:13:37Z |
| format | Article |
| id | doaj.art-d9aa0eb53688491982215549ad8af9ad |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-11T04:13:37Z |
| publishDate | 2023-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-d9aa0eb53688491982215549ad8af9ad2023-11-17T23:20:55ZengMDPI AGMathematics2227-73902023-05-01119217110.3390/math11092171Extreme Value Statistics for Evolving Random NetworksNatalia Markovich0Marijus Vaičiulis1V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 117997 Moscow, RussiaInstitute of Data Science and Digital Technologies, Vilnius University, Akademijos St. 4, LT-08663 Vilnius, LithuaniaOur objective is to survey recent results concerning the evolution of random networks and related extreme value statistics, which are a subject of interest due to numerous applications. Our survey concerns the statistical methodology but not the structure of random networks. We focus on the problems arising in evolving networks mainly due to the heavy-tailed nature of node indices. Tail and extremal indices of the node influence characteristics like in-degrees, out-degrees, PageRanks, and Max-linear models arising in the evolving random networks are discussed. Related topics like preferential and clustering attachments, community detection, stationarity and dependence of graphs, information spreading, finding the most influential leading nodes and communities, and related methods are surveyed. This survey tries to propose possible solutions to unsolved problems, like testing the stationarity and dependence of random graphs using known results obtained for random sequences. We provide a discussion of unsolved or insufficiently developed problems like the distribution of triangle and circle counts in evolving networks, or the clustering attachment and the local dependence of the modularity, the impact of node or edge deletion at each step of evolution on extreme value statistics, among many others. Considering existing techniques of community detection, we pay attention to such related topics as coloring graphs and anomaly detection by machine learning algorithms based on extreme value theory. In order to understand how one can compute tail and extremal indices on random graphs, we provide a structured and comprehensive review of their estimators obtained for random sequences. Methods to calculate the PageRank and PageRank vector are shortly presented. This survey aims to provide a better understanding of the directions in which the study of random networks has been done and how extreme value analysis developed for random sequences can be applied to random networks.https://www.mdpi.com/2227-7390/11/9/2171random networkevolutionPageRankMax-linear modeltail indexextremal index |
| spellingShingle | Natalia Markovich Marijus Vaičiulis Extreme Value Statistics for Evolving Random Networks Mathematics random network evolution PageRank Max-linear model tail index extremal index |
| title | Extreme Value Statistics for Evolving Random Networks |
| title_full | Extreme Value Statistics for Evolving Random Networks |
| title_fullStr | Extreme Value Statistics for Evolving Random Networks |
| title_full_unstemmed | Extreme Value Statistics for Evolving Random Networks |
| title_short | Extreme Value Statistics for Evolving Random Networks |
| title_sort | extreme value statistics for evolving random networks |
| topic | random network evolution PageRank Max-linear model tail index extremal index |
| url | https://www.mdpi.com/2227-7390/11/9/2171 |
| work_keys_str_mv | AT nataliamarkovich extremevaluestatisticsforevolvingrandomnetworks AT marijusvaiciulis extremevaluestatisticsforevolvingrandomnetworks |