結合基於中心性之平面圖形繪製法與以力為導向法呈現小世界圖形及應用於半導體晶圓製造之研究

Abstract

分析大型且複雜的網路圖形是現今重要的議題，小世界圖形即是一類特殊的複雜網路圖，過去應用於社群網路、社會學、計算機科學、商業智能、組織研究及生物學等領域，主要用來探索和提取有用的資訊。傳統的圖形演算並無法有效辨識其結構，使得圖形難以辨別和分析。本研究提供一個視覺化流程來解決這個問題，當中採用了中心性來決定節點間的鏈結，之後使用平面圖繪製方法產生一個沒有交叉鏈結的子圖，隨後對此子圖使用點與邊斥力演算法產生更利於視覺化之圖形，最後補回剩餘鏈結保持原圖形之完整。在實驗結果及圖形分析表明，與先前的研究相比，本研究所提之方法能夠有效的區分群集，並透過這些群集的交互關係，能更深入的了解到網路圖中個體與群集之間的關係。此外，此視覺化流程亦可應用於半導體晶圓製造產業上，並且從視覺上獲得更多有用的資訊利於分析。

Analysis of large and complex network graphs has been an important issue. Small-world network is a special type of those complex network graphs. The structure of this type of graphs cannot be effectively recognized by conventional graph drawing algorithms, such that it is difficult to identify and analyze the network. To solve this problem, this paper proposes a visualization approach, which utilizes centrality to remove some links between nodes, then uses a plane graph drawing method to lay out the reduced subgraph without any edge crossing, then applies a force-directed graph drawing method based on node-edge repulsion to improve the layout, finally adds back the remaining links. On experimental analysis, our results can not only analyze the same information with previous methods, but successfully gain more useful information. It lets us have a better understanding for the relationship between nodes and search out some messages that were never found before. Application of this approach to semiconductor wafer fabrication example is demonstrated.