2023 №4(61)

СОДЕРЖАНИЕ

Монахова Э. А., Монахов О. Г. Открытие аналитических зависимостей параметров оптимальных хордальных сетей на основе анализа данных
Коробов А. В., Мигов Д. А. Алгоритмы расчета надежности сети на основе декомпозиционного подхода
Вишневский В.М., Клименок В. И., Соколов А.М., Ларионов А. А. Исследование fork¬join системы с марковским входным потоком и распределением времени обслуживания фазового типа
Бредихин С. В.,Щербакова Н. Г.,Юргенсон А. Н. Модели сети соавторства научного журнала. Часть 2
Бакулина М. П. Повышение эффективности сжатия изображений на основе метода RLE
Герб А. Р., Омарова Г. А. Алгоритмы разбиения графов на GPU

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 519.8 + 519.7

DOI: 10.24412/2073-0667-2023-4-5-16

EDN: CSZMVY

ОТКРЫТИЕ АНАЛИТИЧЕСКИХ ЗАВИСИМОСТЕЙ ПАРАМЕТРОВ ОПТИМАЛЬНЫХ ХОРДАЛЬНЫХ СЕТЕЙ НА ОСНОВЕ АНАЛИЗА ДАННЫХ

Исследуется решение проблемы поиска общих аналитических зависимостей параметров семейств оптимальных по диаметру хордальных кольцевых сетей на основе анализа большого массива экспериментальных данных. Предложен новый подход, позволяющий автоматизировать процесс открытия аналитически описываемых семейств оптимальных сетей, задаваемых темплейтами с недоопределенными коэффициентами. При этом использованы алгоритмы дифференциальной эволюции, муравьиной колонии и исчерпывающий локальный поиск по заданным темплейтам на множестве экспериментальных данных. Предложенный подход позволил найти описания более 170 новых семейств оптимальных хордальных сетей (до этого было известно только шесть семейств). Благодаря хорошей масштабируемости и простоте маршрутизации оптимальные хордальные кольцевые сети представляют интерес как эффективные и надежные сети связи для сетей на кристалле иерархического типа, для телекоммуникационных сетевых структур и оптоволоконных сетей связи.

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

Работа выполнена при финансовой поддержке бюджетным проектом ИВМиМГ СО РАН (код проекта 0251-2022-0005).

Список литературы

Hwang F.K., A survey on multi-loop networks // Theoret. Computer Science. 2003. № 99.
Barriere L. Symmetry properties of chordal rings of degree 3 // Discr. Appl. Math. 2003. № 129.
Chen S. K., Hwang F. K. and Liu У. C. Some combinatorial properties of mixed chordal rings // J. of Interconnection Networks. 2003. № 4.
Monakhova E. A. A Survey on Undirected Circulant Graphs // Discr. Math. Algorithms and Appl. 2012. № 4.
Pedersen J. M., Riaz T. M., Madsen О. B. Distances in generalized double rings and degree three chordal rings //in IASTED Int. Conf, on Parallel and Distributed Computing and Networks (IASTED PDCN2005). Austria. 2005
Parhami B. Periodically regular chordal rings are preferable to double-ring networks // J. of Interconnection Networks. 2008. № 9.
Farah R. N., Chien S. L. E., and Othman M. Optimum Free-Table Routing in the Optimised Degree Six 3-Modified Chordal Ring Network // J. on Communications. 2017. № 12.
Ahmad M., Zahid Z., Zavaid M., and Bonyah E. Studies of Chordal Ring Networks via Double Metric Dimensions // Math. Problems in Engineering. 2022. (ArticlelD 8303242).
Gutierrez J., Riaz Т., Pedersen J., Labeaga S. and Madsen O. Degree 3 networks topological routing // Image Processing and Communication. 2009. № 14.
Arden B. W. and Lee H. Analysis of Chordal Ring Network // IEEE Trans, on Computers. 1981. № C-30.
11. Barriere, L., Cohen, J., Mitjana, M.: Gossiping in chordal rings under the line model. Theor. Comput. Sci. 2001. 264, 53-64.
Ledzinski, D., Smigiel, S., Zabludowski, L. Analyzing methods of network topologies based on chordal rings // Turkish Journal of Electrical Engineering and Computer Sciences. 2018. V. 26: N 3, Article 25.
Ekmekci, D., Huzber, A. A Review of Enhancement Traditional Wide Band Networks by Using Enhanced WIMAX Technology // Journal of Algebraic Statistics, 2022. V. 13. N 3. P. 1096-1107.
Deng Y., Guo M., Ramos A. F., Huang X., Xu Z., Liu W. Optimal low-latency network topologies for cluster performance enhancement //J. Supercomput. 2020. 76 (12): 9558-9584.
Monakhova E. A., Monakhov O. G., Romanov A. Yu. Routing Algorithms in Optimal Degree Four Circulant Networks Based on Relative Addressing: Comparative Analysis for Networks-on-Chip / IEEE Transactions on Network Science and Engineering. 2023. V. 10, N 1, P. 413-425.
Монахова Э. А., Монахов О. Г. Эволюционный синтез семейств оптимальных двумерных циркулянтных сетей // Вестник СибГУТИ. 2014. № 2.
Morillo Р., Cornelias F., Fiol М. A. The optimization of Chordal Ring Networks // Communication Technology, Eds. Q. Yasheng and W. Xiuying. World Scientific, 1987.
Monakhov O. G., Monakhova E. A., Kireev S. Parallel Generation and Analysis of Optimal Chordal Ring Networks Using Python Tools on Kunpeng Prosessors // In: Malyshkin, V. (eds) Parallel
Computing Technologies. Proc. 17th Inter. Conf. PaCT 2023, Astana, Kazakhstan, Lecture Notes in Computer Science, vol 14098. Springer, Cham. 2023, P. 126-135.
Storn R., Price K. Differential evolution — a simple and efficient heuristic for global optimization over continuous spaces //J. Global Optimization. 1997. № 11.
Zaheer H., Pant M., Monakhov O., Monakhova E. Simple and Efficient Co-operative Approach for Solving Multi modal Problems // Proc. International Conference on Electrical, Electronics and Optimization Techniques, India. 2016.
Du Ke-Lin, Swamy M. N. S. Search and Optimization by Metaheuristics. Techniques and Algorithms Inspired by Nature // Basel: Birkhauser, 2016.

статья

Библиографическая ссылка: Монахова Э. А., Монахов О. Г. Открытие аналитических зависимостей параметров оптимальных хордальных сетей на основе анализа данных //"Проблемы информатики", 2023, № 4, с.5-16. DOI: 10.24412/2073-0667-2023-4-5-16.

А. В. Коробов, Д.А. Мигов

Новосибирский государственный университет, 630090, Новосибирск, Россия

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 621.311.1+519.17

DOI: 10.24412/2073-0667-2023-4-17-28

EDX: HZLMJO

АЛГОРИТМЫ РАСЧЕТА НАДЕЖНОСТИ СЕТИ НА ОСНОВЕ ДЕКОМПОЗИЦИОННОГО ПОДХОДА

В статье рассматривается задача точного расчета структурной надежности сети с ненадежными ребрами и абсолютно надежными вершинами. В качестве показателя надежности используется вероятность связности соответствующего случайного графа. Точный расчет данного показателя — NP-трудная задача, что делает его затруднительным для сетей реальной размерности. Предлагаются модификации метода факторизации, использующегося для точного расчета, основанные на декомпозиции сети по вершинному разрезу (сечению, сепаратору), образованному двумя вершинами. Для более эффективного использования декомпозиции учитывается структурная схожесть получающихся при декомпозиции подграфов — собственно подграфов, и графов, получающихся из них склейкой разрезающих вершин. Разработано три алгоритма, в среднем ускоряющих процесс вычисления вероятности связности произвольного графа. Для сравнения предложенных алгоритмов с методом факторизации и методом факторизации с предварительной декомпозицией приводятся результаты численных экспериментов.

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

Работа выполнена в рамках проекта № 0251-2021-0005 ПФИ ИВМиМГ СО РАН

Список литературы

1. Colbourn Ch. J. The combinatorics of network reliability. N.Y: Oxford Univ, press. 1987. P. 160.

2. Hebert Perez-Roses. Sixty Years of Network Reliability // Mathematics in Computer Science. 2018. V. 12. P. 275-293.

3. Yeh W. C. Novel Binary-Addition Tree Algorithm (BAT) for Binary-State Network Reliability Problem // Reliability Engineering and System Safety. 2020. 208: 107448.

4. Valiant L. The complexity of enumeration and reliability problems. // SIAM Journal on Computing. 1979. V. 8. N 3. P. 410-421.

5. Page L. B., Perry J.E. A Practical Implementation of the Factoring Theorem for Network Reliability // IEEE transactions on reliability. 1988. V. 37, N 3. P. 259-267.

6. Rodionova О. K., Rodionov A. S., Choo H. Network Probabilistic Connectivity: Exact Calculation with Use of Chains // ICCSA-2004, Springer Lecture Notes in Computer Sciences. 2004. Vol. 3046. P. 315-324.

7. Мигов Д. А., Нестеров С. H., Родионов А. С. Методы ускорения расчета надежности сетей с ограничением на диаметр // Вестник СибГУТИ. № 1, 2014, С. 49-56.

8. Wood R. К. Triconnected decomposition for computing К-terminal network reliability // Networks. 1989. V. 19. P. 203-220.

9. Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer Lecture Notes in Computer Sciences. 2006. V. 4097. P. 702-709.

10. Burgos J. M., Amoza F. R. Factorization of network reliability with perfect nodes I: Introduction and statements // Discrete Applied Mathematics. 2016. V. 198. P. 82-90.

11. Д. Мигов. Декомпозиция сети по сечениям при расчете ее надежности // Прикладная дискретная математика. 2020. № .47. С. 62-86.

12. Мур Э., Шеннон К. Надежные схемы из ненадежных реле // Кибернетически сб. М.: Иностр, лит. 1960. Вып. 1. С. 109-148.

13. Migov D. A. Formuly dlya bystrogo rascheta veroyatnosti svyaznosti podmnozhestva vershin v grafah nebol’shoj razmernosti // Problemy informatiki, 2010. N 6. P. 10-17.

14. Rodionov A., Migov D. Obtaining and Using Cumulative Bounds of Network Reliability // Chapter no 5 in: System Reliability. Edt. by Constantin Volosencu. ISBN 978-953-51-3705-4. Publisher: InTech. Rijeka, Croatia. 2017. P. 93-112.

статья

Библиографическая ссылка: Коробов А. В., Мигов Д. А. Алгоритмы расчета надежности сети на основе декомпозиционного подхода //"Проблемы информатики", 2023, № 4, с.17-28. DOI: 10.24412/2073-0667-2023-4-17-28.

В.М. Вишневский*, В. И. Клименок**, А.М. Соколов*, А. А. Ларионов*

*Институт проблем управления им. В. А. Трапезникова РАН, 117997, Москва, Россия

"Белорусский Государственный Институт, 220030, Минск, Беларусь

УДК 519.872

DOI: 10.24412/2073-0667-2023-4-29-56

EDN: MEXKRY

ИССЛЕДОВАНИЕ FORK-JOIN СИСТЕМЫ С МАРКОВСКИМ ВХОДНЫМ ПОТОКОМ И РАСПРЕДЕЛЕНИЕМ ВРЕМЕНИ ОБСЛУЖИВАНИЯ ФАЗОВОГО ТИПА

В настоящей работе исследуется fork-join система массового обслуживания с коррелированным марковским входным потоком. Каждая из поступающих в систему заявок разбивается на K запросов, которые попадают для обслуживания на K обслуживающих подсистем. Каждая из подсистем состоит из одного обслуживающего прибора и буфера. Время обслуживания на приборах имеет фазовое распределение. Для частного случая K = 2 получено условие стационарного режима, представлены алгоритмы для расчета стационарного распределения и стационарных показателей производительности системы. Для исследования характеристик производительности fork-join системы в общем случае K > 2 предложен подход, базирующийся на комбинации методов машинного обучения и имитационного моделирования. Приведены результаты численных примеров.

Ключевые слова: fork-join система массового обслуживания, Марковский входной поток, фазовое распределение времени обслуживания, стационарные характеристики производительности, машинное обучение.

Список литературы

1. Vianna Е., Comarela G., Pontes Т., Almeida J., Almeida V., Wilkinson К., Kuno H., Dayal U. Analytical performance models for mapreduce workloads // International Journal of Parallel Programming, 2013, 41(4/495-525.

2. Rizk A., Poloczek F., Ciucu F. Stochastic bounds in Fork-Join queueing systems under full and partial mapping. Queueing Systems, 2016. 83(3-4/261-291.

3. Nguyen M., Alesawi S., Li N., Che H., Jiang H. ForkTail: A black-box fork-join tail latency prediction model for user-facing datacenter workloads // HPDC 2018 — Proceedings of the 2018 International Symposium on High-Performance Parallel and Distributed Computing, 2018. P. 206¬217.

4. Enganti P., Rosenkrantz T., Sun L., Wang Z., Che H., Jiang H. Forkmv: Mean-and-variance estimation of fork-join queuing networks for datacenter applications // 2022 IEEE International Conference on Networking, Architecture and Storage (NAS), 2022. P. 1-8.

5. Flatto L., Hahn S. Two Parallel Queues Created By Arrivals With Two Demands I // SIAM Journal on Applied Mathematics, 1984. 44(5): 1041-1053.

6. Nelson R. D., Tantawi A. N. Approximate analysis of fork/join synchronization in parallel queues // IEEE Trans. Computers, 1988. 37:739-743.

7. Kim C., Agrawala A. K. Analysis of the Fork-Join Queue // IEEE Transactions on Computers, 1989. 38 (2): 250—255.

8. Vann S., Makowski A. M. Interpolation approximations for symmetric Fork-Join queues. Performance Evaluation, 1994. 20(l-3):245-265.

9. Lui J. C. s., Muntz R., Towsley D. Computing performance bounds for fork-join queueing models. 08 2001.

10. Balsamo S., Donatiello L., Van Dijk N. M. Bound performance models of heterogeneous parallel processing systems // IEEE Transactions on Parallel and Distributed Systems, 1998. 9(10):1041 1056.

11. Lebrecht A. S., Knottenbelt W. J. Response time approximations in fork-join queues. 2007.

12. Thomasian A. Analysis of fork/join and related queueing systems // ACM Computing Surveys, 2014, 47(2).

13. Jiang L., Giachetti R. E. A queueing network model to analyze the impact of parallelization of care on patient cycle time // Health Care Management Science, 2008. 11(3/248-261.

14. Armony M., Israelit S., Mandelbaum A., Marmor Y. N., Tseytlin Y., Yom-Tov G. B. On patient flow in hospitals: A data-based queueing-science perspective // Stochastic Systems, 2015. 5(1) :146 194.

15. Narahari Y., Sundarrajan P. Performability analysis of fork-join queueing systems // Journal of the Operational Research Society, 1995. 46(10):1237-1249.

16. Gallien J., Wein L. M. A simple and effective component procurement policy for stochastic assembly systems // Queueing Systems, 2001. 38(2/221-248.

17. Kemper B., Mandjes M. Mean sojourn times in two-queue fork-join systems: Bounds and approximations // OR Spectrum, 2012. 34(3/723-742.

18. Schol D., Vlasiou M., Zwart B. Large Fork-Join Queues with Nearly Deterministic Arrival and Service Times // Mathematics of Operations Research, 2022. 47(2):1335-1364.

19. Qiu Z., Perez J. F., Harrison P. G. Beyond the mean in fork-join queues: Efficient approximation for response-time tails // Performance Evaluation, 2015. 91:99-116.

20. Klimenok V. I. Performance characteristics of the fork-join queuing system // Informatics, 2023. 20(3/50-60.

21. Marin A., Rossi S. Power control in saturated fork-join queueing systems // Performance Evaluation, 2017. 116:101-118.

22. Lee K., Shah N.B., Huang L., Ramchandran K. The MDS queue: Analysing the latency performance of erasure codes // IEEE Transactions on Information Theory, 2017. 63(5/2822-2842.

23. Wang W., Harchol-Balter М., Jiang Н., Scheller-Wolf A., Srikant R. Delay asymptotics and bounds for multi-task parallel jobs // SIGMETRICS Perform. Eval. Rev., jan 2019, 46(3):2-7.

24. Nguyen M., Alesawi S., Li N., Che H., Jiang H. A black-box fork-join latency prediction model for data-intensive applications // IEEE Transactions on Parallel and Distributed Systems, 2020. 31(9):1983 2000.

25. Vishnevsky V., Gorbunova A. V. Application of Machine Learning Methods to Solving Problems of Queuing Theory // Communications in Computer and Information Science, 2022. 1605 CCIS:304- 316.

26. Gorbunova A. V., Vishnevsky V. M. Estimating the response time of a cloud computing system with the help of neural networks / / Advances in Systems Science and Applications, 2020. 20(3): 105 112.

27. Vishnevsky V., Klimenok V., Sokolov A., Larionov A. Performance Evaluation of the Priority Multi-Server System MMAP/PH/M/N Using Machine Learning Methods // Mathematics, 2021. 9(24).

28. Efrosinin D., Vishnevsky V., Stepanova N. Optimal Scheduling in General Multi-Queue System by Combining Simulation and Neural Network Techniques // Sensors, 2023. 23(12).

29. Dieleman N. A., Berkhout J., Heidergott B. A neural network approach to performance analysis of tandem lines: The value of analytical knowledge // Computers and Operations Research, 2023. 152:106124.

30. Lucantoni D. M. New results on the single server queue with a batch markovian arrival process // Communications in Statistics. Stochastic Models, 1991. 7(1):1—46.

31. Dudin A. N., Klimenok V. L, Vishnevsky V. M. The theory of queuing systems with correlated flows. The Theory of Queuing Systems with Correlated Flows, 2019. P. 1-410.

32. Neuts M. F. Matrix-geometric solutions in stochastic models. The Johns Hopkins University Press, 1981, Baltimore.

33. Ozawa T. Sojourn time distributions in the queue defined by a general QBD process // Queueing Systems, 2006. 53(4):203-211.

34. Horvath G. Efficient analysis of the queue length moments of the MMAP/MAP/1 preemptive priority queue. Performance Evaluation, 2012. 69(12):684 700.

35. Vishnevsky V., Larionov A., Ivanov R., Semenova O. Estimation of IEEE 802.11 DCF access performance in wireless networks with linear topology using ph service time approximations and map input // 2017 IEEE 11th International Conference on Application of Information and Communication Technologies (AICT), 2017. P. 1-5.

36. Gordon A.D., Breiman L., Friedman J.H., Olshen R. A., Stone C.J. Classification and Regression Trees // Biometrics, sep 1984. 40(3):874.

37. Friedman J.H. Stochastic gradient boosting // Computational Statistics and Data Analysis, feb 2002.38 (4):367-378.

38. Kingma D. P., Ba J. Adam: A method for stochastic optimization // International Conference on Learning Representations, dec.

статья

Библиографическая ссылка: Вишневский В.М., Клименок В. И., Соколов А.М., Ларионов А. А. Исследование fork¬join системы с марковским входным потоком и распределением времени обслуживания фазового типа //"Проблемы информатики", 2023, № 4, с.29-56. DOI: 10.24412/2073-0667-2023-4-29-56.

С. В. Бредихин, Н. Г. Щербакова, А. Н. Юргенсон

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 519.177

DOI: 10.24412/2073-0667-2023-4-57-72

EDN: OGXEXX

МОДЕЛИ СЕТИ СОАВТОРСТВА НАУЧНОГО ЖУРНАЛА. ЧАСТЬ 2.

Анализируются две модели сети научного соавторства. Первая, построенная на бинарных отношениях, возникающих между авторами, совместно создавшими по крайней мере одну статью, представлена в виде неориентированного графа, вершины которого соответствуют авторам, а ребра устанавливают связи между ними. Вторая, учитывающая групповые отношения между авторами одной статьи, представлена в виде двудольного графа. Приведены методы конструирования обеих моделей на основе данных, извлеченных из XML-архива статей научного журнала. Измерены базовые параметры моделей, центральность ее вершин и выявлены шаблоны сотрудничества. Оценена публикационная активность организаций, указанных в аффилиации авторов. Эта работа продолжает изучение и апробацию методов анализа сетей соавторства [1, 2].

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

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН (FWNM-2022-0005).

Список литературы

1. БРЕДИХИН С. В., ЛЯПУНОВ В. М., ЩЕРБАКОВА Н. Г. Структура и параметры невзвешенной сети соавторства на основе данных БД RePEc // Пробл. информ. 2021. № 3. С. 56-67. DOI: 10.24411/2073-0667-2021-3-56-57.

2. БРЕДИХИН С. В., ЩЕРБАКОВА Н. Г. Модель сети соавторства научного журнала // Пробл. информ. 2023. № 3. С. 5-18. DOI: 10.24412/2073-0667-2023-3-5-18.

3. 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.

4. DOROGOVTSEV S. X., MENDES J. F. F. Evolution of networks // Advances in Phys. 2002. V. 51, iss. 4. P. 1079-1187. DOI: 10.1080/00018730110112519.

5. NEWMAN M. E. J. The structure and function of complex networks // SIAM Rev. 2003. V. 45, iss. 2. P. 167-256. DOI: 10.1137/S003614450342480.

6. BOCCALETTI S., LATORA V., MORENO Y., CHAVEZ M., HWANG D. U. Complex networks: Structure and dynamics // Phys. Rep. 2006. V. 424, iss. 4-5. P. 175-308. DOI: 10.1016/j.physrep.2005.10.009.

7. BARRAT A., BARTHELEMY М., VESPIGNANI A. Dynamic processes on complex networks. Cambridge University Press, 2008. ISBN: 9780511791383.

8. NEWMAN M. E. J. Scientific collaboration networks. I. Network construction and fundamental results // Phys. Rev. E. 2001. V. 64, iss. 1. 016131. DOI: 10.1103/PhysRevE.64.016131.

9. NEWMAN M. E. J. Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality // Phys. Rev. E. 2001. V. 64, iss. 1, 016132. DOI: 10.1103/PhysRevE.64.016132.

10. UDDIN S., HOSSAIN L., ABBASI A., RASMUSSEN K. Trend and efficiency analysis of co¬authorship network // Scientometrics. 2012. V. 90, iss. 2. P. 687-699. DOI: 10.1007/sl1192-011-0511-x.

П. SAVIC M., IVANOVIC M., RADOVANOVIC M., OGNJANOVIC Z., PEJOVIC A. Exploratory analysis of communities in co-authorship networks: A case study // Intern. Conf, on ICT Innovations, Ohrid (North Macedonia), 2014. P. 55-64.

12. 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.

13. 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.

14. 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.

15. PATANIA A., PETRI G., VACCARINO F. The shape of collaboration // EPJ Data Sci. 2017.

V. 6, 18. DOI: 10.1140/epjds/sl3688-017-0114-8.

16. SEIDMAN S. B. 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.

17. ESTRADA E., RODRIGUEZ-VELAZQUEZ J. A. Complex networks as hypergraphs // arXiv: physics/0505137. 2005. DOI: 10.1016/j.physa.2005.12.002.

18. 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.

19. GUILLAUME J. L., LATAPY M. Bipartite graphs as models of complex networks // Phys. A: Stat. Meehan, and its Appl. 2006. V. 371, iss. 2. P. 795-813. DOI: 10.1016/j.physa.2006.04.047.

20. 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.

21. FAUST K. Centrality in affiliation networks // Soc. Networks. 1997. V. 19. P. 157-191. DOI: 10.1016/80378-8733(96)00300-0.

22. WASSERMAN S., FAUST K. Social network analysis: Methods and applications. Cambridge Univ. Press, 1994. ISBN: 9780511815478. DOI: 10.1017/CBO9780511815478.

23. BREIGER R. L. The duality of persons and groups // Soc. Forces. 1974. V. 53, iss. 2. P. 181-190. DOI: 10.2307/2576011.

24. EVERETT M. G., BORGATTI S. P. The dual-projection approach for two-mode networks // Soc. Networks. 2013. V. 35, iss. 2. P. 204-210. DOI: 10.1016/j.socnet.2012.05.004.

25. EVERETT M. G. Centrality and the dual-projection approach for two-mode social network data // Method. Innov. 2016. V. 9. P. 1-8. DOI: 10.1177/2059799116630662.

26. LATAPY M., MAGNIEN C., DEL VECCHIO N. Basic notions for the analysis of large two-mode networks // Soc. Networks. 2008. V. 30, iss. 1. P. 31-48. DOI: 10.1016/j.socnet.2007.04.006.

27. NEWMAN M. E. J., WATTS D. J., STROGATZ S. H. Random graph models of social networks // Proc. Natl. Acad. Sci. USA. 2002. V. 99. P. 2566-2572. DOI: 10.1073/pnas.01258299.

28. ДИСТЕЛЬ P. Теория графов. Пер. с англ. Новосибирск: Ин-т математики, 2002. ISBN 5-86134-101-Х.

29. SCHMIDT М. The Sankey diagram in energy and material flow management. Part II: Methodology and current applications // J. Indust. Ecol. 2008. V. 12, iss. 2. P. 173-185. DOI: 10. 1111/j.1530-9290.2008.00015.x.

30. КОРМЕН Т., ЛЕЙЗЕРСОН Ч., РИВЕСТ Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2002. ISBN: 5-900916-37-5.

31. БРЕДИХИН С. В., ЛЯПУНОВ В. М., ЩЕРБАКОВА Н. Г. Библиометрические сети научных статей и журналов. Новосибирск: ИВМиМГ СО РАН, 2021. ISBN: 978-5-901548-44-8.

32. FREEMAN L. С. A set of measures of centrality based upon betweenness // Sociometry. 1977. V. 40. P. 35-41. DOI: 10.2307/3033543.

33. BAVELAS A. Communication patterns in task-oriented groups // J. Acoustical Soc. of Amer. 1950. V. 22, iss. 6. P. 725-730. DOI: 10.1121/1.1906679.

34. BONACICH P. Factoring and weighting approaches to status scores and clique identification // J. Math. Soc. 1972. V. 2. P. 113-120. DOI: 10.1080/0022250X.1972.9989806.

35. BONACICH P. Simultaneous group and individual centralities // Soc. Networks. 1991. V. 13, iss. 2. P. 155-168. DOI: 10.1016/0378-8733(91)90018-0.

36. BRIN S., PAGE L. The Anatomy of a large-scale hypertextual web search engine // Comput. Networks and ISDN Syst. 1998. V. 30. P. 107-117. DOI: 10.1016/S0169-7552(98)00110-X.

37. BONDY J. A., MURTY U. S. R. Graph theory with applications. North-Holland, 1976. ISBN: 0-444-19451-7.

38. ZHANG Y., ET AL. On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types // BMC Bioinform. 2014. V. 15, iss. 110. DOI: 10.1186/1471-2105-15-110.

39. LIND P. G., GONZALEZ M. C., HERRMANN H. J. Cycles and clustering in bipartite networks // Phys. Rev. 2005. V. 72, iss. 5. 056127. DOI: 10.1103/PhysRevE.72.056127.

40. WATTS D. J., STROGATZ S. H. Collective dynamics of small-world’ networks // Nature. 1998. V. 393. P. 440-442. DOI: 10.1038/30918.

статья

Библиографическая ссылка: Бредихин С. В., Щербакова Н. Г., Юргенсон А. Н. Модели сети соавторства научного журнала. Часть 2.//"Проблемы информатики", 2023, № 4, с.57-72. DOI: 10.24412/2073-0667-2023-4-57-72.

М. П. Бакулина

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 519.722

DOI: 10.24412/2073-0667-2023-4-73-77

EDX: QBTMBL

ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ СЖАТИЯ ИЗОБРАЖЕНИЙ НА ОСНОВЕ МЕТОДА RLE

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

Ключевые слова: кодирование без потерь, растровое изображение, RLE, коэффициент сжатия.

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН 0251-2022-0005.

Список литературы

1. Тропченко А.Ю, Тропченко А. А. Методы сжатия изображений, аудиосигналов и видео. СПб:СПбГУ ИТМО, 2009.108 с.

2. Bell Т.С., Moffat A., Witten I. Н. Compressing the Digital Library//Proc.Digital Libraries—Texas: College Station,1994.P.41-46.

3. Jiawan Zh., Jizhou S., Zhigang S. Accelerate volume splatting by using run length encoding // Lecture Notes in Computer Science. 2003. V. 2657. P. 907-914.

4. Witten I. H., Neal R., Cleary J. G. Arithmetic coding for data compression // Comm. ACM. 1987. V. 30, N 6. P. 520-540.

5. Сэломон M. Сжатие данных, изображений и звука. М.: Техносфера, 2004. 368 с.

статья

Библиографическая ссылка: Бакулина М. П. Повышение эффективности сжатия изображений на основе метода RLE //"Проблемы информатики", 2023, № 4, с.73-77. DOI: 10.24412/2073-0667-2023-4-73-77.

А. Р. Герб, Г. А. Омарова

Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия

УДК 519.17+519.61

DOI: 10.24412/2073-0667-2023-4-78-87

EDX: WBDTOQ

АЛГОРИТМЫ РАЗБИЕНИЯ ГРАФОВ НА GPU

В данной работе рассматриваются два модифицированных и реализованных на GPU алгоритма: алгоритм меток и алгоритм Ja-Be-Ja. Проведен сравнительный анализ работы на больших графах.

Ключевые слова: граф, GPU, разреженная матрица, итерации, минимальный разрез.

Работа выполнена при финансовой поддержке Министерства пауки и высшего образования Российской Федерации (код проекта: 0251-2022-0001).

Список литературы

1. CUDA С Programming Guide 7.5. ed: NVIDIA Corporation, 2016.

2. Timothy A. Davis and Yifan Hu. The University of Florida Sparse Matrix Collection. ACM Transactions on Mathematical Software 38, 1, Article 1 (December 2011), 25 pages. DOI: https://doi.org/10.1145/2049662.2049663, 2011.

3. Meyerhenke H., Monien B., Schamberger S. Graph partitioning and disturbed diffusion Parallel Computing. 2009. V. 35, iss. 10-11. P. 544-569.

4. Gottesburen L. et al. Deep multilevel graph partitioning. arXiv preprint arXiv:2105.02022. 2021.

5. Kumar R., Charpiat G., Thonnat M. Multiple object tracking by efficient graph partitioning // Computer Vision-ACCV 2014: 12th Asian Conference on Computer Vision, Singapore (Singapore), Nov. 1-5, 2014. Revised Selected Papers, Part IV 12. Springer International Publishing, 2015.

6. Subelj L., Bajec M. Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction // Physical Review E. 2011. V. 83, iss. 3.

7. Raghavan U. N., Albert R., Kumara S. Near linear time algorithm to detect community structures in large-scale networks // Physical review E. 2007. V. 52, No 3.

8. Rahimian F., et al. Ja-be-ja: A distributed algorithm for balanced graph partitioning // IEEE 7th International Conference on Self-Adaptive and Self-Organizing Systems. IEEE, 2013. (с) А. Р. Герб, Г. А. Омарова, 2023

статья

Библиографическая ссылка: Герб А. Р., Омарова Г. А. Алгоритмы разбиения графов на GPU //"Проблемы информатики", 2023, № 4, с.78-87. D

Main menu

You are here

2023 №4(61)