論文の概要: Average Distance Approximation for Static Large Graphs

• arxiv url: http://arxiv.org/abs/2608.16916v1
• Date: Sun, 26 Jul 2026 14:23:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-23 14:54:39.970391
• Title: Average Distance Approximation for Static Large Graphs
• Title（参考訳）: 静的大グラフに対する平均距離近似
• Abstract要約: 大規模ネットワークにおける平均距離の計算は、計算集約的で、制限された主メモリによって制限される。 ランダムウォークは小さなサンプルサイズでは信頼性が低く、より大きな標本では計算コストがかかることが判明した。 EWアルゴリズムは、平均距離推定のための実用的でスケーラブルなソリューションを提供する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Calculating average distances in large-scale networks is computationally intensive and constrained by limited main memory, posing a significant challenge in graph analytics. This study explores and evaluates two primary approaches for estimating average distances: a graph sampling-based method (Random Walk) and landmark-based methods, including the Size Estimation Framework (SEF) and the Eppstein-Wang (EW) algorithm. Random Walk was found to be unreliable for small sample sizes and computationally expensive for larger ones, requiring at least 15% of nodes for accuracy. Landmark-based approaches, leveraging probabilistic data structures like HyperLogLog for memory-efficient neighbor exploration, demonstrated superior performance. Among these, the SEF algorithm offers better memory efficiency, while the EW algorithm achieves higher accuracy with lower computation time. Experiments on static, undirected, and unweighted graphs (both unipartite and bipartite) revealed that the EW algorithm produced results with an error margin as low as 0.02%. Additionally, a subset of 100 randomly selected nodes was sufficient for accurate estimations in most large graphs. The findings indicate that the EW algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.
• Abstract（参考訳）: 大規模ネットワークにおける平均距離の計算は、計算集約的で、メインメモリの制限により制限されており、グラフ解析において大きな課題となっている。 本研究では,平均距離を推定するための主要なアプローチとして,グラフサンプリングに基づく手法(ランドマークウォーク)と,サイズ推定フレームワーク(SEF)とEppstein-Wang(EW)アルゴリズムを含むランドマークに基づく手法について検討・評価する。 ランダムウォークは小さなサンプルサイズでは信頼性が低く、より大きな標本では計算コストがかかり、正確性のために少なくとも15%のノードを必要とすることが判明した。 ランドマークベースのアプローチは、HyperLogLogのような確率的データ構造を利用して、メモリ効率の良い隣の探索を行い、優れたパフォーマンスを示した。 このうちSEFアルゴリズムはメモリ効率が良く、EWアルゴリズムは計算時間を短縮して高い精度を達成している。 静的、非方向、および非重み付きグラフ(ユニパートイトとバイパートライトの両方)の実験では、EWアルゴリズムがエラーマージンを0.02%まで下げた結果が得られた。 さらに、ランダムに選択された100個のノードのサブセットは、ほとんどの大きなグラフで正確な推定に十分であった。 その結果、EWアルゴリズムは平均距離推定のための実用的でスケーラブルな解を提供し、二部グラフと比較して一部グラフの信頼性が高いことが示唆された。

関連論文リスト

• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  最小内部積グリーディ選択規則に基づく,単純かつ効率的なカラム選択グラフサンプリングアルゴリズムを提案する。 ブロックモデルに基づいてアルゴリズムを解析し,次数分布がノード間で均衡している場合,クラスタサイズに対する比例サンプリングを実現する。
  論文  参考訳（メタデータ） (2026-07-30T02:45:31Z)
• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  粗大化における近隣住民の集団干渉を優先する非利己的原則を提案する。 局所等方性仮定に基づいて、O(dot d)干渉評価をO(d)に還元する高速なNOPE*を導出する。 粗いグラフの学習は、元のグラフに匹敵する性能を示し、LLMベースのグラフ推論よりも優れた性能を示すことができる。
  論文  参考訳（メタデータ） (2026-05-13T05:24:35Z)
• Efficient Algorithms for Computing Random Walk Centrality [19.36361626345712]
  本稿では、2つのスケーラブルなアルゴリズムの基盤となるランダムウォーク中心性の新たな定式化について述べる。 1000万以上のノードを持つ大規模な実世界のネットワークの実験は、提案アルゴリズムの効率性と近似品質を実証している。
  論文  参考訳（メタデータ） (2025-10-23T14:36:38Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  自己組織化マップ(SOM)におけるトポロジカルプロジェクションに基づく半教師付き学習手法を提案する。 提案手法は,まずラベル付きデータ上でSOMを訓練し,最小限のラベル付きデータポイントをキーベストマッチングユニット(BMU)に割り当てる。 提案した最小教師付きモデルが従来の回帰手法を大幅に上回ることを示す。
  論文  参考訳（メタデータ） (2024-01-12T22:51:48Z)
• Learning the hub graphical Lasso model with the structured sparsity via an efficient algorithm [0.9999629695552196]
  ハブグラフィカルモデルを推定する二相アルゴリズムを提案する。 提案アルゴリズムはまず,乗算器の2つの交互方向法(ADMM)を用いてよい初期点を生成し,次に半平滑ニュートン法(SSN)に基づく拡張ラグランジアン法(ALM)を暖房開始する。 合成データと実データの両方に関する包括的な実験は、既存の最先端アルゴリズムよりも明らかに優れていることを示している。
  論文  参考訳（メタデータ） (2023-08-17T08:24:28Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Manifold learning with approximate nearest neighbors [1.8477401359673706]
  多様体学習アルゴリズムでは近距離近傍の近似アルゴリズムを多用し,その埋め込み精度への影響を評価した。 ベンチマークmnistデータセットに基づく徹底的な実証調査により,近似近辺の計算時間が大幅に改善されることが示されている。 本アプリケーションは,提案手法を用いて異常を可視化し,同定し,高次元データ中の基盤構造を明らかにする方法を示す。
  論文  参考訳（メタデータ） (2021-02-22T12:04:23Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Scalable Distributed Approximation of Internal Measures for Clustering Evaluation [5.144809478361603]
  クラスタリング評価のための内部測度はシルエット係数であり、計算には2つの距離計算が必要である。 本稿では,任意の距離に基づいてクラスタリングの評価を行うための厳密な近似を計算した最初のスケーラブルアルゴリズムを提案する。 また,このアルゴリズムは凝集や分離などのクラスタリング品質の他の内部指標の厳密な近似に適応可能であることも証明した。
  論文  参考訳（メタデータ） (2020-03-03T10:28:14Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。