Использование матриц смежности для визуализации больших графов

Article Sidebar

PDF
Опубликован: 28.05.2019
УДК 004.021 004.42
DOI: https://doi.org/10.26907/1562-5419-2019-22-1-2-36
Выпуск
Том 22 № 1 (2019)

Main Article Content

Зинаида Владимировна Апанович
Институт систем информатики им. А.П. Ершова Сибирского отделения Российской академии наук, пр. Академика Лаврентьева, 6, Новосибирск, Новосибирская обл., 630090

Аннотация

Экспоненциальный рост размеров таких графов, как социальные сети, интернет-графы и др., требует новых подходов к их визуализации. Наряду с представлениями типа «диаграммы связей вершин» все чаще используются визуализации матриц смежностей, а также разнообразные комбинации этих представлений. В данном обзоре рассмотрены новые подходы к визуализации графов большого объема при помощи матриц смежностей и приведены примеры приложений, где эти подходы применяются. Описаны различные типы шаблонов, возникающие при упорядочении матриц смежностей, соответствующих современным сетям, и алгоритмы, позволяющие выделять эти шаблоны. В частности, продемонстрировано, как использование методов упорядочения матриц совместно с алгоритмами поиска таких шаблонов, как звезды, ложные звезды, цепи, почти клики, полные клики, двудольные ядра и почти двудольные ядра, позволяют создавать понятные визуализации графов, имеющих миллионы вершин и ребер. Также приведены примеры гибридных визуализаций, использующих диаграммы связей вершин для представления неплотных частей графа, а матрицы смежностей – для представления плотных частей и их приложений. Гибридные методы используются для визуализации сетей соавторства, глубоких нейронных сетей, сравнения сетей связности человеческого мозга и др.

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

графы большого объема, визуализация, матрицы смежности, жгуты ребер, гибридная визуализация.

Article Details

Как цитировать
Апанович, З. В. (2019). Использование матриц смежности для визуализации больших графов . Электронные библиотеки, 22(1), 2-36. https://doi.org/10.26907/1562-5419-2019-22-1-2-36
Биография автора

Зинаида Владимировна Апанович

Старший научный сотрудник Института Систем Информатики СО РАН, доцент Новосибирского государственного университета. Сфера научных интересов – визуализация информации, визуализация графов, Semantic Web.

Библиографические ссылки

Liiv I. Seriation and matrix reordering methods: An historical overview// Statistical analysis and data mining. 2010. V. 3, No. 2. P. 70–91.
Petrie F.W.M. Sequences in prehistoric remains// J. Anthropol. Inst. Great Britain and England. 1899. V. 29, No. 3/4. P. 295–301.
Czekanowski J. Zur differentialdiagnose der Neandertalgruppe// Korrespondenzblatt Deutsch Ges Anthropol Ethnol Urgesch XL.1909. V. 6, No. 7. S. 44–47.
Forsyth E., Katz L. A matrix approach to the analysis of sociometric data: preliminary report// Sociometry. 1946. V. 9, No. 4. P. 340–347.
Ghoniem M., Fekete J.D., Castagliola P. On the readability of graphs using node-link and matrix-based representations: a controlled experiment and statistical analysis //Information Visualization. 2005. V. 4, No. 2. P. 114–135.
Díaz J., Petit J., Serna M. A survey of graph layout problems// ACM Comput. Surv. 2002. V. 34, No. 3. P. 313–356.
Mueller C., Martin B., Lumsdaine A. A comparison of vertex ordering algorithms for large graph visualization// Visualization, 2007. APVIS’07. 2007 6th International Asia-Pacific Symposium on Visualization. 2007. IEEE. P. 141–148.
Mueller C., Martin B., Lumsdaine A. Interpreting large visual similarity matrices// 2007 6th International Asia-Pacific Symposium on Visualization, 2007. IEEE. P. 149–152.
Mueller C., Martin B., Cottam J., Lumsdaine A. Matrix representations of graphs. URL: https://www.slideserve.com/amandla/matrix-res-of-graphs.
Cuthill E., MCkee J. Reducing the bandwidth of sparse symmetric matrices// Proceedings of the 1969 24th National Conference (New York, NY, USA, 1969), ACM ’69, ACM. P. 157–172.
King I.P. An automatic reordering scheme for simultaneous equations derived from network systems// International J. for Numerical Methods in Engineering. 1970. V. 2, No. 4. P. 523–533.
Sloan S.W. An algorithm for profile and wavefront reduction of sparse matrices// International J. for Numerical Methods in Engineering. 1986. V. 23, No. 2. P. 239–251.
Blandford D., Blelloch G., Kash I. Compact representations of separable graphs //Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA). 2003. P. 679–688.
West D.B. Introduction to Graph Theory, Prentice-Hall, Inc., 1996. P. 436–449.
Wei T. Corrplot. Visualization of a correlation matrix // r package version 0.73. ed., 2013. URL: https://github.com/taiyun/corrplot.
Kaiser S., Leicsh F. A toolbox for bicluster analysis in r. 2008. URL: https://www.researchgate.net/publication/33029412_A_Toolbox_for_Bicluster_Analysis_in_R.
Hahsler M., Hornik K., Buchta C. Getting things in order: An introduction to the r package seriation// J. of Statistical Software. 2008. V. 25, No. 3. P. 1–34.
Siek J.G., Lee L.-Q., Lumsdaine A. The Boost Graph Library: User Guide and Reference Manual// Pearson Education. 2001. P. 352.
Fekete J.-D. Reorder.js: A JavaScript Library to Reorder Tables and Networks// IEEE VIS 2015, Oct. 2015. Poster. URL: https://hal.inria.fr/hal-01214274. 5
Behrisch M., Bach B., Henry N. Riche, Schreck T., Fekete J.-D. Matrix Reordering Methods for Table and Network Visualization // EuroVis 2016. 2016. V. 35, No. 3. P. 1–24.
Koren Y., Harel D. A multi-scale algorithm for the linear arrangement problem// Revised Papers from the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (London, UK, UK, 2002), WG ’02, Springer-Verlag. 2002. P. 296–309.
Hubert L. Some applications of graph theory and related nonmetric techniques to problems of approximate seriation the case of symmetric proximity measures// British J. of Mathematical and Statistical Psychology. 1974. V. 27, No. 2. P. 133–153.
Gruwaeus G., Wainer H. Two additions to hierarchical cluster analysis//British J. of Mathematical and Statistical Psychology. 1972. V. 25, No. 2. P. 200–206.
George J.A. Computer implementation of the finite element method// PhD thesis, Stanford University. 1971. P. 1–228.
Behrisch M. et al. Magnostics: Image-Based Search of Interesting Matrix Views for Guided Network Exploration //IEEE Transactions on Visualization & Computer Graphics. 2017. V. 23, No. 1. P. 31–40.
Ke Wu, Watters P., Magdon-Ismail M. Network Classification Using Adjacency Matrix Embeddings and Deep Learning//2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). 2016.
Hegde K., Magdon-Ismail M., Ramanathan R., Thapa B. Network Signatures from Image Representation of Adjacency Matrices: Deep Transfer Learning for Subgraph Classification. 2018. URL: https://arxiv.org/abs/1804.06275
Krizhevsky A., Sutskever I., Hinton G.E. Imagenet classification with deep convolutional neural networks// NIPS. 2012. P. 1–9.
Abello J. van Ham F. Matrix zoom: A visual interface to semi-external graphs// IEEE InfoVis. 2004. P. 183–190.
Kang U., Faloutsos C. Beyond ’caveman communities’: Hubs and spokes for graph compression and mining // ICDM. 2011. P. 300–309. URL: https://arxiv.org/ abs/1406.3411
Kang U., Lee J.-Y., Koutra D., Faloutsos C. Net-ray: Visualizing and mining billion-scale graphs // Adv in Knowledge Discovery and Data Mining. Springer. 2014. P. 348–361.
Koutra D., Kang U., Vreeken J., Faloutsos C. Vog: Summarizing and understanding large graphs // Proc. SIAM Int Conf on Data Mining (SDM), Philadelphia, PA. 2014. URL: https://arxiv.org/abs/1406.3411.
Gualdron H., Cordeiro R., Rodrigues J. StructMatrix: Large-scale visualization of graphs by means of structure detection and dense matrices // The Fifth IEEE ICDM Workshop on Data Mining in Networks. 2015. P. 1–8.
Henry N., Fekete J.-D., McGun M. J. Nodetrix: a hybrid visualization of social networks// IEEE Transactions on Visualization and Computer Graphics, 2007. URL: https://arxiv.org/abs/1406.3411. V. 13. P. 1302–1309.
Yang X., Shi L., Daianu M., Tong H., Liu Q., Thompson P. Blockwise human brain network visual comparison using NodeTrix representation// IEEE Trans Vis ComputGraph. 2017.  V. 23, No. 1. P. 181–190. doi: 10.1109/tvcg.2016.2598472
Holten D. Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data// IEEE Transactions on Visualization and Computer Graphics. 2006. V. 12, No. 5. P. 741–748.
Апанович З.В. Методы построения жгутов ребер для улучшения понимаемости информации// Проблемы управления и моделирования в сложных системах труды XV Международной конференции. 2013. С. 439–445.
Апанович З.В., Винокуров П.С., Кислицина Т.А. Методы и средства визуализации больших научных порталов//Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2011. Т. 9. № 3. С. 5–14.
Yang Y., Dwyer T., Goodwin S., Marriott K. Many-to-Many Geographically-Embedded Flow Visualisation: An Evaluation// IEEE Transactions on Visualization & Computer Graphics. 2017. V. 23, No. 1. P. 411–420.
Liu M., Shi J., Li Z., Li C., Zhu J., Liu S. Towards Better Analysis of Deep Convolutional Neural Networks// IEEE Transactions on Visualization & Computer Graphics. 2017. V. 23, No. 1. P. 91–100. doi:10.1109/TVCG.2016.2598831


Представляя статьи для публикации в журнале «Электронные библиотеки», авторы автоматически дают согласие предоставить ограниченную лицензию на использование материалов Казанскому (Приволжскому) федеральному университету (КФУ) (разумеется, лишь в том случае, если статья будет принята к публикации). Это означает, что КФУ имеет право опубликовать статью в ближайшем выпуске журнала (на веб-сайте или в печатной форме), а также переиздавать эту статью на архивных компакт-дисках журнала или включить в ту или иную информационную систему или базу данных, производимую КФУ.

Все авторские материалы размещены в журнале «Электронные библиотеки» с ведома авторов. В случае, если у кого-либо из авторов есть возражения против публикации его материалов на данном сайте, материал может быть снят при условии уведомления редакции журнала в письменной форме.

Документы, изданные в журнале «Электронные библиотеки», защищены законодательством об авторских правах, и все авторские права сохраняются за авторами. Авторы самостоятельно следят за соблюдением своих прав на воспроизводство или перевод их работ, опубликованных в журнале. Если материал, опубликованный в журнале «Электронные библиотеки», с разрешения автора переиздается другим издателем или переводится на другой язык, то ссылка на оригинальную публикацию обязательна.

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

При использовании материалов из журнала обязательна ссылка на URL: http://elbib.kpfu.ru. Любые изменения, дополнения или редактирования авторского текста недопустимы. Копирование отдельных фрагментов статей из журнала разрешается только для научных исследований и персонального использования, но не для коммерческого использования, перепродажи или передачи другому лицу.

Запросы на право переиздания или использования любых материалов, опубликованных в журнале «Электронные библиотеки», следует направлять главному редактору Елизарову А.М. по адресу: [email protected]

Издатели журнала «Электронные библиотеки» не несут ответственности за точки зрения, излагаемые в публикуемых авторских статьях.

Предлагаем авторам статей загрузить с этой страницы, подписать и выслать в адрес издателя журнала по электронной почте скан Авторского договора о передаче неисключительных прав на использование произведения.