論文の概要: Role Similarity Metric Based on Spanning Rooted Forest
- arxiv url: http://arxiv.org/abs/2110.07872v1
- Date: Fri, 15 Oct 2021 05:50:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-18 14:46:14.942094
- Title: Role Similarity Metric Based on Spanning Rooted Forest
- Title（参考訳）: スパン化根付き森林に基づく役割類似度指標
- Authors: Qi Bao, Zhongzhi Zhang
- Abstract要約: 既存の役割類似度メトリクスは、高時間と空間コストのため、大規模な現実世界ネットワーク上のトップkクエリを処理できない。
textsfForestSimは許容される役割類似度尺度であり、対応するトップk類似度探索アルゴリズムを考案する。
その結果,textsfForestSimは100万規模のネットワーク上で効率的に動作し,最先端の手法に匹敵する性能を発揮することがわかった。
- 参考スコア（独自算出の注目度）: 9.188318506016897
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As a fundamental issue in network analysis, structural node similarity has
received much attention in academia and is adopted in a wide range of
applications. Among these proposed structural node similarity measures, role
similarity stands out because of satisfying several axiomatic properties
including automorphism conformation. Existing role similarity metrics cannot
handle top-k queries on large real-world networks due to the high time and
space cost. In this paper, we propose a new role similarity metric, namely
\textsf{ForestSim}. We prove that \textsf{ForestSim} is an admissible role
similarity metric and devise the corresponding top-k similarity search
algorithm, namely \textsf{ForestSimSearch}, which is able to process a top-k
query in $O(k)$ time once the precomputation is finished. Moreover, we speed up
the precomputation by using a fast approximate algorithm to compute the
diagonal entries of the forest matrix, which reduces the time and space
complexity of the precomputation to
$O(\epsilon^{-2}m\log^5{n}\log{\frac{1}{\epsilon}})$ and $O(m\log^3{n})$,
respectively. Finally, we conduct extensive experiments on 26 real-world
networks. The results show that \textsf{ForestSim} works efficiently on
million-scale networks and achieves comparable performance to the state-of-art
methods.
- Abstract（参考訳）: ネットワーク解析の根本的な問題として,構造的ノード類似性が学界で注目され,幅広い応用で採用されている。
これらの構造的ノード類似性尺度のうち、役割類似性は自己同型配座を含むいくつかの公理的性質を満たすため際立っている。
既存の役割類似度メトリクスは、高時間と空間コストのため、大規模な現実世界ネットワーク上のトップkクエリを処理できない。
本稿では,新たな役割類似度計量,すなわち \textsf{forestsim} を提案する。
本研究は,<textsf{ForestSim} が許容される役割類似度尺度であることを証明し,事前計算が完了すると,トップkクエリを$O(k)$で処理できる対応するトップk類似度探索アルゴリズムである \textsf{ForestSimSearch} を考案する。
さらに,フォレスト行列の対角成分を高速近似アルゴリズムを用いて計算することにより,事前計算の時間と空間の複雑さをそれぞれ$o(\epsilon^{-2}m\log^5{n}\log{\frac{1}{\epsilon}})$と$o(m\log^3{n})$に低減する。
最後に,26の現実世界ネットワークについて広範な実験を行った。
その結果, \textsf{ForestSim} は100万規模のネットワーク上で効率的に動作し, 最先端の手法に匹敵する性能を発揮することがわかった。
関連論文リスト
- Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。
検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。
意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。
各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
論文 参考訳（メタデータ） (2025-02-16T16:12:01Z) - SiReRAG: Indexing Similar and Related Information for Multihop Reasoning [96.60045548116584]
SiReRAGは、類似情報と関連する情報の両方を明示的に考慮する新しいRAGインデックス方式である。
SiReRAGは、3つのマルチホップデータセットの最先端インデックス手法を一貫して上回る。
論文 参考訳（メタデータ） (2024-12-09T04:56:43Z) - (PASS) Visual Prompt Locates Good Structure Sparsity through a Recurrent HyperNetwork [60.889175951038496]
大規模ニューラルネットワークは、視覚や言語処理など、さまざまな領域で顕著なパフォーマンスを示している。
構造的刈り込みの鍵となる問題のひとつは、チャネルの意義を見積もる方法である。
我々は,新しいアルゴリズムフレームワーク,すなわち textttPASS を提案する。
視覚的プロンプトとネットワーク重み統計の両方を入力とし、繰り返し的に層ワイドチャネル間隔を出力するように調整されたハイパーネットワークである。
論文 参考訳（メタデータ） (2024-07-24T16:47:45Z) - Hierarchical Clustering via Local Search [0.0]
階層クラスタリングのための局所探索アルゴリズムを提案する。
任意の局所最適木は少なくとも$fracn-23sum_i jw(i,j)$の収益を保証し、そこでは$n$はオブジェクトの数で、$w: [n] times [n] mathbbR+$は関連する類似関数である。
論文 参考訳（メタデータ） (2024-05-24T23:46:24Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳（メタデータ） (2020-06-15T21:36:00Z) - Low Complexity Sequential Search with Size-Dependent Measurement Noise [19.201555109949677]
本稿では、エージェントが任意の時間にその領域にターゲットが存在するかどうかを問い合わせる領域を選択することができるターゲットローカライゼーション問題について考察する。
アレイ処理における初期ビームアライメント、ネットワークにおける重ヒッタ検出、ロボット工学におけるビジュアルサーチといった実用的応用により、我々は事実上重要な複雑さの制約/指標を考察する。
新規検索戦略として$dyaPM$と$hiePM$が提案されている。
論文 参考訳（メタデータ） (2020-05-15T22:40:18Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。