請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9992
標題: | 在大型網路圖上計算完全子圖之最遠距離 Computing the Maximum Clique Distance on a Large-Scale Network |
作者: | Sheng-Yao Tseng 曾聖耀 |
指導教授: | 趙坤茂 |
關鍵字: | 圖形演算法,完全子圖,全點最短路徑,矩陣相乘,廣度優先搜尋, graph algorithm,clique,all-pairs shortest paths,matrix multiplication,breadth-first search, |
出版年 : | 2011 |
學位: | 碩士 |
摘要: | 我們研究完全子圖之最遠距離(clique diameter)問題。給定一個無向、無權重圖,並同時給定一個集合,集合包含圖上所有給定的完全子圖,該問題問其中任兩組完全子圖間之最遠距離為何?由於完全子圖可以代表一個理想的社群,其中每一成員均關聯於其它成員,本問題即是詢問圖上各社群之距離,以及距離最遠的一組社群。假設圖上有n個點與m個邊,同時給定r個完全子圖,我們設計一個O(r(n+m))時間且最多誤差為1的近似演算法,並提供一個轉換方式,讓我們得以運用全點最短路徑演算法來解決我們的研究問題。 We study the clique diameter problem. Given an undirected, unweighted graph containing a set of cliques, we are interested in finding the maximum distance among all pairs of cliques. In the context of social network analysis, a clique represents an ideal community, a clique distance represents the sparsity between the two communities, and a clique diameter indicates the farthest distance among the social network. Let n denote the number of nodes, m denote the number of edges and r denote the number of given cliques. We provide an O(r(n + m)) time algorithm to compute approximate clique distances with additive error of one. Another contribution is a reduction which transforms any instance of the clique distance problem into an instance of the all-pairs shortest paths problem. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9992 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-100-1.pdf | 2.09 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。