摘要
随着复杂网络理论的发展以及实际网络数据规模的越来越大,传统的处理方法已经无法满足网络数据的分析管理需求,为了帮助用户理解网络结构并从中挖掘隐含信息,网络可视化技术得到了极大的发展。本文提出了一种基于层次化社团结构的网络可视化方法。此方法首先采用Blondel快速社团算法将网络划分为多层社团结构,然后再在社团内部采用力导引算法和环状布局双重布局,并通过对阈值的设置实现两种布局方法的自由切换。
本文的所做的主要贡献如下:
1.提出了一种基于层次化结构的网络可视化方法,该方法首先使用一种基于模块度指标优化的社团划分算法将网络分成层次化、社团化的结构,然后再分别对每个层次每个社团进行布局,最终得到整个网络的布局;
2.对于社团内部的布局,本文采用了力导引布局和环形布局相结合的方式。为此,我们对传统FR算法做了一系列的改变,包括参数、显示区域、力作用范围等,使之更加适合在社团层面对图的处理;同时,我们引入了社团间连边密度的概念,通过对一个与连边密度相关的阈值的控制,我们能在局部范围内进行环状布局,从而实现了两种布局方法间的切换。
3.本文列举了当前主要的可视化通用软件工具,并通过对三个不同规模、不同特性的实际网络数据的处理,与本文所提出的方法进行了对比。
With the development of the complex network theory and the growth of the scale of the practical data, traditional methods can not satisfy the needs to analyze and manage the network data. To help users understand the network structure and extract the implicit information, network visualization technologies have been developing rapidly. This thesis proposes a network visualization method based on hierarchical community structure. We use the Blondel fast community method to divide network into multi‐level communities, then apply the force directed algorithm and the circle layout method to visualize the network in each community. Moreover, we introduce a threshold value to transit between these two layout methods. The main contributions of the thesis are summarized as follows:
1. The thesis proposes a new visualization method based on hierarchical community structure, in which we first use the community algorithm based on modularity optimization to divide the network into hierarchical communities, then layout each community on all levels until we get the entire layout of the network;
2. Within each community, we use both the force directed algorithm and the circle layout method. In addition, we modify the traditional FR algorithm through changing parameters, display areas, the effect scope of force and so on, to improve the force directed algorithm to be more suitable for dealing with the community structure; Meanwhile, we introduce the concept of edge density between communities which enables implementing circle layout on the local scale and transiting between the two layout methods through controlling an edge density related threshold value.
3. The thesis enumerates some of the most popular general visualization software, and compares the result by running our method with theirs on 3 different networks.
引文
[1] Knuth D. Computer drawn flowcharts [J]. Communications of ACM, 1963, 6(9): 555-563.
[2] Tutte W. How to draw a graph [C]. Proceedings London Mathematical Society, 1963, 13(3): 743-768.
[3] Eades P. A heuristic for graph drawing [J]. Congressus Numerantum, 1984, 42: 149-160.
[4]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M]. 2006,北京:清华大学出版社.
[5] Lyric D, Jonas K, Stefan N, Peter G. Predicting movie prices through dynamic social network analysis [J]. Procedia Social and Behavioral Sciences, 2010, 2: 6423-6433.
[6] Heer J, Boyd D. Vizster: Visualizing online social networks [C]. Proceedings of InfoVis. 2005, 33-40.
[7] Diaz J, Petit J, Sernam. A survey of graph layout problems [J]. ACM Computing Surveys, 2002, 34(3): 313-356.
[8] Battista G, Eades P, Tamassia R, Tollis I. Graph drawing: Algorithms for the visualization of graphs [M]. 1998, Prentice-Hall, Englewood Cliffs.
[1] Battista G, Eades P, Tamassia R, Tollis I. Algorithms for drawing graphs: an annotated bibliography [J], Comput. Geom. Theory Appl., 1994, 4: 235-282.
[2] Tutte W. How to draw a graph [C]. Proceedings London Mathematical Society, 1963, 13(3): 743-768.
[3] Eades P. A heuristic for graph drawing [J]. Congressus Numerantum, 1984, 42: 149-160.
[4] Fruchterman T, Reingold E. Graph drawing by force-directed placement [J]. Software - Practice & Experience, 1991, 21(11): 1129–1164.
[5] Kamada T, Kawai S. An algorithm for drawing general undirected graphs [J]. Information Process. Lett., 1989, 31(1): 7-15.
[6] Frick A, Ludwig A, Mehldau H. A fast adaptive layout algorithm for undirected graphs [J]. Lecture Notes in Computer Science, 1995, 894: 388-403.
[7] Bru? I, Frick A. Fast interactive 3-D graph visualization [J]. Lecture Notes in Computer Science, 1996, 1027: 99-110.
[8] Davidson R, Harel D. Drawing graphs nicely using simulated annealing [J]. ACM Transactions on Graphics, 1996, 15(4):301-331.
[9] Cohen J. Drawing graphs to convey proximity: An incremental arrangement method [J]. ACM Transactions on Computer-Human Interaction, 1997, 4(3):197-229.
[10] Hadany R, Harel D. A multi-scale algorithm for drawing graphs nicely [J]. Discrete Applied Mathematics, 2001, 113(1):3-21.
[11] Harel D, Koren Y. A fast multi-scale algorithm for drawing large graphs [J]. Graph Algorithms Appl., 2002, 6(3):179-202.
[12] Harel D, Koren Y. Graph drawing by high-dimensional embedding [J]. LNCS, 2002, 2528: 207-219.
[13] Gajer P, Goodrich M, Kobourov S. A multi-dimensional approach to force-directed layouts of large graphs [J]. LNCS, 2001, 1984: 211-221.
[14] Walshaw C, Multilevel force-directed drawing [J], JGAA, 2003, 7(3): 253-285.
[15] Quigley A, Eades P. FADE: graph drawing, clustering, and visual abstraction [J]. Lecture Notes in Computer Science, 2000, 1984: 197-210.
[16] Josh Barnes and Piet Hut. A hierarchical O(NlogN) force calculation algorithm [J]. Nature, 1986, 324:446-449.
[17] Furnas G. Generalized fisheye views [C]. Proceedings of the SIGCHI conference on Human factors in Computing Systems, 1986, 16-23.
[18] Formella A, Keller J. Generalized fisheye views of graphs [J]. Lecture Notes in Computer Science, 1996, 1027: 242-253.
[19] Watts D J, Strogatz S H. Collective dynamics of small-world networks [J]. Nature, 1998, 393(6684): 440-442.
[20] Newman M E J. The structure and function of complex networks [J]. SIAM Review, 2003, 45: 167-256.
[21] Noack A. An energy model for visual graph clustering [C]. The 11th International Symposium on Graph Drawing, 2003, 2912: 425-436.
[22] Breitkreutz B, Stark C, Tyers M. Osprey: A network visualization system [J]. Genome Biology, 2003, 4(3): R22-0012.6.
[23] Yee K P, Fisher D, Dhamija R, Hearst MA. Animated exploration of dynamic graphs with radial layout [J]. Proc. of the InfoVis, 2001, 43-50.
[24] Battista G, Eades P, Tamassia R, Tollis I. Graph drawing: Algorithms for the visualization of graphs [M]. 1998, Prentice-Hall, Englewood Cliffs.
[25] Eades P. Drawing free trees [J]. Bulletin of the Institute of Combinatorics and Its Applications, 1992, 10-36.
[26] Quan W, Huang ML. Fast convergence layout algorithm for drawing graphs in Marching-Graph [J]. Journal of Software, 2008, 19(8): 1920-1932.
[1]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M]. 2006,北京:清华大学出版社.
[2] Fortunato S, Castellano C. Community structure in graphs [J]. Eprint arXiv, 2007, 0712: 2716.
[3] Newman M E J. Detecting community structure in networks [J]. Eur. Phys. J.B, 2004, 38: 321-330.
[4] Newman M E J, Girvan M. Finding and evaluating community structure in networks [J]. Phys. Rev. E, 2004, 69: 026113.
[5] Brandes U, Delling D, Gaertler M, G?rke R, Hoefer M, Nikolski Z, Wagner D. On modularity NP-completeness and beyond [J]. Technical Report, ITI Wagner, Faculty of Informatics, Universit?t Karlsruhe (TH), 2006.
[6] Scott J. Social Network analysis: A handbook [M]. 2006, London: Sage Publications, 2nd edition.
[7] Girvan M, Newman M E J. Community structure in social and biological networks [C]. Proc. Natl. Acad. Sci., 2001, 99: 7821-7826.
[8] Tyler J, Wilkinson D, Huberman B. Email as spectroscopy: Automated discovery of community structure within organizations [C]. International Conference on Communities and Technologies, 2003: 81-96.
[9] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks [C]. Proc. Natl. Acad. Sci., 2004, 101: 2658-2663.
[10] Newman M E J. Fast algorithm for detecting community structure in networks [J]. Phys. Rev. E, 2004, 69: 066133.
[11] Blondel V, Guillaume J, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks [J]. J. Stat. Mech., 2008, P10008.
[12] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multiscale complexity in networks [J]. Nature, 2010, 446: 761-764.
[13] Fortunato S. Community detection in graphs [J]. Physics Reports, 2010, 486: 75-174.
[1] Huisman M, Van Duijin M A J. Software for social network analysis [M]. In: Carrington P J, Scott J, Wasserman S(eds.), Models and Methods in Social Network Analysis, 2005, Cambridge: Cambridge University Press, 270-316.
[2] Blondel V, Guillaume J, Lambiotte R, Lefebvre E. Fast unfolding ofcommunities in large networks [J]. J. Stat. Mech., 2008, P10008.
[3] Fruchterman T, Reingold E. Graph drawing by force-directed placement [J]. Software - Practice & Experience, 1991, 21(11): 1129–1164.
[4] Fortunato S. Community detection in graphs [J]. Physics Reports, 2010, 486: 75-174.
[5] http://www.cfinder.org
[6] http://flare.prefuse.org
[7] http://gephi.org
[8] http://www.graphviz.org
[9] http://graphexploration.cond.org
[10] http://jung.sourceforge.net
[11] http://nodexl.codeplex.com
[12] http://vlado.fmf.uni-lj.si/pub/networks/pajek
[13] http://prefuse.org
[14] http://www.r-project.org
[15] http://visone.info
[16] http://www.cytoscape.org
[17] http://nwb.cns.iu.edu
[18] https://sci2.cns.iu.edu/user/index.php
[19] http://www.textrend.org
