論文の概要: 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万規模のネットワーク上で効率的に動作し, 最先端の手法に匹敵する性能を発揮することがわかった。
関連論文リスト
- Weak Schur sampling with logarithmic quantum memory [0.0]
弱いシュアサンプリングのための新しいアルゴリズムを提案する。
我々のアルゴリズムは、既約表現をインデックスするヤングラベルと対称群の多重度ラベルの両方を効率的に決定する。
論文 参考訳(メタデータ) (2023-09-21T10:02:46Z) - Exponential Separations in Symmetric Neural Networks [48.80300074254758]
我々は、対称なNetworkparencitesantoro 2017simple ArchitectureをDeepSetsparencitezaheerdeep Architectureの自然な一般化と見なしている。
解析活性化関数の制限の下で、次元が$N$の集合に作用する対称函数を$D$で構成する。
論文 参考訳(メタデータ) (2022-06-02T19:45:10Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳(メタデータ) (2021-07-22T14:25:16Z) - An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。
本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
論文 参考訳(メタデータ) (2021-06-08T23:38:29Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳(メタデータ) (2021-06-04T02:32:26Z) - Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of
Them All? [17.514226416388475]
我々は、個々の公平性の観点からr$-nn問題を研究し、平等な機会を提供する。
クエリから$r$の距離内のすべてのポイントは、返されるのと同じ確率を持つ必要があります。
フェアNN問題の正確かつ近似的な変種に対して,複数の効率的なデータ構造を提案する。
論文 参考訳(メタデータ) (2021-01-26T16:13:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。