論文の概要: Effective resistance in metric spaces
- arxiv url: http://arxiv.org/abs/2306.15649v1
- Date: Tue, 27 Jun 2023 17:43:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-28 12:23:10.022344
- Title: Effective resistance in metric spaces
- Title(参考訳): 距離空間における有効抵抗
- Authors: Robi Bhattacharjee, Alexander Cloninger, Yoav Freund, Andreas
Oslandsbotn
- Abstract要約: 有効抵抗(ER)はグラフの構造を問う魅力的な方法である。
サンプルのサイズが無限大になるにつれて、任意の2点間のERが自明な量に収束することを示す。
領域を固定し続けることにより、点数が無限大になるにつれて、領域ベースのERが非自明な極限に収束することを示す。
- 参考スコア(独自算出の注目度): 65.94598202303497
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Effective resistance (ER) is an attractive way to interrogate the structure
of graphs. It is an alternative to computing the eigenvectors of the graph
Laplacian.
One attractive application of ER is to point clouds, i.e. graphs whose
vertices correspond to IID samples from a distribution over a metric space.
Unfortunately, it was shown that the ER between any two points converges to a
trivial quantity that holds no information about the graph's structure as the
size of the sample increases to infinity.
In this study, we show that this trivial solution can be circumvented by
considering a region-based ER between pairs of small regions rather than pairs
of points and by scaling the edge weights appropriately with respect to the
underlying density in each region. By keeping the regions fixed, we show
analytically that the region-based ER converges to a non-trivial limit as the
number of points increases to infinity. Namely the ER on a metric space. We
support our theoretical findings with numerical experiments.
- Abstract(参考訳): 有効抵抗(ER)はグラフの構造を問う魅力的な方法である。
これはグラフラプラシアンの固有ベクトルを計算するに代わるものである。
ERの魅力的な応用の1つは、頂点が計量空間上の分布からのIDサンプルに対応するグラフを点雲に向けることである。
残念なことに、任意の2点間のerは、サンプルのサイズが無限大になるにつれてグラフの構造に関する情報を持たない自明な量に収束する。
本研究では,一対の点ではなく,一対の小さな領域間の領域ベースERを考慮し,各領域の基底密度に対して適切なエッジ重みを拡大することにより,この自明な解を回避することができることを示す。
領域を固定し続けることにより、点数が無限大になるにつれて、領域ベースのERが非自明な極限に収束することを示す。
すなわち、計量空間上の ER である。
我々は数値実験で理論的な結果を支持する。
関連論文リスト
- Shot-noise reduction for lattice Hamiltonians [0.7852714805965528]
格子ハミルトンのエネルギー期待値を量子コンピュータ上で効率的に推定することは深刻な課題である。
拡張性のある代替手段として幾何学的分割を導入する。
サンプリング数の改善が不完全な固有状態の改善にどのように寄与するかを示す。
論文 参考訳(メタデータ) (2024-10-28T17:50:28Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
本稿では,グラフ上の分布と信号の間の新しい距離を提案する。
GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。
グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
論文 参考訳(メタデータ) (2023-06-05T00:01:17Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳(メタデータ) (2023-02-02T08:33:36Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。
ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。
我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
論文 参考訳(メタデータ) (2022-10-15T08:01:08Z) - Bump hunting through density curvature features [0.0]
確率密度の曲率関数に基づく抽象的なバンプ構造を定義する。
本研究では、ハウゼンドルフ距離におけるバンプ境界の整合性を保証するための理論的な結果を示す。
異なる曲率のインスタンスを効果的に組み合わせ、洞察に富んだ可視化を生成すると結論付けている。
論文 参考訳(メタデータ) (2022-07-30T10:00:42Z) - Universality in Anderson localization on random graphs with varying
connectivity [0.0]
W_E$の値を超える非エルゴディック領域があることが示される。
W_C$とは別の$W_E$は存在しないが、完全に発達したエルゴディディディティが$|W-W_C|-1$のように分岐する長さスケールが見つかる。
臨界点におけるこれらの2つのスケールの分離は、真の非エルゴード非局所化領域を可能にする。
論文 参考訳(メタデータ) (2022-05-29T09:47:39Z) - Structure from Voltage [6.212269948361801]
有効抵抗(ER)はグラフの構造を問う魅力的な方法である。
我々は、$n$の頂点が$n2$のグラフにおけるスケーリング抵抗を使用することで、電圧と有効抵抗の有意義な制限が得られることを示す。
また、計量グラフに「基底」ノードを加えることで、選択された点から他のすべての点までのすべての距離を計算する単純で自然な方法が得られることを示す。
論文 参考訳(メタデータ) (2022-02-28T20:06:10Z) - Convergence of Gaussian-smoothed optimal transport distance with
sub-gamma distributions and dependent samples [12.77426855794452]
本稿では,より一般的な設定下でのGOT距離を推定するための収束保証を提供する。
我々の分析における重要なステップは、GOT距離がカーネルの最大誤差距離の族に支配されていることを示すことである。
論文 参考訳(メタデータ) (2021-02-28T04:30:23Z) - The Convergence Indicator: Improved and completely characterized
parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
我々は、粒子が最終的に単一点に収束するか、分岐するかを計算するのに使用できる新しい収束指標を導入する。
この収束指標を用いて、収束群につながるパラメータ領域を完全に特徴づける実際の境界を提供する。
論文 参考訳(メタデータ) (2020-06-06T19:08:05Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。