【正文】 I 畢業(yè)設計論文 復雜網絡圖的可視化技術研究 Research On Visualization Technique For Complex Networks Graph 摘 要 II 可視化技術 已經成為 計算機應用科學的一個重要研究領域， 通過對圖進行可視化的展示，人們不僅能夠對圖的整體結構以及各節(jié)點之間的聯(lián)系獲得直觀清晰的認識，并且通過可視化展示效果的處理以及用戶的交互，能夠對用戶所關心的圖的某一個部分進行有針對性的觀察和分析，從而使用戶能夠獲取更多有價值的信息，對用戶的工作產 生有意義的指導作用。但是隨著需要被處理的網絡圖的規(guī)模的不斷擴大，其內部的聯(lián)系日益復雜，如何對復雜的網絡圖進行快速并且清晰有效的展示成為圖的可視化技術的研究的重點內容。 本文從復雜網絡圖的可視化布局的流程出發(fā)，闡述了課題研究所涉及到的相關基礎知識。論文針對課題所研究的對象和相關常用的概念的符號約定進行了說明；對 FDA、 FR 兩種圖布局算法的理論依據和實現(xiàn)過程進行了描述，分析了各自的優(yōu)勢和不足之處；介紹了 GN、 NF 兩種網絡圖的社區(qū)結構發(fā)現(xiàn)算法，描述了算法的設計思路和實現(xiàn)流程，并指出了其各自的特點和缺陷。 為了能夠 規(guī)避基于模塊度最優(yōu)的社區(qū)發(fā)現(xiàn)算法出現(xiàn)的的分辨率限制問題，論文引入了邊密度的概念?；?GN 算法的邊分裂思路和 NF 算法的節(jié)點凝聚思路，論文提出了一個基于邊密度的社區(qū)結構發(fā)現(xiàn)算法 —— ECAA（ EdgeDensity CastEdge All Algorithm），對復雜網絡圖先依據邊密度先進行邊的分裂，然后再進行節(jié)點的凝聚，未利用模塊度最優(yōu)從而避免了分辨率限制的問題，算法的時間復雜度是 ? ?Ok m? （其中 m 為網絡中的邊數， k 為網絡中節(jié)點的最大節(jié)點度），小于GN 和 NF 算法，從而提高了算法的執(zhí)行效率。 基于 FR 算法的思路，論文引入了改進的 FR 算法 —— NWFR（ Node Weighted FR），通過調整初始化布局以加快算法的收斂速度；重新定義受力模型以適應帶權節(jié)點網絡圖的處理；修改節(jié)點越界的處理方式，使布局結果更加美觀。 利用上述理論的研究成果，論文設計并實現(xiàn)了一個復雜網絡圖可視化系統(tǒng)。系 統(tǒng)定義了通用的操作接口和統(tǒng)一的內部數據格式；在展示交互模塊采用 WPF技術 MVVM 架構，實現(xiàn)了展示界面和業(yè)務邏輯的分離，提高了程序的復用性并 III 提供了豐富的輔助操作以獲得更好的用戶體驗。將層次化網絡圖算法和圖布局算法封裝在兩個模塊中，在每個模塊中利用工廠模式以提供統(tǒng)一的調用接口，并且每個模塊可以集成多個算法，提高了系統(tǒng)的可擴展性和可維護性。 關鍵詞： 復雜網絡，社區(qū)結構，分辨率限制，邊密度，自動探測，力導引，數據可視化 IV ABSTRACT Visualization technology has bee an important research field of the putational applied science. Through the visual display of the graph, People can not only obtain a visualized and clear understanding about the whole structure and the relationship between each node, but also get targeted observation and analysis about the part of the graph that users care about by processing the effect of the visual display and users’ interaction which enables users to get more valuable information and significant guidance. But with the rapid development of information technology, the scale of the graph which needs to be processing is unceasingly expanding, while the internal relation being increasingly plex. How to make a clear and effective display of a plicated work diagram has bee the key content of the research of the graph’ s visualization technology. Starting from the process of the visual layout of plex work diagram， the paper gives a presentation of the relevant basic knowledge of the project research. It gives an illustration of the object and the agreed symbols。 gives an introduction of the theoretical basis and implementation process of two map layout algorithms FDA, FR, analyzing their advantages and disadvantages respectively。 gives an introduction of two munity structure discovery s GN, NF, describes the design ideas and implementation process of algorithms, and points out their characteristics and defects respectively. To avoid the problem of resolution limit of the munity discovery algorithm based on the maximization of the value of Q, the paper introduces the concept of the density of edges. Based on the thought of edge splitting of GN and the thought of node aggregating of NF ,a munity structure discovery algorithm ECAA（ Edge Density Cast Edge All Algorithm） based on the density of edges has been put forwarded. To V plex work diagrams, the algorithm first splits the edges according to the density of edge, and then aggregates the nodes, not using the maximization of the value of Q so as to avoid the problem of resolution limit. The time plexity of the algorithm is O () (m is the number of edge in the work, k is the largest degree of node in the work) which is less than that of GN and NF , so as to improve the efficiency of the algorithm. Based on the thought of FR algorithm, the improved FR algorithmNWFR （ Node Weighted FR） has been introduced. It accelerates the speed of convergence of the algorithm by adjusting the initial layout。 redefines the force model so as to adjust the process of weighted node work graph。 modifies the treatment of transgression at the same time to make layout more artistic. Making use of the research results of the theories above, a visualization system of a plicated work graph has been designed and implemented. The system defines the general operational interface and unified format of internal data. Technology of WPF and structure of MVVM are used in the display of interactive module, which realizes the separation of the display interface and business logic, improving the reusability of the program and providing a variety of auxiliary operation to get a better user experience. To package the hierarchical work diagram and the visualization graph algorithms in two modules, and to use factory model in each module to provide unified call interface. Each module can integrate several algorithms. All of them improve the scalability and maintainability of the system. Keywords: Complex works, Community structure, Resolution limit, Edge density, Automatic detect, ForceDirected, Data visualization VI 目 錄 摘 要 ............................................................................................................................ I ABSTRACT ..................................................................................................................... IV 目 錄 ........................................................................................................................... VI 第一章 緒論 ...................................................................................................................... 1 課題研究背景及意義 ............................................................................................. 1 課題研究現(xiàn)狀 ....................................................................................................... 2 網絡圖的布局算法 ...................................................................................... 2 社區(qū)結構發(fā)現(xiàn)算法 ...................................................................................... 3