(34.239.176.198) 您好!臺灣時間:2021/04/23 19:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:范耀中
研究生(外文):Yao-Chung Fan
論文名稱:真實世界圖形之表示
論文名稱(外文):Representing Real World Graphs
指導教授:呂芳懌呂芳懌引用關係
指導教授(外文):Fang-Yie Leu, Ph. D.
學位類別:碩士
校院名稱:東海大學
系所名稱:資訊工程與科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:49
中文關鍵詞:圖形表示式非常大圖形小世界現象資料壓縮圖形理論
外文關鍵詞:Graph RepresentationVery Large GraphSmall World PhenomenaData Compaction and CompressionGraph Theory
相關次數:
  • 被引用被引用:0
  • 點閱點閱:155
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:0
圖形在計算機領域有極廣泛的應用。傳統的圖形多為小型的應用與理論,然而隨著網際網路的成熟與線上系統的應用,擁有成千上萬節點的大圖形,諸如,全球資訊網路圖形(Web Graph)與人際關係圖形(Social Network)等圖,逐漸的被應用在計算機科學的領域。舉搜尋引擎為例,google利用全球資訊網路圖形的連結資訊,來達成較有效(effective)的資訊檢索。近年來,亦有若干文獻針對許多本質相異的大圖形的性質與應用提出討論與應用。然而,這方面的研究最基本的問題在於該如何將如此巨大的圖形表示於記憶體中。
這篇文章主要利用圖形中節點的重新排列與小世界現象(Small World Phenomena),提出一資料結構,名為SWL(Small World Linkage),來解決大圖形資料量過大的問題。在無任何資料的損失(lossless)下,使用SWL可使圖形的資料量縮減為原先之一半,然而有別於傳統的資料壓縮,SWL的使用並無增加時間複雜度上額外的負擔。再者,SWL與先前相關的研究成果並無衝突,意即SWL可與先前所提出的壓縮方法相互加強,以達較佳的壓縮率。
文中,我們首先利用數學模型證明SWL的可行性,並對時間與空間複雜度作一分析討論。接著,我們將SWL實作於三個知名的真實世界圖形,分別為蛋白質新陳代謝網路,食物鏈圖形,與全球資訊網圖形,並與標準的鄰接串列進行比較,實驗的結果佐證SWL確如模型所預測般可行。文末,我們也提出SWL在執行效率上的最佳化方法與壓縮率的提升,並提供實驗佐證之。
Representing a small graph is simple. Representing a graph with massive amount of vertices and edges is an engineering challenge. In this article we propose a method that can compress a massive digraph (directed graph) into about half size of the original representation represented by using adjacency list. This method also provides a fast decompression algorithm that works as quickly as adjacency list does. Particularly, our approach is not mutually exclusive with other compression techniques. We can exploit a higher compression ratio by integrating some other compression techniques, for example, Huffman coding and Delta coding, with our approach.
In this paper we deal with the problem of finding a compact representation of a graph from which the vertices adjacent to a vertex given can be easily determined. A standard adjacency list approach consisting of two lists (one for incoming list and the other for outgoing) for each vertex is redundant since only incoming lists or outgoing lists are sufficient to reconstruct the graph. However, to eliminate one of the lists (incoming and outgoing) will dramatically increase the complexity of determining the neighborhoods of a specified vertex. Exactly as this tradeoff problem, our work presents a compromise approach. First, we partition the graph into subgraphs such that most of the edges in the graph are involved within those subgraphs. Only few edges are cut. Second, the edges are classified into distant edges, those that are cut, and short edges, those existing in a subgraph. After that, the short edges in outgoing lists are eliminated and the distant edges in outgoing lists are retained. That is, the outgoing lists are now replaced by distant lists. Thus, the size of this representation will approach to half size of adjacency-list representation.
For determining what vertices are adjacent to a given vertex v, we can directly read the incoming list and distant list of v. Besides, the out-going list of v can be reconstructed by scanning incoming lists of the subgraph containing v. Based on this approach, we can acquire the entire linking information of v. Furthermore, via probabilistic analysis we can expect that the performance of finding all vertices adjacent to a given vertex of the proposed representation will work as quickly as adjacency-list one does.
ABSTRACT 5
摘要 7
1. INTRODUCTION 8
1.1 BACKGROUND 8
1.2 INTRODUCTION OF THE PROBLEM 9
2. AN OVERVIEW OF THE SMALL WORLD PHENOMENA 11
2.1 PHENOMENA IN REAL WORLD GRAPHS 11
2.2 BACKGROUND ON THE THEORY OF GRAPHS 12
2.2.1 Random Graph Theory 13
2.2.2 Small World Model 13
2.2.3 Scale Free Model 15
3. COMPRESSION PROCESS 16
3.1 GRAPH PARTITION 16
3.1.1 Minimum Cut Algorithm 16
3.1.2 Judgment Factor 20
3.1.3 Graph Partition Algorithm 20
3.1.4 Parallel Cuts 22
3.1.5 Preprocess of MMCA 24
3.2 INDEX 25
3.2.1 Partition and Index Parse 25
4. DATA STRUCTURES 28
4.1 RECONSTRUCTION PROPERTIES 29
4.2 SMALL WORLD LINKAGE 30
4.3 OPERATOR IMPLEMENTATION 31
5. MATHEMATICAL EVALUATION 33
5.1 PERFORMANCE EVALUATION 33
5.2 COMPRESSING RATIO EVALUATION 36
6. THE MEASUREMENT AND RESULTS 37
6.1 EMPIRICAL RESULTS 37
6.2 MEMORY ALLOCATION 39
6.3 DISCUSSION 40
6.4 PERFORMANCE IMPROVEMENT 41
6.5 COMPRESSION RATIO IMPROVEMENT 43
7. CONCLUSION AND FUTURE WORKS 45
8. REFERENCES 47
[1] Shudong J., A. Bestavros, “Small world Internet Topologies,” Technical Report 2002
[2] Adamic L., “The Small World Web. Xerox Palo Research Center” In Lecture Notes in Computer Science, 1696, Proceedings of the European Digital Libraries (ECDL), Page(s):443-454, 1999.
[3] Bharat K., A. Borde, M.Henzinger, P. Kumar, and S. Venkatasubramanian,
“The Connectivity Server: fast access to linkage information on the Web,” In proceedings of the 7th world wide web Conference, 1998.
[4] James A., L. Adam and J.R Buchsbaum “Westbrook: A Functional Approach to External Graph Algorithm,” 6th European Symposium on algorithms, 1998.
[5] Torsten S. and J. Yuan, “Compressing the Graph Structure of the Web,” Data Compression Conference, 2001. Proceedings. DCC 2001. , Page(s): 213 -222, 2001.
[6] Randall, K.H., R. Stata. R.G Wickremesinghe, and J.L. Wiener, “The Link Database: fast access to graphs of the Web,” Data Compression Conference, 2002. Proceedings. DCC 2002,Page(s): 122 -131, 2002
[7] Watts D.J., S.H. Strogatz, “Collective dynamics of small world networks,” Nature 393, Page(s):440-443, 1998.
[8] Barabasi A.L, and R. Albert, “Emergence of scaling in random networks,” Science 286 Page(s):509-512, 1999.
[9] Abello, W., F. Chung and L. Lu., “A random graph model for massive graphs,” Proceedings of the 32d Annual ACM Symposium on the Theory of Computing 1999
[10] Abello, J., P. M. Pardalos and M. G. C. Resende, “On maximum clique problems in very large graphs,” 1999.
[11] David R. K and C. Stein., “An Algorithm for Minimum Cuts,” Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, Page(s):757-765. 1993.
[12] Barrar A. and M. Weigt, “On the properties of small world network models,” The European Physical Journal B(13), Page(s):547-560, 2000.
[13]Adle.M. M. Mitzenmacher, “Towards compressing Web graphs” Data Compression Conference, 2001, Proceedings. DCC 2001, Page(s): 203 -212, 2001.
[14] Reka A and B. Barabasi, “Statistical Mechanics of Complex Networks,” Reviews of Modern Physics, Volume 74, 2002.
[15] Witten I.H, A. Moffat, and T.C. Bell, “Managing Gigabytes: Compressing and Index Documents and Image,” Morgan Kaufmann, second edition, 1999.
[16] Sayood K. “Introduction to Data Compression,” Morgan Kaufmann, second edition, 2000.
[17] Bang-Jensen J, and G.Gutin “Digraphs: Theory, Algorithms and Applications,” Springer Monographs in Mathematics, 2000.
[18] Leu F. Y. and Y. C. Fan, “Compressing a Directed Massive Graph using Small World Model,” Data compression Conference, 2004, Proceedings. DCC 2004, Page(s):550, 2004.
[19] Leu F. Y. and Y. C. Fan, “Dealing with the structure of Real World Graph,” International Conference on Computer Science and its applications, Proceeding ICCSA 2004, Page(s): 40-49, 2004.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔