|
|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/8809
|
| タイトル: | A Linear-Space Algorithm for Distance Preserving Graph Embedding |
| 著者: | Asano, Tetsuo
Bose, Prosenjit
Carmi, Paz
Maheshwari, Anil
Shu, Chang
Smid, Michiel
Wuhrer, Stefanie |
| キーワード: | Graph embedding
Multi-dimensional scaling
Clustering |
| 発行日: | 2009-05 |
| 出版者: | Elsevier |
| 誌名: | Computational Geometry : Theory and Applications |
| 巻: | 42 |
| 号: | 4 |
| 開始ページ: | 289 |
| 終了ページ: | 304 |
| DOI: | 10.1016/j.comgeo.2008.06.004 |
| 抄録: | The distance preserving graph embedding problem is to embed the vertices of a given weighted graph onto points in d-dimensional Euclidean space for a constant d such that for each edge the distance between their corresponding endpoints is as close to the weight of the edge as possible. If the given graph is complete, that is, if the weights are given as a full matrix, then multi-dimensional scaling [13] can minimize the sum of squared embedding errors in quadratic time. A serious disadvantage of this approach is its quadratic space requirement. In this paper we develop a linear-space algorithm for this problem for the case when the weight of any edge can be computed in constant time. A key idea is to partition a set of n objects into O√<n> disjoint subsets (clusters) of size O√<n> such that the minimum inter cluster distance is maximized among all possible such partitions. Experimental results are included comparing the performance of the newly developed approach to the performance of the well-established least-squares multi-dimensional scaling approach [13] using three different applications. Although least-squares multi-dimensional scaling gave slightly more accurate results than our newly developed approach, least-squares multi-dimensional scaling ran out of memory for data sets larger than 15000 vertices. |
| Rights: | NOTICE: This is the author’s version of a work accepted for publication by Elsevier. Changes resulting from the publishing process, including peer review, editing, corrections, structural formatting and other quality control mechanisms, may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid and Stefanie Wuhrer, Computational Geometry : Theory and Applications, 42(4), 2009, 289-304, http://dx.doi.org/10.1016/j.comgeo.2008.06.004 |
| URI: | http://hdl.handle.net/10119/8809 |
| 資料タイプ: | author |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| C12260.pdf | | 1185Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
