maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1025Research ArticleОригинальные статьиArticlesВизуализация динамических графов для анализа сложных сетейThe Analysis of Complex Networks with Dynamic Graph VisualizationПупыревС. Н.PupyrevS. N.pupyrev@gmail.comТихоновА. В.TikhonovA. V.altsoph@gmail.comУральский государственный университетRussian FederationООО CorelogicRussian Federation201020032010171117135Copyright © Пупырев С.Н., Тихонов А.В., 20102010Пупырев С.Н., Тихонов А.В.Pupyrev S.N., Tikhonov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1025

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

The work describes a technique for dynamic graph visualization that helps us to analyze complex networks. Our method builds layouts for a sequence of graphs, while preserving the mental map. We show how to modify force-directed algorithms for the dynamic graphs. The proposed method is applied for visualization of several social networks. The experiments demonstrate the effectiveness of dynamic graph drawing for analyzing real-world data and the evolution of social relationships changing over time.

519.6рисование графовдинамический графвизуализацияанализ сложных сетейgraph drawingdynamic graphvisualizationcomplex network analysisReferencesAlbert R., Barabasi A.-L. Statistical mechanics of complex networks // Reviews of Modern Physics. 2002. 74. P. 47-97.Albert R., Barabasi A.-L. Statistical mechanics of complex networks // Reviews of Modern Physics. 2002. 74. P. 47-97.Boitmanis K., Brandes U., Pich C. Visualizing internet evolution on the autonomous systems level // Proc. 15th Intl. Symp. Graph Drawing. 2007. P. 365-376.Boitmanis K., Brandes U., Pich C. Visualizing internet evolution on the autonomous systems level // Proc. 15th Intl. Symp. Graph Drawing. 2007. P. 365-376.Branke J. Dynamic graph drawing // Drawing Graphs, Springer Lecture Notes In Computer Science. 2001. P. 228-246.Branke J. Dynamic graph drawing // Drawing Graphs, Springer Lecture Notes In Computer Science. 2001. P. 228-246.Chen L., Buja A. Local multidimensional scaling for nonlinear dimension reduction, graph layout and proximity analysis // Journal of the American Statistical Association. 2009. 104(485). P. 209-219.Chen L., Buja A. Local multidimensional scaling for nonlinear dimension reduction, graph layout and proximity analysis // Journal of the American Statistical Association. 2009. 104(485). P. 209-219.Diehl S., Gorg C. Graphs, they are changing // Proc. 10th Int. Symp. on Graph Drawing. 2002. P. 23-30.Diehl S., Gorg C. Graphs, they are changing // Proc. 10th Int. Symp. on Graph Drawing. 2002. P. 23-30.Dwyer T. Two and a Half Dimensional Visualisation of Relational Networks. PhD thesis, The University of Sydney, 2005.Dwyer T. Two and a Half Dimensional Visualisation of Relational Networks. PhD thesis, The University of Sydney, 2005.Eades P. A heuristic for graph drawing // Congressus Numerantium. 1984. 42. P. 149-160.Eades P. A heuristic for graph drawing // Congressus Numerantium. 1984. 42. P. 149-160.Erten C., Harding P. J., Kobourov S. G., Wampler K., Yee G. Exploring the computing literature using temporal graph visualization // Proc. of SPIE. 2004. Vol. 5295. P. 45-56.Erten C., Harding P. J., Kobourov S. G., Wampler K., Yee G. Exploring the computing literature using temporal graph visualization // Proc. of SPIE. 2004. Vol. 5295. P. 45-56.Fruchterman T., Reingold E. Graph drawing by force-directed placement // Softw. -Pract. Exp. 1991. 21(11). P. 1129-1164.Fruchterman T., Reingold E. Graph drawing by force-directed placement // Softw. -Pract. Exp. 1991. 21(11). P. 1129-1164.Fu X., Hong S.-H., Nikolov N. S., Shen X., Wu Y., Xu K. Visualization and analysis of email networks // Proc. of Asia-Pacific Symp. on Visualisation. 2007. P. 1-8.Fu X., Hong S.-H., Nikolov N. S., Shen X., Wu Y., Xu K. Visualization and analysis of email networks // Proc. of Asia-Pacific Symp. on Visualisation. 2007. P. 1-8.Gansner E. R., Koren Y., North S. C. Graph drawing by stress majorization // Proc. 12th Int. Symposium on Graph Drawing. 2004. P. 239-250.Gansner E. R., Koren Y., North S. C. Graph drawing by stress majorization // Proc. 12th Int. Symposium on Graph Drawing. 2004. P. 239-250.Hanstein H., Groh G. Interactive visualization of dynamic social networks // GI Jahrestagung (2). 2008. P. 929-936.Hanstein H., Groh G. Interactive visualization of dynamic social networks // GI Jahrestagung (2). 2008. P. 929-936.Harel D., Koren Y. A fast multi-scale method for drawing large graphs // Journal of Graph Algorithms and Applications. 2002. 6(3). P. 282-285.Harel D., Koren Y. A fast multi-scale method for drawing large graphs // Journal of Graph Algorithms and Applications. 2002. 6(3). P. 282-285.Kamada T., Kawai S. An algorithm for drawing general undirected graphs // Inform. Process. Lett. 1989. 31. P. 7-15.Kamada T., Kawai S. An algorithm for drawing general undirected graphs // Inform. Process. Lett. 1989. 31. P. 7-15.Klimt B., Yang Y. Introducing the enron corpus // Proc. of First Conf. on Email and Anti-Spam. 2004.Klimt B., Yang Y. Introducing the enron corpus // Proc. of First Conf. on Email and Anti-Spam. 2004.Kruskal J. B., Seery J. B. Designing network diagrams // Proc. ofthe First General Conference on Social Graphics.1980. P. 22-50.Kruskal J. B., Seery J. B. Designing network diagrams // Proc. ofthe First General Conference on Social Graphics.1980. P. 22-50.Misue K., Eades P., Lai W., Sugiyama K. Layout adjustment and the mental map // Journal ofVisual Languages and Computing. 1995. 6(2). P. 183-210.Misue K., Eades P., Lai W., Sugiyama K. Layout adjustment and the mental map // Journal ofVisual Languages and Computing. 1995. 6(2). P. 183-210.Noack A. An energy model for visual graph clustering // Proc. 11th Int. Symp. on Graph Drawing. 2003. P. 425-436.Noack A. An energy model for visual graph clustering // Proc. 11th Int. Symp. on Graph Drawing. 2003. P. 425-436.Pich C. Applications of Multidimensional Scaling to Graph Drawing. PhD thesis, Universitat Konstanz, 2009.Pich C. Applications of Multidimensional Scaling to Graph Drawing. PhD thesis, Universitat Konstanz, 2009.Purchase H. Which aesthetic has the greatest effect on human understanding? // Proc. 5th Int. Symp. on Graph Drawing. 1998. P. 248-261.Purchase H. Which aesthetic has the greatest effect on human understanding? // Proc. 5th Int. Symp. on Graph Drawing. 1998. P. 248-261.Tutte W. T. How to draw a graph // Proc. London Math. Society. 1963. 13(52). P. 743-768.Tutte W. T. How to draw a graph // Proc. London Math. Society. 1963. 13(52). P. 743-768.Система визуализации графов GraphVis. http://graphvis.googlecode.com.Система визуализации графов GraphVis. http://graphvis.googlecode.com.

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