Прикладные аспекты использования алгоритмов ранжирования для ориентированных взвешенных графов(на примере графов социальных сетей)
Ключевые слова:
ранжирование, ориентированный граф, взвешенный граф, инкрементальный алгоритм, локальный алгоритмАннотация
Рассматриваются прикладные аспекты использования предварительного ранжирования вершин ориентированного взвешенного графа. Особое внимание уделяется широкому использованию такого приема в разработке эвристических алгоритмов дискретной оптимизации. Задача ранжирования имеет непосредственное отношение к проблеме определения центральности в социальных сетях, обработке больших массивов данных реального мира, но как показано в статье, явно или косвенно используется при разработке алгоритмов решения прикладных задач в качестве начального этапа построения решения. Приводятся примеры использования предварительного ранжирования, в которых продемонстрировано повышение эффективности решения некоторых прикладных задач, имеющих широкое применение в математических методах оптимизации. Дано описание структуры первой фазы вычислительного эксперимента, которая связана с получением тестовых наборов данных. Полученные данные представлены взвешенными графами, которые соответствуют нескольким группам социальной сети ВКонтакте с числом вершин в диапазоне от 9000 до 24 тысяч участников. Показано, что структурные характеристики полученных графов по числу компонент связности существенно различаются. Продемонстрированы некоторые характеристики центральности (распределения степенных последовательностей), которые имеют экспоненциальный характер. Основное внимание уделяется анализу трех алгоритмов построения иерархии ранжирования вершин графов, предлагаются новые подходы к вычислению рангов вершин с использованием информации об активности пользователей в социальных сетях. Проводится сравнение распределений полученных совокупностей рангов. Вводится понятие сходимости алгоритмов ранжирования вершин графов, а также обсуждаются различия их использования при рассмотрении данных большой размерности и необходимости построения решения в случае учета только локальных изменений.Литература
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.
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.
Опубликован
2018-11-30
Как цитировать
Печенкин, В. В., Королёв, М. С., & Димитров, Л. В. (2018). Прикладные аспекты использования алгоритмов ранжирования для ориентированных взвешенных графов(на примере графов социальных сетей). Труды СПИИРАН, 6(61), 94-118. https://doi.org/10.15622/sp.61.4
Раздел
Математическое моделирование и прикладная математика
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
