УДК 519.677

ПРИКЛАДНЫЕ АСПЕКТЫ ИСПОЛЬЗОВАНИЯ АЛГОРИТМОВ РАНЖИРОВАНИЯ ДЛЯ ОРИЕНТИРОВАННЫХ ВЗВЕШЕННЫХ ГРАФОВ(НА ПРИМЕРЕ ГРАФОВ СОЦИАЛЬНЫХ СЕТЕЙ)

В.В. Печенкин, М.С. Королёв, Л.В. Димитров

Аннотация


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

Ключевые слова


ранжирование; ориентированный граф; взвешенный граф; инкрементальный алгоритм; локальный алгоритм

Полный текст:

PDF

Литература


  1. Кочетов Ю.А., Хмелев А.В. Гибридный алгоритм локального поиска для задачи маршрутизации разнородного ограниченного автопарка // Дискретный анализ и исследование операций. 2015. Т. 22. № 5. C. 5–29.
  2. Кривошеин Д.Ю., Марченко А.М. Алгоритмы пересчёта кратчайших путей в графе при изменении весов ребер // Проблемы разработки перспективных микро– и наноэлектронных систем. 2012. № 1. С. 263–266.
  3. Demetrescu C., Finocchi I., Italiano G.F. Dynamic graphs. URL: www.diku.dk/PATH05/CRC-book1.pdf (дата обращения: 01.02.17).
  4. Pearce D.J., Kelly P.H.J. A dynamic topological sort algorithm for directed acyclic graphs // Journal of Experimental Algorithmics (JEA). 2007. vol. 11. pp. 1–7.
  5. Deepak А., Tobias F. Average-Case Analysis of Incremental Topological Ordering // Discrete Applied Mathematics. 2010. vol. 158. no. 4. pp. 240–250.
  6. Nicoara D., Kamali S., Daudjee K., Chen L. Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases // EDBT. 2015. pp. 25-36.
  7. Ammar A.B. Query optimization techniques in graph Databases // International Journal of Database Management Systems (IJDMS). 2016. vol. 8. no. 4. 14 p.
  8. Курейчик В.В., Жиленков М.А. Муравьиный алгоритм для решения оптимизационных задач с явно выраженной целевой функцией // Информатика, вычислительная техника и инженерное образование. 2015. № 2. С. 1–12.
  9. Agarw S. Ranking on Graph Data // Proceedings of the 23rd International Conference on Machine Learning. 2006. pp. 25–32.
  10. Розенберг И.Н. Использование нечетких представлений данных при определении медиан графа // Известия Южного федерального университета. Технические науки. 2001. № 4. С. 64–72.
  11. Adaikalam A., Manikandan S., Rajamani V. Fuzzy graph based shortest path ranking method for optical network // Optical and Quantum Electronics. 2017. vol. 49. no. 9. 296 p.
  12. Barman A., Shah S.K. SHaPE: A Novel Graph Theoretic Algorithm for Making Consensus-Based Decisions in Person Re-identification Systems // IEEE International Conference on Computer Vision (ICCV). 2017. pp. 1124–1133.
  13. Roffo G., Melzi S., Castellani U., Vinciarelli A. Infinite Latent Feature Selection: A Probabilistic Latent Graph-Based Ranking Approach // IEEE International Conference on Computer Vision (ICCV). 2017. pp. 1407–1415.
  14. Печенкин В.В., Решетников Д.С., Ярская-Смирнова В.Н. Визуализация сетевой структуры групповых отношений // 4М. Методология, методы, математическое моделирование. 2014. № 39. С. 40–61.
  15. Королёв М.С., Решетников Д.С. Подходы к задаче ранжирования вершин в теории графов // Проблемы управления в социально-экономических и технических системах. 2017. С. 138–141.
  16. Lumbreras A., Gavaldà R. Applying trust metrics based on user interactions to recommendation in social networks // Advances in Social Networks Analysis and Mining (ASONAM), IEEE/ACM International Conference. 2012. рp. 1159–1164.
  17. Jameson K.A., Appleby M.C., Freeman L.C. Finding an appropriate order for a hierarchy based on probabilistic dominance // Animal Behaviour. 1999. vol. 57. no. 5. рр. 991–998.
  18. Easy visualizations of PageRank and Page Groups with Gephi. URL: https://searchengineland.com/easy-visualizations-pagerank-page-groups-gephi-265716 (дата обращения: 07.02.2017).
  19. Sarma A. Das, Molla A.R., Pandurangan G., Upfal E. Fast distributed pagerank computation // Theoretical Computer Science. 2015. vol. 561. pp. 113–121.
  20. Dai L., Freris N.M. Fully distributed PageRank computation with exponential convergence // 2017. arXiv preprint arXiv:1705.09927. 5 p.
  21. Nathan E., Fairbanks J., Bader D. Ranking in Dynamic Graphs using Exponential Centrality // International Workshop on Complex Networks and their Applications. Springer. 2017. pp. 378–389.
  22. Рыков Ю.Г., Кольцова О.Ю., Мейлахс П.А. Структура и функции онлайн-сообществ: сетевая картография ВИЧ-релевантных групп в социальной сети «ВКонтакте» // Социологические исследования. 2016. № 8. С. 30–42.


Виталий Владимирович Печенкин - д-р социол. наук, профессор, профессор кафедры прикладных информационных технологий института прикладных информационных технологий и коммуникаций, Саратовский государственный технический университет имени Гагарина Ю.А..
Область научных интересов: оптимизационные задачи на графах и сетях, визуализация графов, методы статистической обработки многомерных данных, многомерное шкалирование, анализ социальных сетей, использование математических и компьютерных подходов в социологических исследованиях.
Число научных публикаций: 110.

Адрес (E-mail): pechenkinvv@mail.ru
Почтовый адрес: Политехническая, 77, Саратов, 41005
Телефон: +7(8452)99-87-15


Михаил Сергеевич Королёв - аспирант кафедры прикладных информационных технологий института прикладных информационных технологий и коммуникаций, Саратовский государственный технический университет имени Гагарина Ю.А., ассистент кафедры кафедры прикладных информационных технологий института прикладных информационных технологий и коммуникаций, Саратовский государственный технический университет имени Гагарина Ю.А..
Область научных интересов: алгоритмы и методы оптимизации, виртуальная реальность, дополненная реальность, 3D-проектирование, 3D-моделирвоание, архитектурная визуализация, компьютерное зрение, компьютерный дизайн..
Число научных публикаций: 8.

Адрес (E-mail): koroliow.mikhail@yandex.ru
Почтовый адрес: Политехническая, 77, Саратов, 41005
Телефон: +7(8452)99-87-15


Любомир Ванков Димитров - д-р физ.-мат. наук, профессор, проректор по учебной деятельности и аккредитации, Технический университет - София, профессор машиностроительного факультета, Технический университет - София.
Область научных интересов: мехатроника, автоматика, микроэлектронные модули и системы и их применение (MEMS).
Число научных публикаций: 230.

Адрес (E-mail): lubomir_dimitrov@tu-sofia.bg
Почтовый адрес: бул. Св. Климент Охридски, 8, София, 1756, Болгария
Телефон: +359 2 965-25 60




DOI: http://dx.doi.org/10.15622/sp.61.4

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.