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

Main Article Content

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

Аннотация

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

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