論文の概要: 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万規模のネットワーク上で効率的に動作し, 最先端の手法に匹敵する性能を発揮することがわかった。
関連論文リスト
- (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) - Scalable network reconstruction in subquadratic time [0.0]
本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。
我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
論文 参考訳（メタデータ） (2024-01-02T19:00:13Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳（メタデータ） (2020-06-15T21:36:00Z) - DC-NAS: Divide-and-Conquer Neural Architecture Search [108.57785531758076]
本稿では,ディープ・ニューラル・アーキテクチャーを効果的かつ効率的に探索するためのディバイド・アンド・コンカ(DC)手法を提案する。
ImageNetデータセットで75.1%の精度を達成しており、これは同じ検索空間を使った最先端の手法よりも高い。
論文 参考訳（メタデータ） (2020-05-29T09:02:16Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。