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

Abstract

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