ellibsЭлектронные библиотекиRussian Digital Libraries Journal1562-5419Казанский (Приволжский) федеральный университет10.26907/1562-5419-2019-22-1-2-36ellibs-103Research ArticleСтатьиИспользование матриц смежности для визуализации больших графовUsing adjacency matrices for visualization of large graphsАпановичЗ. В.apanovich@iis.nsk.suИнститут систем информатики им. А.П. Ершова Сибирского отделения Российской академии наукRussian Federation201928022019221236Copyright © Апанович З.В., 20192019Апанович З.В.Апанович З.В.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ellibs.elpub.ru/jour/article/view/103

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

Exponential size growth of such graphs as social networks, Internet graphs, etc. requires new approaches to their visualization. Along with node-link diagram representations, adjacency matrices and various hybrid representations are increasingly used for large graphs visualizations. This survey discusses new approaches to the visualization of large graphs using adjacency matrices and gives examples of applications where these approaches are used. We describe various types of patterns arising when adjacency matrices corresponding to modern networks are ordered, and algorithms making it possible to reveal these patterns. In particular, the use of matrix ordering methods in conjunction with algorithms looking for such graph patterns as stars, false stars, chains, near-cliques, full cliques, bipartite cores and near-bipartite cores enable users to create understandable visualizations of graphs with millions of vertices and edges. Examples of hybrid visualizations using node-link diagrams for representing sparse parts of a graph and adjacency matrices for representing dense parts are also given. The hybrid methods are used to visualize co-authorship networks, deep neural networks, to compare networks of the human brain connectivity, etc.

графы большого объемавизуализацияматрицы смежностижгуты ребергибридная визуализацияlarge graphsvisualizationadjacency matricesedge bundleshybrid visualizationReferencesLiiv I. Seriation and matrix reordering methods: An historical overview// Statistical analysis and data mining. 2010. V. 3, No. 2. P. 70–91.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.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.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.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.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.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. 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., 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.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.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.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.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.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.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.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.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.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.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. 5Fekete 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. 5Behrisch 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.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.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.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.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.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.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.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.06275Hegde 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.06275Krizhevsky A., Sutskever I., Hinton G.E. Imagenet classification with deep convolutional neural networks// NIPS. 2012. P. 1–9.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.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.3411Kang 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.3411Kang 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.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.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.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.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.2598472Yang 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.2598472Holten 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.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.Апанович З.В. Методы построения жгутов ребер для улучшения понимаемости информации// Проблемы управления и моделирования в сложных системах труды XV Международной конференции. 2013. С. 439–445.Апанович З.В., Винокуров П.С., Кислицина Т.А. Методы и средства визуализации больших научных порталов//Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2011. Т. 9. № 3. С. 5–14.Апанович З.В., Винокуров П.С., Кислицина Т.А. Методы и средства визуализации больших научных порталов//Вестник Новосибирского государственного университета. Серия: Информационные технологии. 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.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.2598831Liu 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

The authors declare that there are no conflicts of interest present.