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

Автор: Щербакова Наталья Григорьевна

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

Рубрика: Прикладные информационные технологии

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

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

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

Комплексные системы, гиперграфы, двудольные графы, симплициальныс комплексы, центральность акторов

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

IDR: 143179396 | DOI: 10.24412/2073-0667-2022-3-24-45

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

Diestel R. Graph theory. Graduate texts in mathematics. Springer, 2005.
Albert R., Barabasi A-L. Statistical mechanics of complex networks // Rev. of Modern Phys. 2002. V. 74. P. 47-97. DOI: 10.1103/RevModPhys.74.47.
Newman M. E. J. Networks: An introduction. Oxford, NY: Oxford Univ. Press., 2010. ISBN-13: 9780199206650.
Rosvall M., Esquivel A. V., Lancichinetti A., West J. D., Lambiotte R. Memory in network ows and its e-ects on spreading dynamics and community detection // Nature commun. 2014. V. 5, 4630. DOI: 10.1038/ncomms5630.
On B.-W., Elmacioglu E., Lee D., Kang J., Pei J. Improving grouped-entity resolution using quasi-cliques // Proc. of the 6th Intern. conf. on data mining (ICDM'06). 2006. P. 1008 1015. DOI: 10.1109/ICDM.2006.85.
Benson A. R., Abebe R., Schaub M. T., Jadbabaie A., Kleinberg J. Simplicial closure and higher-order link prediction // Proc. Nat. Acad. Sci. 2018.V. 115, N 48: E11221-E11230. DOI: 10.1073/pnas.1800683115.
Johnson J. Hypernetworks in the science of complex systems. UK: Imperial College Press. 2013. ISSN: 1755-7453.
Battiston F., Cencetti G., Iacopini I., Latora V., Lucas M., Patania A. Young J-G., Petri G. Networks beyond pairwise interactions: Structure and dynamics // Phys. Rep. 2020. V. 874. P. 1-92. DOI: 10.1016/j.physrep.2020.05.004.
Lambiotte R., Rosvall M., Scholtes I. From networks to optimal higher-order models of complex systems // Nature Phys. 2019. V. 15. P. 313-320. DOI: 10.1038/s41567-019-0459-y.
Boccaletti S., Bianconi G., Criado R., del Genio C. I., Gómez-Gardeñes J., Romance M., Sendina-Nadal I., Wang Z., Zanin M. The structure and dynamics of multilayer networks // Phys. Rep. 2014. V. 544(1). P. 1-122. DOI: 10.1016/j.physrep.2014.07.001.
Bianconi G. Multilayer networks: Structure and function. Oxford Univ. Press. 2018. ISBN-13: 9780198753919.
Holme P.Modern temporal network theory: A colloquium // Eur. Phys. J. B 88, 234. 2015. DOI: 10.1140/epjb/e2015-60657-4.
Borgatti S. P., Everett M. G. Network analysis of 2-mode data // Soc. networks. 1997. V. 19. P. 243 269. DOI: 10.1016/S0378-8733(96)00301-2.
Newman M. E. J., Strogatz, S. H., Watts D. J. Random graphs with arbitrary degree distributions and their applications // Phys. Rev. E 64, 026118. 2001. DOI: 10.1103/PhysRevE.64.026118.
Breiger R. L. The duality of persons and groups // Soc. Forces. 1974. V. 53, N 2. P. 1981-1990. DOI: 10.2307/2576011.
Atkin R. H. From cohomology in physics to q-connectivity in social science // Intern. J. Man-Machine Stud. 1972. V. 4, iss. 2. P. 139-167. DOI: 10.1016/S0020-7373(72)80029-4.
Atkin R. H. An algebra for patterns on a complex, I // Intern. J. Man-Machine Stud. 1974. V. 6, iss. 3. P. 285 307. DOI: 10.1016/S0020-7373(74)80024-6.
Atkin R. H. An algebra for patterns on a complex, II // Intern. J. Man-Machine Stud. 1976. V. 8, iss. 5. P. 483 498. DOI: 10.1016/S0020-7373(76)80015-6.
Hatcher A. Algebraic topology. Cambridge, UK: Cambridge Univ. Press, 2002.
Seidman S. Structures induced by collections of subsets: A hypergraph approach // Math. Soc. Sci. 1981. V. 1, iss. 4. P. 381 396. DOI: 10.1016/0165-4896(81)90016-0.
Berge C. Graphs and hypergraphs. Amsterdam: North-Holland. 1976.
Wilson T. P. Relational networks: An extension of sociometric concepts // Soc. Networks. 1982. V. 4, iss. 2. P. 105-116. DOI: 10.1016/0378-8733(82)90028-4.
Andjelkovic M., Tadic B., Maletic S., Rajkovi c M. Hierarchical sequencing of online social graphs // Phys. A: Statistical Mechanics and its Applications. 2015. V. 436, iss. 15. P. 582 595. DOI: 10.1016/j.physa.2015.05.075.
Zhou D., Huang J., Scholkopf B. Learning with hypergraphs: Clustering, classi cation, and embedding // Proc. of the 19th Intern. conf. on neural information processing systems. 2007. P. 1601 1608. DOI: 10.7551/mitpress/7503.003.0205.
Bothorel C., Bouklit M. An algorithm for detecting communities in folksonomy hypergraphs. I2CS 2011: the 11th Intern. conf. on innovative Internet community services, Berlin (Germany), June 2011. P. 159-168. hal-00724991.
Estrada E., Rodr-iguez-Velazquez J. A. Complex networks as hypergraphs // arxiv: physics/0505137, 2005. DOI: 10.1016/j.physa.2005.12.002.
Morris S. A., Yen G. G. Construction of bipartite and unipartite weighted networks from collections of journal papers // arxiv: physics/0503061, 2005.
Guillaume J.-L., Latapy M. Bipartite graphs as models of complex networks // Phys. A: Stat. Mechan. and its Appl. 2006. V. 371, iss. 2. P. 795 813. DOI: 10.1016/j.physa.2006.04.047.
Ghoshal G., Zlatic V., Caldarelli G., Newman M. E. J. Random hypergraphs and their applications // Phys. Rev. E 79(6), 066118. 2009. DOI: 10.1103/PhysRevE.79.066118.
Torres J. J., Bianconi G. Simplicial complexes: higher-order spectral dimension and dynamics // J. Phys.: Complexity. V. 1, iss. 1. 2020. 015002. DOI: 10.1088/2632-072X/ab82f5.
Carletti T., Fanelli D., Nicoletti S. Dynamical systems on hypergraphs // J. of Phys.: Complexity. 2020. V. 1, iss. 3, 035006. DOI: 10.1088/2632-072X/aba8e1.
Berge C. Hypergraphs. North-Holland. 1989.
Voloshin V. I. Introduction to graph and hypergraph theory. Nova Science Publ., 2009. ISBN: 978-1-60692372-6.
Bretto A. Hypergraph theory: An introduction (Mathematical Engineering). Heidelberg: Springer Intern. Publishing, 2013. ISBN: 978-3-319-00079-4. DOI: 10.1007/978-3-319-00080-0.
Stell J. G. Relations on hypergraphs // RAMiCS'12: Proc. of the 13th Intern. conf. on relational and algebraic methods in computer science. 2012. P. 326 341. DOI: 10.1007/978-3-642-33314-9_22.
Ouvrard X. Hypergraphs: An introduction and review // arxiv: 2002.05014v2, 2020.
Benson A. R., Gleich D. F., Leskovec J. Higher-order organization of complex networks // Science. 2016. V. 353 (6295). P. 163-166. DOI: 10.1126/science.aad9029.
Makinen E. How to draw a hypergraph // Intern. J. of Comput. Math. 1990. V. 34, iss. 3 4. DOI: 10.1080/00207169008803875.
Johnson D. S., Pollak H. O. Hypergraph planarity and the complexity of drawing Venn diagrams // J. Graph Theory. 1987. V. 10. P. 309 325. DOI: 10.1002/jgt.31901103067.
Kaufmann M., van Kreveld M., Speckmann B. Subdivision drawings of hypergraphs // Graph Drawing. V. 5417. P. 396-407. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. ISBN: 978-3-642-00218-2 978-3-642-00219-9. DOI: 10.1007/978-3-642-00219-9_39.
Torres L., Blevins A. S., Bassett D. S., Eliassi-Rad T. The why, how, and when of representations for complex systems // SIAM Rev. 2021. V. 63, iss. 3. P. 435 485.
Maletic S., Rajkovic M., Vasiljevic D. Simplicial complexes of networks and their statistical properties // Proc. Intern. conf. on computational science, Springer. 2008. P. 568-575.
Estrada E., Ross G. J. Centrality in simplicial complexes. Application to protein interaction networks // J. Theor. Biol. 2018. V. 438. P. 46-60. DOI: 10.1016/j.jtbi.2017.11.003.
Serrano D. H., G omez D. Centrality measures in simplicial complexes: applications of topological data analysis to network science // Appl. Math. Comput. 2020. V. 383, iss. 3, 125331. DOI: 10.1016/j.amc.2020.125331.
Patania A., Petri G., Vaccarino F. The shape of collaboration // EPJ Data Sci. 2017. V. 6, iss. 18. DOI: 10.1140/epjds/s13688-017-0114-8.
Serrano D. H., Hernandez-Serrano J., Gomez D. Simplicial degree in complex networks. Applications of topological data analysis to network science // Chaos, Solitons & Fractals. 2020. V. 137, 109839. DOI: 10.1016/j.chaos.2020.109839.
Zhou W., Nakhleh U. Properties of metabolic graphs: biological organization or representation artifacts? // BMC Bioinformatics. 2011. V. 12. P. 132-144.
Gallagher S. R., Goldberg D. S. Clustering coe cients in protein interaction hypernetworks // BCB'13: Proc. of the Intern. Conf. on Bioinformatics, Comput. Biology and Biomedical Informatics, Washington (USA), Sept. 22-25, 2013. P. 552-560. DOI: 10.1145/2506583.2506635.
Freeman L. C. Centrality in social networks. Conceptual clarication // Soc. Networks. 1978/1979. V. 1. P. 215 239. DOI: 10.1016/0378-8733(78)90021-7.
Friedkin N. E. Theoretical foundations for centrality measures // Amer. J. Soc. 1991. V. 96. P. 1478 1504. DOI: 10.1086/229694.
Wasserman S., Faust K. Social network analysis. Cambridge Univ. Press, 1984. ISBN: 9780511815478. DOI: 10.1017/CBO9780511815478.
Boldi P., Vigna S. Axioms for centrality // Intern. Math. 2013. V. 10(3-4). P. 222-262. DOI: 10.1080/15427951.2013.865686.
Faust K. Centrality in a liation networks // Social Networks. 1997. V. 19. P. 157-191. DOI: 10.1016/S0378-8733(96)00300-0.
Kapoor K., Sharma D., Srivastava J. Weighted node degree centrality for hypergraphs // Proc. of the IEEE 2nd Intern. Network Science Workshop (NSW). 2013. P. 152 155. United States, West Point, NY, April 20 May 1, 2013. DOI: 10.1109/NSW.2013.6609212.
Bonacich P. Simultaneous group and individual centralities // Soc. networks 1991. V. 13, iss. 2. P. 155-168. DOI: 10.1016/0378-8733(91)90018-O.
Busseniers E. General centrality in a hypergraph // arXiv: 1403.5162, 2014.
Bonacich P. Factoring and weighting approaches to status scores and clique identication // J. of Math. Soc. 1972. V. 2, N 1. P. 113 120. DOI: 10.1080/0022250X.1972.9989806.
Bonacich P. Power and centrality: A family of measures // Amer. J. Soc. 1987. V. 92, N 5. P. 1170 1182.
Chen X. The shortest path algorithms of hypergraphs based on search strategies // J. of Software. 2015. V. 10, N 1. P. 94 105. DOI: 10.17706/jsw.10.1.94-105.
Brandes U. A faster algorithm for betweenness centrality // Math. Sociol. 2001. V. 25. P. 163 177. DOI: 10.1080/0022250X.2001.9990249.
Brandes U. On variants of shortest-path betweenness centrality and their generic computation // Soc. Networks. 2008. V. 30. P. 136 145. DOI: 10.1016/j.socnet.2007.11.001.
Puzis R., Purohit M., Subrahmanian V. S. Betweenness computation in the single graph representation of hypergraphs // Soc. networks. 2013. V. 35, iss. 4. P. 561 572. DOI: 10.1016/j.socnet.2013.07.006.
Cooper J., Dutle A. Spectra of uniform hypergraphs // Linear Algebra Appl. 2012. V. 436, iss. 9. P. 3268 3292. DOI: 10.1016/j.laa.2011.11.018.
Hu S., Qi L. The Laplacian of a uniform hypergraph // J. Comb. Optim. 2015. V. 29, iss. 2. P. 331 366. DOI 10.1007/s10878-013-9596-x.
Banerjee A., Char A., Mondal B. Spectra of general hypergraphs // Linear Algebra Appl. 2016. V. 518, iss. 1. P. 14-30. DOI:10.1016/j.laa.2016.12.022.
Rodriguez J. A. On the Laplacian spectrum and walk-regular hypergraphs // Lin. And Multilin. Alg. 2003. V. 51, N 3. P. 285-297.
Shi J., Malik J. Normalized cuts and image segmentation // IEEE Trans. on Pattern Analysis and Machine Intell. 2000. V. 22(8). P. 888-905.
Meila M., Shi J. A random walks view of spectral segmentation // In Proc. 8th Intl.Workshop on Artif. Intell. and Statistics. PMLR R3:203-208, 2001.
Lu L., Peng X. High-ordered random walks and generalized Laplacians on hypergraphs // Intern. Workshop on Algorithms and Models for the Web-Graph. Springer, 2011. P. 14-25.
Muhammad A., Egerstedt M. Control using higher order Laplacians in network topologies // Proc. of 17th Intern. Symp. on Math. Theory of Networks and Systems, Citeseer, 2006. P. 1024-1038.
Moore T. J., Drost R. J., Swami A. The communications and networks collaborative technology alliance publication network: a case study on graph and simplicial complex analysis // Comput. and inform. sci. Directorate, ARL, US army research Laboratory. 2015.

Еще

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