Модели многоуровневых сетей (краткий обзор)

Автор: Кальней Артем Максимович

Журнал: Проблемы информатики @problem-info

Рубрика: Теоретическая и системная информатика

Статья в выпуске: 3 (52), 2021 года.

Бесплатный доступ

Ограниченность модели графа при моделировании реальных сетей давно уже стала очевидна. Как следствие, стало появляться огромное количество трудов, учитывающих многоуровневый характер реальных сетей, однако вопросы унификации моделей и терминов стали подниматься лишь в прошлом десятилетии. В данной статье представлен исторический обзор развития моделей многоуровневых сетей. Описаны несколько наиболее развитых моделей на сегодняшний момент, а также логика их построения. Приведена таблица, показывающая примеры применения рассмотренных моделей.

Многоуровневые сети, многослойные сети, моделирование, гиперсети

Короткий адрес: https://sciup.org/143178344

IDR: 143178344 | DOI: 10.24412/2073-0667-2021-3-5-20

Список литературы Модели многоуровневых сетей (краткий обзор)

Newman, М. Е. J. Networks: An Introduction. Oxford: Oxford University Press, 2010.
Wasserman, S., Faust, K. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.-U. Complex networks: structure and dynamics // Phvs. Reps. 2006. N 424. P. 175-308.
Bollobas, B. Modern Graph Theory. Berlin: Springer, 1998.
Barabasi, A.-L., Albert, R. Emergence of scaling in random networks // Science. 1999. N 286. P. 509-512.
Clauset,A., Shalizi, C. R., Newman, M. E. J. Power-law distributions in empirical data // SIAM Rev. 2009. N 51. P. 661-703.
Watts, D. J., Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature. 1998. N 393. P. 440-442.
Porter, M. A. Small-world network // Scholarpedia. 2012. N 7. P. 1739.
Porter, M. A., Onnela, J.-P., Mucha, P. J. Communities in networks // Not. Am. Math. Soc. 2009. N 56. P. 1082-1097, 1164-1166.
Fortunato, S. Community detection in graphs // Phvs. Reps. 2010. N 486. P. 75-174.
Lancichinetti, A., Kivela, M., Saramaki, J., Fortunato, S. Characterizing the community structure of complex networks. PLOS ONE. 2010. N 5. P. ell976.
Bang-Jensen, J., Gutin, G. Digraphs: Theory, Algorithms and Applications, 2nd edn. Berlin: Springer, 2008.
Barrat, A., Barthelemv, M., Pastor-Satorras, R., Vespignani, A. The architecture of complex weighted networks // Proc. Natl Acad. Sci. USA, 2004. N 101. P. 3747-3752.
Newman, M. E. J. Analysis of weighted networks // Phvs. Rev. E, 2004. N 70. P. 056131.
Breiger, R. L. The duality of persons and groups // Social Forces, 1974. N 53. P. 181-190.
Holme, P., Saramaki, J. Temporal networks // Phvs. Reps., 2012. N 519. P. 97-125.
Holme, P., Saramaki, J. (eds). Temporal Networks. Berlin: Springer, 2013.
Mikko Kivela, Alex Arenas, Marc Barthelemv, James P. Gleeson, Yamir Moreno, and Mason A. Porter. (2014), Multilayer networks // Journal of Complex Networks 2, 2014. N 3. P. 203-271.
D'Agostino, G., Scala, A. Networks of Networks: The Last Frontier of Complexity. Berlin: Springer, 2014.
Boccaletti, S., Bianconi, G., Criado, R., del Genio, C. I., Gomez-Gardenes, J., Romance, M., Sendina-Nadal, I., Wang, Z., Zanin, M. The structure and dynamics of multilayer networks // Phvs. Reps., to appear. 2014.
Krackhardt, D. (1987) Cognitive social structures // Soc. Netw. 1987. N 9. P. 109-134.
Padgett, J. F., Ansell, C. K. Robust action and the rise of the medici, 1400-1434 // Am. J. Soc. 1993. N 98. P. 1259-1319.
Scott, J. Social Network Analysis. New York, NY: SAGE Publications, 2012.
Roethlisberger, F., Dickson,WT. Management and the Worker. Cambridge: Cambridge University Press. 1939.
Gluckman, M. The Judicial Process Among the Barotse of Northern Rhodesia. Manchester: Manchester University Press, 1955.
Verbrugge, L. M. Multiplexitv in adult friendships // Soc. Forces, 1979. N 57. P. 1286-1309.
Craven, P. , Wellman, B. (1973) The network city // Sociol. Inquiry. 1973. N 43. P. 57-88.
Pattison, P., Wasserman, S. Logit models and logistic regressions for social networks: II. Multivariate relations // Br. J. Math. Stat. Psychol. 1999. N 52. P. 169-193.
Lusher, D., Koskinen, J., Robins, G. Exponential Random Graph Models for Social Networks. Cambridge: Cambridge University Press, 2013.
Krackhardt, D., Carlev, K. M. A PCANS model of structure in organization // International Symposium on Command and Control Research and Technology, Monterrav, CA, 1998. P. 113-119.
Carlev, K. M., Hill, V. Structural change and learning within organizations. Dynamics of Organizational Societies: Models, Theories and Methods (A. Lomi, ed.). Cambridge, MA: MIT Press/AAAI Press/Live Oak, 2001.
Lorrain, F., WThite, H. C. Structural equivalence of individuals in social networks //J. Math. Sociol. 1971. N 1. P. 49-80.
Boorman, S. A., White, H. C. Social structure from multiple networks. II. Role structures. Am. J. Sociol. 1976. N 81. R 1384-1446.
Breiger, R. L., Pattison, P. E. Cumulated social roles: the duality of persons and their algebras // Soc. Netw. 1986. N 8. P. 215-256.
Doreian, P., Batagelj, V., Ferligoj, A. Generalized Blockmodeling. Cambridge, UK: Cambridge University Press, 2004.
White, H. C., Boorman, S. A., Breiger, R. L. Social structure from multiple networks. I. Blockmodels of roles and positions // Am. J. Sociol. 1976. P. 730-780.
WTinship, C., Mandel, M. Roles and positions: a critique and extension of the blockmodeling approach // Sociol. Method. 1983-1984. N 14. P. 314-344.
Pattison, P. Social networks, algebraic models for. Encyclopedia of Complexity and Systems Science (R. A. Meyers ed.). New York: Springer, 2009. P. 8291-8306.
Dunlavv, D. M., Kolda, T. G., Kegelmever, W. P. Multilinear algebra for analyzing data with multiple linkages. Graph Algorithms in the Language of Linear Algebra (J. Kepner k, J. Gilbert eds). Fundamentals of Algorithms. Philadelphia: SIAM, 2011. P. 85-114.
Kolda, T. G., Bader, B. W. Tensor decompositions and applications. SIAM Rev. 2009. N 51. P. 455-500.
Acar, E., Yener, B. Unsupervised multiwav data analysis: a literature survey // IEEE Trans. Knowl. Data Eng., 2009. N 91. P. 6-20.
Martin, C. D., Porter, M. A. The extraordinary SVD // Am. Math. Monthly. 2012. N 119. P. 838-851.
Kolda, T., Bader, B.WT. The TOPHITS model for higher-order web link analysis // Proceedings of the SIAM Data Mining Conference Workshop on Link Analysis, Counterterrorism and Security, Bethesda, MD, 2006.
Kolda, T. G., Bader, B. W., Kenny, J. P. Higher-order web link analysis using multilinear algebra // Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005), Houston, TX, 2005. P. 242-249.
Zhou, D., Orshanskiv, S. A., Zha, H., Giles, C. L. Co-ranking authors and documents in a heterogeneous network // Seventh IEEE International Conference on Data Mining (ICDM 2007), Omaha, NE, 2007. P. 739-744.
Cai, D., Shao, Z., He, X., Yan, X., Han, J. Community mining from multi-relational networks // Proceedings of the 9th European Conference on Principles and Practice of Knowledge Discovery in Databases, Porto, Portugal, 2005.
Sun, Y., Han, J. Mining heterogeneous information networks: a structural analysis approach // ACM SIGKDD Explor. Newslett. 2013. N 14. P. 20-28.
Carlev, K. M. Dynamic network analysis. Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers. Committee on Human Factors, National Research Council, 2003. P. 133-145.
Chang, S. E., Seligson, H. A., Eguchi, R. T. Estimation of the economic impact of multiple lifeline disruption: memphis light, gas and water division case study. Technical Report NCEER-96-0011, Multidisciplinarv Center for Earthquake Engineering Research (MCEER), Buffalo, NY, 1996.
Little, R. G. Controlling cascading failure: understanding the vulnerabilities of interconnected infrastructures // J. Urban. Tech. 2002. N 9. P. 109-123.
Rosato, V., Issacharoff, L., Tiriticco, F., Meloni, S., Porcellinis, S., Setola, R. Modelling interdependent infrastructures using interacting dynamical models // Int. J. Crit. Infra. 2008. N 4. P. 63-79.
Khapugin, S., Rodionov, A. S. Modeling grouped failures in network reliability analysis // B ACM IMCOM 2015 - Proceedings [a44] (ACM IMCOM 2015 - Proceedings). 2015. Association for Computing Machinery, Inc. https://doi.org/10.1145/2701126.2701218.
Leicht, Е. A., D'Souza, R. М. Percolation on interacting networks. arXiv:0907.0894 fcondmat. dis-nn]. 2009.
Buldvrev, S. V., Parshani, R., Paul, G., Stanley, H. E., Havlin, S. (2010) Catastrophic cascade of failures in interdependent networks // Nature. 2010. N 464. P. 1025-1028.
Vespignani, A. The fragility of interdependencv // Nature. 2010. N 464. P. 984-985.
Dijkstra, F., Andree, В., Kovmans, K., van der Hama, J., Grosso, P., de Laat, C. A multi-layer network model based on ITU-T G.805 // Comput. Netw. 2008. N 52. P. 1927-1937.
Rotaru, Sandra. Cross-layer design in wireless local area networks (WLANs) issues and possible solutions. 2018. 10.13140/RG.2.2.13913.77924.
Koster, A. M. C. A., Orlowski, S., Raack, C., Baier, G., Engel, Т., Belotti, P. Branch-and-cut techniques for solving realistic two-layer network design problems // Graphs and Algorithms in Communication Networks. Springer, Heidelberg, 2009. P. 95-118.
Chigan, C., Atkinson, G., Nagarajan, R. On the modeling issue of joint cross-layer network protection/restoration // Proceedings of Advanced Simulation Technologies Conference (ASTC '04), 2004. P. 57-62.
Kurant, M., Thiran, P. Layered complex networks // Phvs. Rev. Lett. 96, 2006. 138701-1— 138701-4.
Попков В. К. Математические модели связности. Новосибирск: НИМ н Ml СО РАН, 2006. 490 с.
Popkov V. К., Sokolova О. D. Application of Hyper net Theory for the Networks Optimization Problems // 17th IMACS World Congress, July 2005, Paper T4-I-42-011.
Rodionov A. S., Sokolova O., Yurgenson A., Choo H. On Optimal Placement of the Monitoring Devices on Channels of Communication Network // ICCSA 2009, Part II, LNCS, Vol. 5593. 474487.
Rodionov A. S., Choo H., Nechunaeva K. A. Framework for Biologically Inspired Graph Optimization // Proceedings of ICUIMC 2011, Seoul, Republic of Korea, 2011. P. 2.5, 4 pages.
Попков Владимир Константинович Применение теории S-гиперсетей для моделирования систем сетевой структуры // Проблемы информатики. 2010. № 4.
Попков В. К. Математические модели живучести сетей связи. Новосибирск: ВЦ СО АН СССР, 1990. 233 с.
Попков В. К. Методы оптимизации структур зоновых сетей связи / В.К. Попков, С. Б. Кауль, М. И. Нечепуренко. Новосибирск: ВЦ СО АН СССР, 1983. 182 с.
Попков В. К. Математические модели и методы оптимизации городских транспортных систем // Материалы 2-й Всерос. конф. „Проблемы оптимизации и экономические приложения", Омск, 29 июня — 4 июля 2009 г. Омск: Б. и., 2009. С. 80-81.
Kalnev A., Migov D., Rodionov A., Nasibullina Т. Designing of optimal power supply networks for the equipment of multifunctional safety systems // Novosibirsk, Russia, The 2019 15th International Asian School-Seminar Optimization Problems of complex systems.
Rodionov A., Rodionova О. Random Hvpernets in Reliability Analysis of Multilayer Networks. In: Mastorakis N., Bulucea A., Tsekouras G. (eds) Computational Problems in Science and Engineering // Lecture Notes in Electrical Engineering. 2015. V. 343. Springer, Cham, https ://doi .org/10.1007/ 978-3-319-15765-8-17.
Garbuzov, A. S. Rodionov. Some Problems of Fuzzy Modeling of Telecommunications Networks // Proc. of the 9 Int. Conf. on Ubiquitous Information Management and Communication, (IMCOM), Indonesia, Bali, 8-10 Jan. New York : ACM, 2015. P. 12.1-12.5. DOI: 10.1145/2701126.2701216. ISBN: 978-1-4503-3377-1. S. 418-422.
Hammoud, Zaynab, Kramer, Frank. Multilayer networks: aspects, implementations, and application in biomedicine. Big Data Analytics. 2020. 5. 10.1186/s41044-020-00046-0.
Kinsley Amy C., Rossi Gianluigi, Silk Matthew J., VanderWaal Kimberly. Multilayer and Multiplex Networks: An Introduction to Their Use in Veterinary Epidemiology. Frontiers in Veterinary Science, 2020, P. 596.
Sole-Ribalta, Albert Gomez, Sergio Arenas, Alex. Congestion Induced by the Structure of Multiplex Networks // Physical Review Letters. 2016. 116. 10.1103/PhysRevLett.116.108701.
Zhang, Shuai Liang, Man-Gui Li, Hui-Jia. Method to enhance traffic capacity for two-layer complex networks // Canadian Journal of Physics. 2014. N 92. P. 1599-1605. 10.1139/cjp-2013-0711.
Wu, Jiexin, Pu, Cunlai Li, Lunbo Cao, Guo. Traffic dynamics on multilayer networks // Digital Communications and Networks. 2018. N 6. 10.1016/j.dcan.2018.10.011.

Еще

Статья обзорная