Вестник БГУ. Математика, информатика
Библиографическое описание:
, , О РАСПРЕДЕЛЕНИИ ЧИСЛА ЦЕПОЧЕК СПЕЦИАЛЬНОГО ВИДА В РАЗМЕЧЕННОМ ПОЛНОМ ГРАФЕ // Вестник БГУ. Математика, информатика. - 2023. №2. . - С. 3-13.
Заглавие:
О РАСПРЕДЕЛЕНИИ ЧИСЛА ЦЕПОЧЕК СПЕЦИАЛЬНОГО ВИДА В РАЗМЕЧЕННОМ ПОЛНОМ ГРАФЕ
Финансирование:
Коды:
Аннотация:
В работе рассматривается распределение числа цепочек из одинаковых меток вершин полного графа, в котором метки присваиваются вершинам случайно в соответствии с заданным распределением на конечном множестве и независимо друг от друга. Доказана центральная предельная теорема для числа таких цепочек, когда число вершин стремится к бесконечности, а длина цепочки остается фиксированной, в том числе в схеме серий (когда вероятности меток, присваеваемых вершинам, могут меняться с ростом числа вершин графа). Для части области изменения параметров построена оценка расстояния между функцией распределения числа цепочек указанного вида и функцией распределения стандартного нормального закона в равномерной метрике. При помощи численного моделирования установлено, что нормальная аппроксимация может применяться к распределению числа цепочек меток вершин на полных графах с числом вершин порядка сотни.
Ключевые слова:
полный граф, случайные метки, пути на графах, нормальное распределение, центральная предельная теорема.
Список литературы:
Jorgensen P., Tian F. Duality for gaussian processes from random signed measures // Mathematical Analysis and Applications: Selected Topics. 2018. P. 23-56. DOI:10.1002/9781119414421.ch2
Hu C., Cheng L., Sepulcre J., Johnson K., Fakhri G., Lu Y., Li Q. A spectral graph regression model for learning brain connectivity of Alzheimer’s disease // PLoS One. 2015. Vol. 10, № 5. P. 24. DOI: 10.1371/journal.pone.0128136
Chen S., Zhang Z., Mo C., Wu Q., Kochunov P., Hong L. Characterizing the Complexity of Weighted Networks via Graph Embedding and Point Pattern Analysis // Entropy. 2020. Vol. 22, № 9. P. 12. DOI: 10.3390/e22090925
Liemhetcharat S., Veloso M. Weighted synergy graphs for effective team formation with heterogeneous ad hoc agents // Artificial Intelligence. 2014. Vol. 208. P. 41-65. DOI: 10.1016/j.artint.2013.12.002
He M., Glasser J., Pritchard N., Bhamidi S., Kaza N. Demarcating geographic regions using community detection in commuting networks with significant self-loops // PLoS One. 2020. Vol. 15, № 4. P. 31. DOI: 10.1371/journal.pone.0230941
Hassin R., Zemel E. On Shortest Paths in Graphs with Random Weights // Mathematics of Operations Research. 1985. Vol. 10, № 4. P. 557–564. DOI: 10.1287/moor.10.4.557
Janson S. One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights // Combinatorics, Probability and Computing. 1999. Vol. 8, № 4. P. 347-361. DOI: 10.1017/S0963548399003892
Knisley J., Knisley D. Vertex-weighted graphs and their applications // Utilitas Mathematica. 2014. Vol. 94, № 7. P. 16.
Карпов Д. В. Теория графов. Москва: Изд-во МЦНМО, 2022. 560 с. Текст: непосредственный.
Janson S. Normal Convergence by Higher Semiinvariants with Applications to Sums of Dependent Random Variables and Random Graphs // The Annals of Probability. 1988. Vol. 16, № 1. P. 305-312. DOI: 10.1214/aop/1176991903
Baldi P., Rinott Y. On Normal Approximations of Distributions in Terms of Dependency Graphs // The Annals of Probability. 1989. Vol. 17, № 4. P. 1646–1650. DOI: 10.1214/aop/1176991178
Hu C., Cheng L., Sepulcre J., Johnson K., Fakhri G., Lu Y., Li Q. A spectral graph regression model for learning brain connectivity of Alzheimer’s disease // PLoS One. 2015. Vol. 10, № 5. P. 24. DOI: 10.1371/journal.pone.0128136
Chen S., Zhang Z., Mo C., Wu Q., Kochunov P., Hong L. Characterizing the Complexity of Weighted Networks via Graph Embedding and Point Pattern Analysis // Entropy. 2020. Vol. 22, № 9. P. 12. DOI: 10.3390/e22090925
Liemhetcharat S., Veloso M. Weighted synergy graphs for effective team formation with heterogeneous ad hoc agents // Artificial Intelligence. 2014. Vol. 208. P. 41-65. DOI: 10.1016/j.artint.2013.12.002
He M., Glasser J., Pritchard N., Bhamidi S., Kaza N. Demarcating geographic regions using community detection in commuting networks with significant self-loops // PLoS One. 2020. Vol. 15, № 4. P. 31. DOI: 10.1371/journal.pone.0230941
Hassin R., Zemel E. On Shortest Paths in Graphs with Random Weights // Mathematics of Operations Research. 1985. Vol. 10, № 4. P. 557–564. DOI: 10.1287/moor.10.4.557
Janson S. One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights // Combinatorics, Probability and Computing. 1999. Vol. 8, № 4. P. 347-361. DOI: 10.1017/S0963548399003892
Knisley J., Knisley D. Vertex-weighted graphs and their applications // Utilitas Mathematica. 2014. Vol. 94, № 7. P. 16.
Карпов Д. В. Теория графов. Москва: Изд-во МЦНМО, 2022. 560 с. Текст: непосредственный.
Janson S. Normal Convergence by Higher Semiinvariants with Applications to Sums of Dependent Random Variables and Random Graphs // The Annals of Probability. 1988. Vol. 16, № 1. P. 305-312. DOI: 10.1214/aop/1176991903
Baldi P., Rinott Y. On Normal Approximations of Distributions in Terms of Dependency Graphs // The Annals of Probability. 1989. Vol. 17, № 4. P. 1646–1650. DOI: 10.1214/aop/1176991178
Статья.pdf