文献

J-GLOBAL ID：201802250120795690   整理番号：18A0162643

非常に大きなグラフにおける推定三角形数のエッジベースくさびサンプリング【Powered by NICT】

Edge-Based Wedge Sampling to Estimate Triangle Counts in Very Large Graphs

著者 (2件)： Turkoglu Duru ,  Turk Ata
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： ICDM  ページ： 455-464  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： グラフにおける三角形の数はグラフはモデリングであることをネットワークの重要な特徴の多くを推定するために有用である。しかし,この数の正確な値を見出す計算的に高価である。数エッジのランダムサンプリング,またはくさび(隣接エッジ対)に基づく近似アルゴリズムがこの値を推定するための提案されている。べき乗則次数分布をもつ大規模疎グラフのための,ランダムエッジでのサンプリングは,正確な推定のための十分な情報を提供する前に多数のエッジがのサンプリングを必要とすることを論じ,既存のくさびサンプリング法は,偏ったサンプリング,少ない正確な推定をもたらすをもたらした。本論文では,両手法の欠点を解決するエッジとくさびサンプリング間のハイブリッドアルゴリズムを提案した。均一エッジサンプリングから開始し,次に各選択されたエッジを拡張全三角形数を推定するためのより多くの情報であることをくさびを形成した。するコア推定は第1段階で各端はに関与する三角形の数である。アプローチにより,非常に小サンプリング比の正確な近似を提供し,95%信頼度で推定を提供しながら,試料サイズの8倍までを最新技術より優れていた。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 無作為抽出 ,  *グラフ ,  信頼度 ,  モデリング ,  ネットワーク
準シソーラス用語： ハイブリッドアルゴリズム ,  次数分布 ,  べき乗則 ,  近似アルゴリズム , 【Automatic Indexing@JST】

分類 (3件)： 計算機網  (JC03000K) ,  数値計算  (JE02000J) ,  電話・データ通信・交換一般  (ND11010T)

タイトルに関連する用語 (6件)： グラフ ,  推定 ,  三角形 ,  エッジ ,  くさび ,  サンプリング