Использование матриц смежности для визуализации больших графов
https://doi.org/10.26907/1562-5419-2019-22-1-2-36
Аннотация
Экспоненциальный рост размеров таких графов, как социальные сети, интернет-графы и др., требует новых подходов к их визуализации. Наряду с представлениями типа «диаграммы связей вершин» все чаще используются визуализации матриц смежностей, а также разнообразные комбинации этих представлений. В данном обзоре рассмотрены новые подходы к визуализации графов большого объема при помощи матриц смежностей и приведены примеры приложений, где эти подходы применяются. Описаны различные типы шаблонов, возникающие при упорядочении матриц смежностей, соответствующих современным сетям, и алгоритмы, позволяющие выделять эти шаблоны. В частности, продемонстрировано, как использование методов упорядочения матриц совместно с алгоритмами поиска таких шаблонов, как звезды, ложные звезды, цепи, почти клики, полные клики, двудольные ядра и почти двудольные ядра, позволяют создавать понятные визуализации графов, имеющих миллионы вершин и ребер. Также приведены примеры гибридных визуализаций, использующих диаграммы связей вершин для представления неплотных частей графа, а матрицы смежностей – для представления плотных частей и их приложений. Гибридные методы используются для визуализации сетей соавторства, глубоких нейронных сетей, сравнения сетей связности человеческого мозга и др.
Ключевые слова
Об авторе
З. В. Апанович
Институт систем информатики им. А.П. Ершова Сибирского отделения Российской академии наук
Россия
Россия
Список литературы
1. Liiv I. Seriation and matrix reordering methods: An historical overview// Statistical analysis and data mining. 2010. V. 3, No. 2. P. 70–91.
2. Petrie F.W.M. Sequences in prehistoric remains// J. Anthropol. Inst. Great Britain and England. 1899. V. 29, No. 3/4. P. 295–301.
3. Czekanowski J. Zur differentialdiagnose der Neandertalgruppe// Korrespondenzblatt Deutsch Ges Anthropol Ethnol Urgesch XL.1909. V. 6, No. 7. S. 44–47.
4. Forsyth E., Katz L. A matrix approach to the analysis of sociometric data: preliminary report// Sociometry. 1946. V. 9, No. 4. P. 340–347.
5. 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.
6. Díaz J., Petit J., Serna M. A survey of graph layout problems// ACM Comput. Surv. 2002. V. 34, No. 3. P. 313–356.
7. 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.
8. Mueller C., Martin B., Lumsdaine A. Interpreting large visual similarity matrices// 2007 6th International Asia-Pacific Symposium on Visualization, 2007. IEEE. P. 149–152.
9. Mueller C., Martin B., Cottam J., Lumsdaine A. Matrix representations of graphs. URL: https://www.slideserve.com/amandla/matrix-res-of-graphs.
10. 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.
11. 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.
12. 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.
13. Blandford D., Blelloch G., Kash I. Compact representations of separable graphs //Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA). 2003. P. 679–688.
14. West D.B. Introduction to Graph Theory, Prentice-Hall, Inc., 1996. P. 436–449.
15. Wei T. Corrplot. Visualization of a correlation matrix // r package version 0.73. ed., 2013. URL: https://github.com/taiyun/corrplot.
16. 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.
17. 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.
18. Siek J.G., Lee L.-Q., Lumsdaine A. The Boost Graph Library: User Guide and Reference Manual// Pearson Education. 2001. P. 352.
19. 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
20. 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.
21. 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.
22. 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.
23. 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.
24. George J.A. Computer implementation of the finite element method// PhD thesis, Stanford University. 1971. P. 1–228.
25. 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.
26. 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.
27. 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
28. Krizhevsky A., Sutskever I., Hinton G.E. Imagenet classification with deep convolutional neural networks// NIPS. 2012. P. 1–9.
29. Abello J. van Ham F. Matrix zoom: A visual interface to semi-external graphs// IEEE InfoVis. 2004. P. 183–190.
30. 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
31. 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.
32. 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.
33. 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.
34. 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.
35. 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
36. 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.
37. Апанович З.В. Методы построения жгутов ребер для улучшения понимаемости информации// Проблемы управления и моделирования в сложных системах труды XV Международной конференции. 2013. С. 439–445.
38. Апанович З.В., Винокуров П.С., Кислицина Т.А. Методы и средства визуализации больших научных порталов//Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2011. Т. 9. № 3. С. 5–14.
39. 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.
40. 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
Рецензия
Для цитирования:
Апанович З.В. Использование матриц смежности для визуализации больших графов . Электронные библиотеки. 2019;22(1):2-36. https://doi.org/10.26907/1562-5419-2019-22-1-2-36
For citation:
Using adjacency matrices for visualization of large graphs . Russian Digital Libraries Journal. 2019;22(1):2-36. (In Russ.) https://doi.org/10.26907/1562-5419-2019-22-1-2-36
Просмотров:
34
Послать статью по эл. почте 