在大型網路圖上計算完全子圖之最遠距離

Computing the Maximum Clique Distance on a Large-Scale Network

曾聖耀(Sheng-Yao Tseng)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.00070

摘要

我們研究完全子圖之最遠距離（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.

並列關鍵字

graph algorithm ； clique ； all-pairs shortest paths ； matrix multiplication ； breadth-first search

參考文獻

[19] D.R. Karger, D. Koller, and S.J. Phillips. Finding the hidden path: time bounds

[8] Pierluigi Crescenzi, Roberto Grossi, Claudio Imbrenda, Leonardo Lanzi, and

sublinear i/o. In Rolf H. Möhring and Rajeev Raman, editors, ESA, volume

[22] Cl emence Magnien, Matthieu Latapy, and Michel Habib. Fast computation of

estimation of diameter and shortest paths (without matrix multiplication).