論文の概要: A metric on directed graphs and Markov chains based on hitting
probabilities
- arxiv url: http://arxiv.org/abs/2006.14482v2
- Date: Mon, 18 Jan 2021 16:54:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 03:57:41.497760
- Title: A metric on directed graphs and Markov chains based on hitting
probabilities
- Title（参考訳）: ヒット確率に基づく有向グラフとマルコフ連鎖の計量
- Authors: Zachary M. Boyd, Nicolas Fraiman, Jeremy L. Marzuola, Peter J. Mucha,
Braxton Osting, and Jonathan Weare
- Abstract要約: エルゴード的、有限状態、時間均質なマルコフ連鎖の状態空間に関する計量を導入する。
提案手法は,あるノードから別のノードへのランダムウォーカーの移動に伴う距離空間の近さを仮定して構築した。
特に、私たちのメトリクスは、最も短くて平均的な歩行距離に敏感であり、既存のメトリクスと比較して新しい情報を与えます。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The shortest-path, commute time, and diffusion distances on undirected graphs
have been widely employed in applications such as dimensionality reduction,
link prediction, and trip planning. Increasingly, there is interest in using
asymmetric structure of data derived from Markov chains and directed graphs,
but few metrics are specifically adapted to this task. We introduce a metric on
the state space of any ergodic, finite-state, time-homogeneous Markov chain
and, in particular, on any Markov chain derived from a directed graph. Our
construction is based on hitting probabilities, with nearness in the metric
space related to the transfer of random walkers from one node to another at
stationarity. Notably, our metric is insensitive to shortest and average walk
distances, thus giving new information compared to existing metrics. We use
possible degeneracies in the metric to develop an interesting structural theory
of directed graphs and explore a related quotienting procedure. Our metric can
be computed in $O(n^3)$ time, where $n$ is the number of states, and in
examples we scale up to $n=10,000$ nodes and $\approx 38M$ edges on a desktop
computer. In several examples, we explore the nature of the metric, compare it
to alternative methods, and demonstrate its utility for weak recovery of
community structure in dense graphs, visualization, structure recovering,
dynamics exploration, and multiscale cluster detection.
- Abstract（参考訳）: 非向グラフにおける最短経路、可換時間、拡散距離は、次元減少、リンク予測、トリップ計画といった応用で広く用いられている。
マルコフ連鎖や有向グラフから導出されるデータの非対称構造の利用に関心が高まるが、このタスクに特に適応する指標はほとんどない。
我々は、任意のエルゴード、有限状態、時間同質なマルコフ連鎖の状態空間上の計量、特に有向グラフから導かれる任意のマルコフ連鎖について紹介する。
提案手法は,あるノードから別のノードへのランダムウォーカーの移動に伴う距離空間の近さを仮定して構築した。
特に、私たちの測定基準は、最短距離と平均歩行距離に影響を受けないので、既存の測定基準と比較して新しい情報を与えます。
我々は、計量における退化の可能性を利用して、有向グラフの興味深い構造理論を開発し、関連する商化手順を探求する。
我々のメトリックは、$O(n^3)$ timeで計算でき、$n$は状態の数であり、例えば、デスクトップコンピュータ上の$n=10,000$ノードと$\approx 38M$エッジまでスケールする。
いくつかの例では、メートル法の性質を調べ、別の方法と比較し、密度グラフにおけるコミュニティ構造の弱い回復、可視化、構造回復、ダイナミクス探索、マルチスケールクラスタ検出に有用性を示す。
関連論文リスト
- Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence [13.552044856329648]
We developed a linear-runtime estimator called Windowed Good-Turing (WingIt)
リスクは$widetildeO(mathsfT_mix/n)$で、$mathsfT_mix$は全変動距離におけるチェーンの混合時間を表す。
軌道の周波数が小さい要素に配置される定常質量を近似するために, 推定器を拡張した。
論文 参考訳（メタデータ） (2024-04-08T18:55:07Z) - Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。
我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。
グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
論文 参考訳（メタデータ） (2023-11-29T12:48:33Z) - Graph GOSPA metric: a metric to measure the discrepancy between graphs of different sizes [3.8823562292981393]
本稿では,ノード数が異なる可能性のあるグラフ間の相似性を測定する指標を提案する。
提案したグラフGOSPAメトリクスは、適切に割り当てられたノード、ミスノード、偽ノード、グラフ間のエッジミスマッチに対するノード属性エラーに関連するコストを含む。
論文 参考訳（メタデータ） (2023-11-10T11:40:24Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
本稿では,グラフ上の分布と信号の間の新しい距離を提案する。
GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。
グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
論文 参考訳（メタデータ） (2023-06-05T00:01:17Z) - Tight and fast generalization error bound of graph embedding in metric
space [54.279425319381374]
非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。
我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
論文 参考訳（メタデータ） (2023-05-13T17:29:18Z) - Identifying latent distances with Finslerian geometry [6.0188611984807245]
生成モデルにより、データ空間と測地学は最も非現実的であり、操作が不可能である。
本研究では,引き戻し距離の期待値が明示的に最小となる別の測度を提案する。
高次元では、どちらの測度も$Oleft(frac1Dright)$の速度で収束することが証明される。
論文 参考訳（メタデータ） (2022-12-20T05:57:27Z) - Entropic Optimal Transport in Random Graphs [8.7314407902481]
グラフ解析において、古典的なタスクはノード間の(グループの)類似性の計算によって構成される。
潜在空間におけるノード群間の距離を連続的に推定することは可能であることを示す。
論文 参考訳（メタデータ） (2022-01-11T13:52:34Z) - Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth
Mover's Distance [63.203951161394265]
現代の機械学習では、多くの領域における観測間の相互作用や類似性によって生じる大きなグラフに遭遇することが一般的である。
本研究では,地球移動器距離(EMD)と測地コストを基礎となるグラフ上で比較し,グラフ信号のデータセットを整理する。
いずれの場合も,UDEMDをベースとした埋め込みは,他の手法と比較して高精度な距離を求めることができる。
論文 参考訳（メタデータ） (2021-07-26T17:19:02Z) - Markov Random Geometric Graph (MRGG): A Growth Model for Temporal
Dynamic Networks [0.0]
本稿では,時間的動的ネットワークの成長モデルであるMarkov Random Geometric Graphs (MRGGs)を紹介する。
本稿では, MRGGsを用いて生長グラフの依存構造を検出し, リンク予測問題を解く方法を示す。
論文 参考訳（メタデータ） (2020-06-12T08:35:54Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。