(34.239.176.198) 您好！臺灣時間：2021/04/23 19:48

### 詳目顯示:::

:

• 被引用:0
• 點閱:155
• 評分:
• 下載:19
• 書目收藏:0
 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.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 Efficient and Robust Schemes for Accuracy-Guaranteed Sensor Data Aggregation 2 從小世界與無尺度角度探討全球城市網絡之連結特性-以飛機航線及其機場據點城市為例 3 延伸樹辨識問題之研究 4 大型社交網絡服務網站的小世界現象及其影響因素：以Facebook為例 5 在社群網路服務中找出不活躍的使用者 6 社會網絡中心性對學習成效之影響─以輔大某課程為例 7 圖形在距離標號中之擴張性 8 k元N立方體的迴圈/路徑嵌入問題之研究 9 疊蓋式網路與實體網路不匹配問題之研究 10 圖的k多重支配問題 11 應用於分散式感測網路的可適性預先分配金鑰模型 12 最佳化網路成長模型的理論研究 13 利用拓撲特性分析與演算法設計之網際網路效能改善研究 14 應用結構洞與小世界理論分析供應鏈資訊流通性之研究 15 在超立方體上當壞一點之情況下要建造最長路徑之所能容忍的最大錯邊個數

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室