論文の概要: Efficient Algorithms for Computing Random Walk Centrality
- arxiv url: http://arxiv.org/abs/2510.20604v1
- Date: Thu, 23 Oct 2025 14:36:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 03:08:18.12998
- Title: Efficient Algorithms for Computing Random Walk Centrality
- Title（参考訳）: ランダムウォーク中心性計算のための効率的なアルゴリズム
- Authors: Changan Liu, Zixuan Xie, Ahad N. Zehmakan, Zhongzhi Zhang,
- Abstract要約: 本稿では、2つのスケーラブルなアルゴリズムの基盤となるランダムウォーク中心性の新たな定式化について述べる。
1000万以上のノードを持つ大規模な実世界のネットワークの実験は、提案アルゴリズムの効率性と近似品質を実証している。
- 参考スコア（独自算出の注目度）: 19.36361626345712
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Random walk centrality is a fundamental metric in graph mining for quantifying node importance and influence, defined as the weighted average of hitting times to a node from all other nodes. Despite its ability to capture rich graph structural information and its wide range of applications, computing this measure for large networks remains impractical due to the computational demands of existing methods. In this paper, we present a novel formulation of random walk centrality, underpinning two scalable algorithms: one leveraging approximate Cholesky factorization and sparse inverse estimation, while the other sampling rooted spanning trees. Both algorithms operate in near-linear time and provide strong approximation guarantees. Extensive experiments on large real-world networks, including one with over 10 million nodes, demonstrate the efficiency and approximation quality of the proposed algorithms.
- Abstract（参考訳）: ランダムウォーク中央性(英: Random walk centrality)は、グラフマイニングにおいて、ノードの重要性と影響を定量化するための基本的な指標であり、他の全てのノードからノードにヒットする時間に対する重み付け平均として定義される。
リッチグラフ構造情報とその広範囲の応用を捕捉する能力があるにもかかわらず、この測度を大規模ネットワーク向けに計算することは、既存の手法の計算要求のため、いまだに現実的ではない。
本稿では,2つのスケーラブルアルゴリズムの基盤となるランダムウォーク中央性(ランダムウォーク中央性)の新たな定式化について述べる。
どちらのアルゴリズムもほぼ直線的に動作し、強い近似保証を提供する。
1000万以上のノードを含む大規模な実世界のネットワークに対する大規模な実験は、提案アルゴリズムの効率性と近似品質を実証している。
関連論文リスト
- Fast Geometric Embedding for Node Influence Maximization [49.84018914962972]
低次元空間にグラフを埋め込む効率的な力配置アルゴリズムを導入する。
アプリケーションとして、提案した埋め込みにより、ネットワーク内の高影響ノードを見つけることができ、標準のgreedyアルゴリズムの高速でスケーラブルな代替手段を提供することがわかった。
論文 参考訳（メタデータ） (2025-06-09T05:21:56Z) - Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm [8.329034093208826]
低ランク近似を用いてテンソルネットワークの収縮を効率的に近似する手法を提案する。
提案アルゴリズムは,低ランク近似を行う場合,環境の大部分を組み込む柔軟性を有する。
論文 参考訳（メタデータ） (2024-06-14T07:13:52Z) - A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - Degree-Based Random Walk Approach for Graph Embedding [0.0]
計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。
提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
論文 参考訳（メタデータ） (2021-10-21T19:16:16Z) - Consistency of random-walk based network embedding algorithms [13.214230533788932]
node2vecアルゴリズムとDeepWalkアルゴリズムを行列ファクタリゼーションの観点から検討する。
その結果,観測ネットワークの幅,ランダムウォークのウィンドウサイズ,ノード2vec/DeepWalk埋め込みの収束率との微妙な相互作用が示唆された。
論文 参考訳（メタデータ） (2021-01-18T22:49:22Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Quantized Decentralized Stochastic Learning over Directed Graphs [54.005946490293496]
有向グラフ上で通信する計算ノード間でデータポイントが分散される分散学習問題を考える。
モデルのサイズが大きくなるにつれて、分散学習は、各ノードが隣人にメッセージ(モデル更新)を送信することによる通信負荷の大きなボトルネックに直面します。
本稿では,分散コンセンサス最適化におけるプッシュサムアルゴリズムに基づく有向グラフ上の量子化分散学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-23T18:25:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。