Теория ресурсных сетей
Аннотация и ключевые слова
Аннотация (русский):
Излагается новая модель распространения однородных ресурсов – ресурсная сеть – и исследуются ее динамические свойства. Ресурсная сеть – это ориентированный граф, ребра которого имеют положительные пропускные способности. Каждая вершина может хранить неограниченное количество ресурса. Сеть функционирует в дискретном времени. Суммарное количество ресурса во время функционирования сети не меняется. В момент t каждая вершина отдает ресурс смежным вершинам по одному из двух правил: если ресурса в вершине не меньше, чем сумма пропускных способностей всех ее исходящих ребер, вершина отдает «все, что может», т.е. пропускные способности ее выходящих ребер используются полностью; в противном случае вершина отдает весь свой ресурс, распределяя его пропорционально пропускным способностям. Для каждой сети существует порог Т суммарного ресурса: поведение сети при «малом» (меньшем Т) и «большом» ресурсе оказывается существенно различным. Если в сети имеются источники (вершины, у которых суммарная входная пропускная способность меньше выходной) и приемники (у которых суммарная входная пропускная способность больше выходной), то при большом ресурсе весь ресурс, превосходящий Т, в конечном счете достается некоторым приемникам (аттракторам). Предлагается матричная классификация ресурсных сетей по двум основаниям: по структуре графа сети, и по пропускным способностям. Общая схема исследования для всех классов ресурсных сетей одинакова: доказывается существование (или отсутствие) предельного состояния и предельного потока, решаются задачи их вычисления при различных начальных состояниях и значениях суммарного ресурса, демонстрируется различие в поведении при малом и большом ресурсе. Однако методы решения этих задач и конкретные результаты для разных классов сетей существенно различны.

Ключевые слова:
ресурсная сеть, графовая динамическая модель, сетевая модель, пороговая модель, марковские процессы, предельное состояние, устойчивость, поток, рассеяние на графах.
Текст

Текст

Спислит

1. Агаев Р.П., Чeботарев П.Ю. Матрица максимальных исходя-щих лесов орграфа и ее применения // Автоматика и телемеха-ника. – 2000. – № 9. – С. 15–43.

2. Агаев Р.П., Чeботарев П.Ю. Остовные леса орграфа и их при-менение // Автоматика и телемеханика. – 2001. – № 3. – С. 108–133.

3. Агаев Р.П., Чeботарев П.Ю. О нахождении собственного про-ектора и компонент матрицы // Автоматика и телемеханика. – 2002. – № 10. – С. 3–12.

4. Агаев Р.П., Чеботарев П.Ю. Сходимость и устойчивость в за-дачах согласования характеристик (обзор базовых результатов) / Управление большими системами. Специальный выпуск 30.1 «Сетевые модели в управлении». – М.: ИПУ РАН, 2010. – С. 470–505.

5. Агаев Р.П., Чeботарев П.Ю. Метод проекции в задаче о кон-сенсусе и регуляризованный предел степеней стохастической матрицы // Автоматика и телемеханика. – 2011. – № 12. – С. 38–59.

6. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоко-вые алгоритмы. – М.: Наука, 1975. – 119 с.

7. Барон С.А., Введение в теорию суммируемости рядов. – 2-е изд.. – Таллин, 1977. – 280 с.

8. Бурман Ю.М. Многочлен Татта и модель случайных кластеров, Матем. просв., сер. 3, 11, – М.: МЦНМО, 2007. – С. 47–60.

9. Басангова Е.О., Ерусалимский Я.М. Смешанная достижимость на частично ориентированных графах // Деп. в ВИНИТИ. – 1982. – № 5892-82.

10. Басангова Е.О., Ерусалимский Я.М. Различные виды смешан-ной достижимости // Алгебра и дискретная математика. Эли-ста, КГУ. – 1985. – С. 70–75.

11. Гантмахер Ф.Р. Теория матриц. – М.: Физматлит, 2004. – 560 с.

12. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Социальные сети. Модели информационного влияния, управления и проти-воборства. – М.: Изд-во физико-математической литературы, 2010. – 228 с.

13. Губанов Д.А., Новиков Д.А. Модели унифицированного ин-формационного управления в однородных социальных сетях / Управление большими системами. Специальный выпуск 30.1 «Сетевые модели в управлении». – М.: ИПУ РАН, 2010. – С. 722–742.

14. Ерзин А.И., Тахонов И.И. Задача поиска сбалансированного потока // Сибирский журнал индустриальной математики. – 2006. – Т. IX, № 4 (28). – С. 50–63.

15. Ерзин А.И., Тахонов И.И. Равновесное распределение ресурсов в сетевой модели // Сибирский журнал индустриальной математики. – 2005. – Т. VIII, № 3(23). – С. 58–68.

16. Ерусалимский Я.М. Потоки в сетях с нестандартной достижи-мостью // Известия вузов. Северо-Кавказский регион. Ест. нау-ки. – 2012. – № 1. – С. 5–7.

17. Ерусалимский Я.М. Общий метод решения задач о достижимо-сти на ориентированных графах // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. – 2000. – № 3. – С. 62–63.

18. Ерусалимский Я.М., Петросян А.Г. Многопродуктовые потоки в сетях с нестандартной достижимостью // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. – 2005. – № 6. – С. 8–16.

19. Ерусалимский Я.М., Петросян А.Г. Случайные процессы в сетях с биполярной магнитностью // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. – 2005. – № 11. – С. 10–16.

20. Ерусалимский Я.М., Скороходов В.А. Общий подход к нестан-дартной достижимости на графах.// Известия вузов. Сев.-Кавк. Регион. Естест. Науки. 2005, Спецвыпуск. Псевдодифференциальные уравнения и некоторые проблемы математической физики. — С. 64–67.

21. Ерусалимский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. – 2003. – № 2. – С. 3–5.

22. Ерусалимский Я.М., Скороходов В.А., Кузьминова М.В., Пет-росян А.Г. Графы с нестандартной достижимостью: задачи, приложения. – Ростов н/Д.: Южный федеральный университет, 2009. – 195 c.

23. Ерусалимский Я.М., Водолазов Н.Н. Нестационарный поток в сети // Вест. ДГТУ. – 2009. – Т. 9. – № 3. – C. 402–409.

24. Ерусалимский Я.М., Водолазов Н.Н. Максимальный всплеск в сети и максимальный объём сети // Изв. ВУЗов. Северо-Кавказ. регион. Естеств. науки. – 2010. – № 6. – C. 9–13.

25. Жилякова Л.Ю. Несимметричные ресурсные сети. I. Процессы стабилизации при малых ресурсах // Автоматика и телемеха-ника. – 2011. – № 4. – С. 133–143.

26. Жилякова Л.Ю. Применение ресурсных сетей для моделирова-ния распространения веществ в водной среде // Проблемы управления. – 2011. – № 2. – С. 46–51.

27. Жилякова Л.Ю. Полные несимметричные ресурсные сети. Случай одного приемника // Изв. ВУЗов. Северо-Кавказ. реги-он. Естеств. науки. – 2011. – № 4 (164). – С. 14–18.

28. Жилякова Л.Ю. Несимметричные ресурсные сети. II. Потоки при больших ресурсах и их стабилизация // Автоматика и те-лемеханика. – 2012. – № 6. – С. 103–118.

29. Жилякова Л.Ю. Несимметричные ресурсные сети. III. Исследование предельных состояний // Автоматика и телемеханика. – 2012. – № 7. – С. 67–77.

30. Жилякова Л.Ю. Исследование эйлеровых ресурсных сетей / Управление большими системами. – Вып. 41. – М.: ИПУ РАН, 2013. – С. 28–50.

31. Жилякова Л.Ю. Эргодические циклические ресурсные сети. I. Колебания и равновесные состояния при малых ресурсах / Управление большими системами. – Вып. 43. – М.: ИПУ РАН, 2013. – С. 34–54.

32. Жилякова Л.Ю. Эргодические циклические ресурсные сети. II. Большие ресурсы / Управление большими системами. – Вып. 45. – М.: ИПУ РАН, 2013. – С. 6–29.

33. Жилякова Л.Ю. Управление предельными состояниями в по-глощающих ресурсных сетях // Проблемы управления. – 2013. – № 3. – С. 51–59.

34. Жилякова Л.Ю. Графовые динамические модели и их свойства // Автоматика и телемеханика. – 2015. – № 8. – С. 115 – 139.

35. Жилякова Л.Ю. Ресурсная сеть с ограничением на ёмкость ат-тракторов // Управление большими системами. – Вып. 58. – М.: ИПУ РАН, 2015. – С. 67–89.

36. Жилякова Л.Ю. Ресурсные сети с ограничениями на ёмкость аттракторов. Формальные характеристики // Управление боль-шими системами. – Вып. 59. – М.: ИПУ РАН, 2016. – С. 72–119.

37. Жилякова Л.Ю. Распределение ресурса между аттракторами в регулярных несимметричных ресурсных сетях // Управление большими системами. – Вып. 60. – М.: ИПУ РАН, 2016. – С. 82–118.

38. Кемени Дж., Снелл Дж. Конечные цепи Маркова. – М.: Наука, 1970. – 272 с.

39. Кочкаров А.А., Салпагаров М.Б., Кочкаров Р.А. Моделирова-ние разрушения сложных систем с ациклической структурой / Управление большими системами. – Вып. 17. – М.: ИПУ РАН, 2007. – С. 103–120.

40. Кочкаров А.А., Салпагаров М.Б., Эльканова Л.М. Дискретная модель структурного разрушения сложных систем // Проблемы управления. – 2007. – № 5. – С. 21–26.

41. Кузнецов О.П. Однородные ресурсные сети. I. Полные графы // Автоматика и телемеханика. – 2009. – № 11. – С. 136–147.

42. Кузнецов О.П., Жилякова Л.Ю. Двусторонние ресурсные сети – новая потоковая модель // Доклады Академии Наук. – 2010. – Т. 433, № 5. – С. 609–612.

43. Кузнецов О.П., Жилякова Л.Ю. Полные двусторонние ресурс-ные сети с произвольными пропускными способностями // Управление большими системами. Специальный выпуск 30.1 «Сетевые модели в управлении». – М.: ИПУ РАН, 2010. – С. 640–664.

44. Кузьминова М.В. Ограниченные магнитные достижимости на ориентированных графах // Известия ВУЗов. Северо-Кавказ-ский регион. Естественные науки. Приложение. – 2006. – № 6. – С. 12–26.

45. Куссуль Н., Соколов А. Адаптивное обнаружение аномалий в поведении пользователей компьютерных систем с помощью марковских цепей переменного порядка. Ч. 2: Методы обнару-жения аномалий и результаты экспериментов // Проблемы управления и информатики. – 2003. – № 4. – С. 83–88.

46. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограни-чениями: научное издание / М.: Вычислитель¬ный центр им. А.А. Дородницына РАН. – 2007. – 80 с.

47. Ланкастер П. Теория матриц. – М.: Наука, 1982. – 272 с.

48. Ловас Л., Пламмер М. Прикладные задачи теории графов. Тео-рия паросочетаний в математике, физике, химии: Пер. с англ. – М.: Мир, 1998. – 653 с.

49. Новиков Д.А. Сетевые структуры и организационные системы. – М.: ИПУ РАН, 2003.

50. Петросян А.Г. Потоковая задача в многопродуктовых сетях с нестандартной достижимостью // Современные проблемы ма-тематического моделирования. – Ростов н/Д., 2005. – C. 334–340.

51. Петросян А.Г. Потоки в сетях с биполярной достижимостью // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. – 2006. – № 3. – С. 32–37.

52. Робертс Ф.С. Дискретные математические модели с приложе-ниями к социальным, биологическим и экологическим задачам. – М.: Наука, 1986. – 496 с.

53. Романовский В.И. Дискретные цепи Маркова. – М.; Л.: Госу-дарственное издательство научно-технической литературы, 1949. – 436 с.

54. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. – М.: Мир, 1984, – 454 с.

55. Севастьянов Б.А. Ветвящиеся процессы. – М.: Наука, 1971.

56. Седжвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах. – СПб.: ДиаСофтЮП, 2002. – 496 c.

57. Скороходов В.А. Графы с магнитной достижимостью. Марков-ские процессы и потоки в сетях // деп. в ВИНИТИ, 2003, № 410-В2003

58. Фляйшнер Г. Эйлеровы графы и смежные вопросы: Пер. с англ. – М.: Мир, 2002. – 176 с.

59. Форд Л.P., Фалкерсон Д.Р. Потоки в сетях: Пер. с англ. – М.: Мир, 1996. – 334 с.

60. Фрэнк Г., Фриш И. Сети, связь и потоки: Пер. с англ. / Под ред. Д.А. Поспелова. – М.: Связь, 1978. – 448 с.

61. Хорн Р., Джонсон Ч. Матричный анализ. – М.: Мир, 1989. – 655 с.

62. Чеботарев П.Ю., Агаев Р.П. Согласование характеристик в многоагентных системах и спектры лапласовских матриц орграфов // Автоматика и телемеханика. – 2009. – № 3. – С. 136–151.

63. Чеботарев П.Ю., Агаев Р.П. Об асимптотике в моделях консен-суса. – URL: http://ubs.mtas.ru/bitrix/components/bitrix/forum.interface/show_file.php?fid=7640

64. Aiello, W., Awerbuch, B., Maggs, B. and Rao, S. Approximate load balancing on dynamic and asynchronous networks, Proc. 25th ACM Symp. of Theory of Computing. 1993. P. 632–634.

65. Ahuja, R.K., Magnanti, T.L., Orlin, J.B. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, United States, 1993.

66. Aldous, D.J. Lower bounds for covering times for reversible Mar-kov chains and random walks on graphs. J. Theoret. Probab. 2, no. 1. 1989. P. 91–100.

67. Aleliunas, R., Karp, R.M., Lipton, R.J., Lovász L., and C.W. Rack-off. Random walks, universal travelling sequences, and the com-plexity of maze problem // Proc. 20th Ann. Symp. on Foundations of Computer Science. P. 218–223, 1979.

68. Anderson, R.J., Lovász L., Shor, P.W., Spencer, J., Tardos, E. and Winograd, S. Disks, balls, and walls: analysis of a combinatorial game // Amer. Math. Monthly 96. 1989. pp. 481–493.

69. Bak, P. How Nature Works: The Science of Self-Organized Criti-cality. New York: Copernicus. 1996. (Рус. пер.: Как работает природа: Теория самоорганизованной критичности. – М.: УРСС: Либроком, 2013. – 276 с.

70. Bak, P., Tang, C. and Wiesenfeld, K. Self-organized criticality, Physical Review A 38. 1988, P. 364–374.

71. Bak, P., Chen K. Self-organized criticality. Scientific American 264, January 1991 issue. P. 46–53.

72. Barabási A.-L., Albert R. Emergence of scaling in random networks / Science. 1999. V. 286. No. 5439. P. 509–512.

73. Bayer, D. and Diaconis, P. Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2. 1992, P. 294–313.

74. Biggs, N.L. Chip-Firing and the Critical Group of a Graph // Journal of Algebraic Combinatorics 9 (1999), pp. 25–45. Kluwer Academic Publishers. Netherlands. 1999.

75. Biggs, N. The Tutte-polynomial as a growth function // J. Algebraic Combinatorics 10. 1999, pp. 115–133.

76. Björner, A., Lovász L., and Shor, P. Chip-firing games on graphs // Europ. J. Comb. 12 (1991), 283–291.

77. Björner, A. and Lovász L. Chip-firing games on directed graphs, J. Algebraic Combinatorics 1. 1992, pp. 305–328.

78. Blanchard, Ph., Volchenkov, D. Random Walks and Diffusions on Graphs and Databases: An Introduction (Springer Series in Syner-getics). Springer-Verlag – Berlin–Heidelberg. 2011.

79. Brin, S., Page, L. The PageRank Citation Ranking: Bringing Order to the Web. URL: http://infolab.stanford.edu/~backrub/pageranksub.ps

80. Chebotarev P., Agaev R. Forest matrices around the Laplacian ma-trix // Linear Algebra and its Applications. – 2002. – Vol. 356. – P. 253–274.

81. Chung, F., Ellis, R. A chip-firing game and Dirichlet eigenvalues // Discrete Math. 257. 2002. pp. 341–355.

82. Chung, F. Laplacians and the Cheeger inequality for directed graphs. Ann. Comb. 9, 1. 2005.

83. Cori, R. and Rossin, D. On the sandpile group of dual graphs // Eu-rop. J. Comb. 21. 2000, pp. 447–459.

84. Dasgupta, K., Singh, R., Viswanathan, B., Chakraborty, D., Muk-herjea, S., Nanavati, A.A. Social Ties and their Relevance to Churn in Mobile Telecom Networks // Proceedings of the 11th interna-tional conference on Extending database technology EDBT´08: Ad-vances in database technology ACM New York, NY, USA. 2008.

85. De Groot M.H. Reaching a Consensus // J. Amer. Statist. Assoc. – 1974. – Vol. 69, No. 345. – P. 118–121.

86. Dhar, D. Self-organized critical state of sandpile automaton models, Physical Review Letters 64. 1990, P. 1613–1616.

87. Dhar, D. The abelian sandpile and related models // Physica A: Sta-tistical Mechanics and its Applications. Volume 263, Issues 1–4, 1 February 1999, pp. 4–25.

88. Dhar, D., Sadhu, T., Chandra, S. Pattern formation in growing sandpiles // Euro. Phys. Lett. Volume 85, Number 4, 48002. 2009. arXiv:0808.1732 [cond-mat.stat-mech]

89. Dhar, D., Ruelle, P., Sen, S., Verma, D.-N. Algebraic Aspects of Abelian Sandpile Models. 1994. arXiv:cond-mat/9408020

90. Engel, A. The probabilistic abacus, Educ. Stud. in Math. 6. 1975. pp. 1–22.

91. Engel, A. Why does the probabilistic abacus work? Educ. Stud. in Math. 7. 1976. pp. 59–69.

92. Fleischer, L., Skutella, M. Minimum Cost Flows Over Time without Intermediate Storage. // Proc. 35th ACM/SIAM Symp. on Discrete Algorithms (SODA), Baltimore, MD, January 2003, pp. 66–75.

93. Hajnal J. The ergodic properties of non-homogeneous finite Markov chains // Proc. Cambridge Philos. Soc. – 1956. – Vol. 52. – P. 67–77.

94. Hajnal J. Weak ergodicity in non-homogeneous Markov chains // Proc. Cambridge Philos. Soc. – 1958. – Vol. 54. – P. 233–246.

95. Hu, T.C. Multy-commodity network flows. – J. ORSA, 1963. № 11 (3). P. 344–360.

96. Ivashkevich, E.V., Priezzhev, V.B., Introduction to the sandpile model. Physica A 254, 97–116. 1998.

97. Kuznetsov, O.P., Zhilyakova, L.Yu. Flows and Limit States in Bidirectional Resource Networks// Preprints of the 18th IFAC World Congress. Milano (Italy) August 28 – September 2, 2011, pp. 14031–14035

98. Kuznetsov, O.P., Zhilyakova, L.Yu. Nonsymmetric resource net-works. The study of limit states // Management and Production En-gineering Review. Volume 2, Number 3, September 2011, pp. 33–39.

99. Lancaster P., Tismenetsky M. The Theory of Matrices, 2nd ed. New York: Academic Press, 1985.

100. Lopez, C.M. Chip firing and the Tutte polynomial // Annals of Combinatorics, 1. 1997. pp. 253–259.

101. Lovász, L. and Winkler, P. Mixing of Random Walks and Other Diffusions on a Graph // Surveys in Combinatorics, 1995 (ed. P. Rowlinson), London Math. Soc. Lecture Notes Series 218, Cam-bridge Univ. Press. pp. 119–154.

102. Maes, C., Redig, F., and Saada, E., The Abelian sandpile model on an infinite tree // Ann. Probab. Volume 30, Number 4 (2002), 2081–2107.

103. Maes, C., Redig, F., and Saada, E., Abelian Sandpile Models in Infinite Volume. March, 2005. 24 p. URL:http://www.academia.edu/2491250/Abelian_sandpile_models_in_infinite_volume

104. Maes, C., Redig, F., Saada E., The infinite volume limit of dissipa-tive abelian sandpiles, Commun. Math. Phys. 244, No. 2, 395–417. 2004.

105. Meester, R., Redig, F., and Znamenski, D. The Abelian sandpile; a mathematical introduction. 2008. 20 p. URL:http://www.cs.vuanl/~rmeester/onderwijs/introduction_spatial_models/sandpile2.pdf

106. Meshbahi M., Egerstedt M. Graph Theoretic Methods in Multiagent Networks. Princeton, NJ: Princeton University Press, 2010.

107. Meyer, C.D., Jr., Limits and the Index of a Square Matrix, SIAM J. Applied Math., 1974, vol. 26, pp. 469–478.

108. Meyn, S., Tweedie, R. L. Markov Chains and Stochastic Stability. Cambridge University Press. 2009. 594 p.

109. Norris, J. R. Markov Chains. Cambridge University Press. 1998. 237 p.

110. Priezzhev, V.B., Structure of two-dimensional sandpile. I. Height probabilities. Journal of Stat. Phys. 74, 955–979 (1994).

111. Prisner, E. Parallel Chip Firing on Digraphs // Complex Systems 8. 1994. pp. 367–383.

112. Redig, F., Mathematical aspects of the abelian sandpile model. June, 2005. 60 p. URL: http://www.math.leidenuniv.nl/~redig/sandpilelectures.pdf

113. Ren W., Cao Y., Distributed Coordination of Multi-agent Networks: Emergent Problems, Models, and Issues. London: Springer, 2011.

114. Rothblum, U.G. Computation of the eigenprojection of a nonnega-tive matrix at its spectral radius // Stochastic Systems: Modeling, Identification and Optimization II, ser. Mathematical Programming Study, R.J.-B. Wets, ed. Amsterdam: North-Holland. – 1976. – Vol. 6. – P. 188–201.

115. Seneta, E. Non-negative Matrices and Markov Chains. Springer. 2006. – 279 p.

116. Speer, E. R. Asymmetric abelian sandpile models // Journal of Sta-tistical Physics. April 1993, Volume 71, Issue 1–2, pp. 61–74.

117. Spencer, J. Balancing vectors in the max norm. Combinatorica, v. 6. 1986, pp. 55–66.

118. Turcotte, D.L., Self-Organized Criticality, Rep. Prog. Phys. 62, pp. 1377–1429. 1999.

119. Volchenkov D., Volchenkova L., Blanchard P. Epidemic spreading in a variety of scale free networks. // Physical Review E 66, 046137. – 2002.

120. Watts D.J., Strogatz S.H. Collective dynamics of ´small-world´ net-works // Nature. 1998. V. 393. No. 6684. P. 440–442.

121. Ye, N. A Markov chain model of temporal behavior for anomaly detection // Proceedings of the 2000 IEEE Workshop on Informa-tion Assurance and Security United States Military Academy, West Point, NY, 6–7 June, 2000. P. 171–174.

Войти или Создать
* Забыли пароль?