Using adjacency matrices for visualization of large graphs

Article Sidebar

PDF (Русский)
Published: 28.05.2019
UDC 004.021 004.42
DOI: https://doi.org/10.26907/1562-5419-2019-22-1-2-36
Issue
Vol. 22 No. 1 (2019)

Main Article Content

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

Abstract

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.

Article Details

Author Biography

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

Senior researcher of the Institute of Informatics Systems of SB RAS, Associate Professor of Novosibirsk State University. Research interests include information visualization, graph visualization, Semantic Web.

References

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


Presenting an article for publication in the Russian Digital Libraries Journal (RDLJ), the authors automatically give consent to grant a limited license to use the materials of the Kazan (Volga) Federal University (KFU) (of course, only if the article is accepted for publication). This means that KFU has the right to publish an article in the next issue of the journal (on the website or in printed form), as well as to reprint this article in the archives of RDLJ CDs or to include in a particular information system or database, produced by KFU.

All copyrighted materials are placed in RDLJ with the consent of the authors. In the event that any of the authors have objected to its publication of materials on this site, the material can be removed, subject to notification to the Editor in writing.

Documents published in RDLJ are protected by copyright and all rights are reserved by the authors. Authors independently monitor compliance with their rights to reproduce or translate their papers published in the journal. If the material is published in RDLJ, reprinted with permission by another publisher or translated into another language, a reference to the original publication.

By submitting an article for publication in RDLJ, authors should take into account that the publication on the Internet, on the one hand, provide unique opportunities for access to their content, but on the other hand, are a new form of information exchange in the global information society where authors and publishers is not always provided with protection against unauthorized copying or other use of materials protected by copyright.

RDLJ is copyrighted. When using materials from the log must indicate the URL: index.phtml page = elbib / rus / journal?. Any change, addition or editing of the author's text are not allowed. Copying individual fragments of articles from the journal is allowed for distribute, remix, adapt, and build upon article, even commercially, as long as they credit that article for the original creation.

Request for the right to reproduce or use any of the materials published in RDLJ should be addressed to the Editor-in-Chief A.M. Elizarov at the following address: amelizarov@gmail.com.

The publishers of RDLJ is not responsible for the view, set out in the published opinion articles.

We suggest the authors of articles downloaded from this page, sign it and send it to the journal publisher's address by e-mail scan copyright agreements on the transfer of non-exclusive rights to use the work.