Числовые характеристики структур сетей связи
Ключевые слова:
сеть связи, граф, структура, инвариант, матрица смежностей, матрица инциденций, мини-код, макси-кодАннотация
При решении задач, связанных с анализом и синтезом сетей связи по показателям устойчивости, особое место занимают вопросы описания структур сетей связи с позиции теории графов. При этом традиционным является подход, подразумевающий формальное представление телекоммуникационной сети как неориентированного графа. В данной работе рассматриваются возможные варианты представления графов не в форме их диаграмм (рисунков в двумерной плоскости), а на основе различного набора чисел, либо же вообще одного числа. Подобное описание в ряде случаев позволяет существенно упростить процедуры, связанные с вычислением показателей не только устойчивости исходной сети, но иногда и других показателей качества. При этом появляется возможность алгоритмического решения задач синтеза структур телекоммуникационных сетей, а не только переборными визуальными методами. Приведены примеры расчетов характеристик структур сетей связи для простейших вариантов. Кроме того, в работе не только описан аналитический аппарат формирования числовых описаний структур сетей, но и представлены соотношения, выполняющие трансформацию подобных описаний друг в друга.Литература
1. Форман Дж. Много цифр: Анализ больших данных при помощи Excel // М.: Альпина Паблишер. 2016. 464 с.
2. Остроумова Л.А. Математические ожидания k-х входящих степеней вершин в случайных графах в модели Боллобаша-Риордана // Труды Московского физико- технического института. 2012. Т. 4. № 1(13). C. 29–40.
3. Лакеев А. В. Элементы теории обыкновенных графов : учеб. пособие // Иркутск: Изд-во ИГУ. 2014. 83 с.
4. Колганов А.С. Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров // Параллельные вычислительные технологии (ПаВТ’2016). 2016. С. 530–543.
5. Arefin A.S., Riveros C., Berretta R., Moscato P. kNN-MST-Agglomerative: A fast and scalable graph-based data clustering approach on GPU // 7th International Conference on Computer Science & Education (ICCSE). 2012. pp. 585–590.
6. Chen P.-Yu, Choudhury S., Hero A.O. Multi-centrality graph spectral decompositions and their application to cyber intrusion detection. 2016. URL: http://de.arxiv.org/abs/1512.07372v1. (дата обращения: 24.01.2017).
7. Kalofolias S.V., Bresson X., Bronstein M.M., Vandergheynst P. Robust principal component analysis on graphs. CoRR. 2015. vol. abs/1504.06151. URL: http://arxiv.org/abs/1504.06151. (дата обращения: 24.01.2017).
8. Кристофидес Н. Теория графов: пер. с англ. // М.: Мир. 1978. 432 с.
9. Дудник Б.Я., Овчаренко В. Ф. Надежность и живучесть систем // М.: Радио и связь. 1984. 216 с.
10. Татт У. Теория графов: пер. с англ // М.: Мир. 1988. 424 с.
11. Харари Ф. Теория графов: пер. с англ., изд. 2-е // М.: Едиториал УРСС. 2003. 296 с.
12. Зыков А.А. Основы теории графов // М.: Наука. 1987. 384 с.
13. Батенков К.А. Особенности оценки качества функционирования сетей связи // Ресурсоэффективные системы в управлении и контроле: взгляд в будущее: сборник научных трудов V Международной конференции школьников, студентов, аспирантов, молодых ученых. 2016. Том 1. C. 30–31.
14. Батенков К.А. Об анализе живучести сетей связи на основе вероятностного подхода // Неделя науки СПбПУ: материалы научной конференции с междунароодным участием. СПб.: Изд-во Политехн. ун-та. 2016. C. 6–8.
15. Егунов М.М., Шувалов В.П. Анализ структурной надёжности транспортной сети // Вестник СибГУТИ. 2012. №1. С. 54–60.
16. Tsitsiashvili G.Sh. Complete calculation of disconnection probability in planar graphs // Reliability: Theory and Applications. 2012. vol.1. no.1. pp. 154–159.
17. Bollobás B., Riordan O. The diameter of a scale-free random graph // Combinatorica. 2004. vol. 24. no. 1. pp. 5–34.
18. Bollobás B., Riordan O., Spencer J., Tusnády G. The degree sequence of a scale-free random graph process // Random Structures Algorithms. 2001. vol. 18. no.3. pp. 279–290. pp. 40–73.
19. Grechnikov E.A. An estimate for the number of edges between vertices of given degrees in random graphs in the Bollob´ as–Riordan model // Moscow Journal of Combinatorics and Number Theory. 2011. vol. 1. no. 2. pp. 40–73.
20. Drinea E., Enachescu M., Mitzenmacher M. Variations on random graph models for the web // Technical report. Department of Computer Science. Harvard University. 2001.
21. Dorogovtsev S.N., Mendes J.F.F., Samukhin A.N. Structure of growing networks with preferential linking // Phys. rev. lett. 2000. vol. 85. pp. 4633.
22. Kumar R. et al. Stochastic models for the web graph // Proc. 41st Symposium on Foundations of Computer Science. 2000.
23. Батенков К. А. Устойчивость сетей связи // Орел: Академия ФСО России. 2017. 277 с.
2. Остроумова Л.А. Математические ожидания k-х входящих степеней вершин в случайных графах в модели Боллобаша-Риордана // Труды Московского физико- технического института. 2012. Т. 4. № 1(13). C. 29–40.
3. Лакеев А. В. Элементы теории обыкновенных графов : учеб. пособие // Иркутск: Изд-во ИГУ. 2014. 83 с.
4. Колганов А.С. Параллельная реализация алгоритма поиска минимальных остовных деревьев с использованием центрального и графического процессоров // Параллельные вычислительные технологии (ПаВТ’2016). 2016. С. 530–543.
5. Arefin A.S., Riveros C., Berretta R., Moscato P. kNN-MST-Agglomerative: A fast and scalable graph-based data clustering approach on GPU // 7th International Conference on Computer Science & Education (ICCSE). 2012. pp. 585–590.
6. Chen P.-Yu, Choudhury S., Hero A.O. Multi-centrality graph spectral decompositions and their application to cyber intrusion detection. 2016. URL: http://de.arxiv.org/abs/1512.07372v1. (дата обращения: 24.01.2017).
7. Kalofolias S.V., Bresson X., Bronstein M.M., Vandergheynst P. Robust principal component analysis on graphs. CoRR. 2015. vol. abs/1504.06151. URL: http://arxiv.org/abs/1504.06151. (дата обращения: 24.01.2017).
8. Кристофидес Н. Теория графов: пер. с англ. // М.: Мир. 1978. 432 с.
9. Дудник Б.Я., Овчаренко В. Ф. Надежность и живучесть систем // М.: Радио и связь. 1984. 216 с.
10. Татт У. Теория графов: пер. с англ // М.: Мир. 1988. 424 с.
11. Харари Ф. Теория графов: пер. с англ., изд. 2-е // М.: Едиториал УРСС. 2003. 296 с.
12. Зыков А.А. Основы теории графов // М.: Наука. 1987. 384 с.
13. Батенков К.А. Особенности оценки качества функционирования сетей связи // Ресурсоэффективные системы в управлении и контроле: взгляд в будущее: сборник научных трудов V Международной конференции школьников, студентов, аспирантов, молодых ученых. 2016. Том 1. C. 30–31.
14. Батенков К.А. Об анализе живучести сетей связи на основе вероятностного подхода // Неделя науки СПбПУ: материалы научной конференции с междунароодным участием. СПб.: Изд-во Политехн. ун-та. 2016. C. 6–8.
15. Егунов М.М., Шувалов В.П. Анализ структурной надёжности транспортной сети // Вестник СибГУТИ. 2012. №1. С. 54–60.
16. Tsitsiashvili G.Sh. Complete calculation of disconnection probability in planar graphs // Reliability: Theory and Applications. 2012. vol.1. no.1. pp. 154–159.
17. Bollobás B., Riordan O. The diameter of a scale-free random graph // Combinatorica. 2004. vol. 24. no. 1. pp. 5–34.
18. Bollobás B., Riordan O., Spencer J., Tusnády G. The degree sequence of a scale-free random graph process // Random Structures Algorithms. 2001. vol. 18. no.3. pp. 279–290. pp. 40–73.
19. Grechnikov E.A. An estimate for the number of edges between vertices of given degrees in random graphs in the Bollob´ as–Riordan model // Moscow Journal of Combinatorics and Number Theory. 2011. vol. 1. no. 2. pp. 40–73.
20. Drinea E., Enachescu M., Mitzenmacher M. Variations on random graph models for the web // Technical report. Department of Computer Science. Harvard University. 2001.
21. Dorogovtsev S.N., Mendes J.F.F., Samukhin A.N. Structure of growing networks with preferential linking // Phys. rev. lett. 2000. vol. 85. pp. 4633.
22. Kumar R. et al. Stochastic models for the web graph // Proc. 41st Symposium on Foundations of Computer Science. 2000.
23. Батенков К. А. Устойчивость сетей связи // Орел: Академия ФСО России. 2017. 277 с.
Опубликован
2017-07-03
Как цитировать
Батенков, К. А. (2017). Числовые характеристики структур сетей связи. Труды СПИИРАН, 4(53), 5-28. https://doi.org/10.15622/sp.53.1
Раздел
Теоретическая и прикладная математика
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
