論文の概要: NISQ-ready community detection based on separation-node identification
- arxiv url: http://arxiv.org/abs/2212.14717v1
- Date: Fri, 30 Dec 2022 13:58:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 17:55:31.889605
- Title: NISQ-ready community detection based on separation-node identification
- Title（参考訳）: 分離ノード同定に基づくNISQ対応コミュニティ検出
- Authors: Jonas Stein, Dominik Ott, Mirco Schoenfeld, Sebastian Feld
- Abstract要約: 入力グラフの隣接行列として,QUBO行列をスパースとして表現し,ノード数のみを必要とする新しいQUBO方式を提案する。
QUBO行列の空間性は、典型的には関連する研究において非常に密接なものであり、分離ノードという新しい概念によって大幅に改善される。
- 参考スコア（独自算出の注目度）: 1.3496450124792878
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The analysis of network structure is essential to many scientific areas,
ranging from biology to sociology. As the computational task of clustering
these networks into partitions, i.e., solving the community detection problem,
is generally NP-hard, heuristic solutions are indispensable. The exploration of
expedient heuristics has led to the development of particularly promising
approaches in the emerging technology of quantum computing. Motivated by the
substantial hardware demands for all established quantum community detection
approaches, we introduce a novel QUBO based approach that only needs
number-of-nodes many qubits and is represented by a QUBO-matrix as sparse as
the input graph's adjacency matrix. The substantial improvement on the sparsity
of the QUBO-matrix, which is typically very dense in related work, is achieved
through the novel concept of separation-nodes. Instead of assigning every node
to a community directly, this approach relies on the identification of a
separation-node set, which -- upon its removal from the graph -- yields a set
of connected components, representing the core components of the communities.
Employing a greedy heuristic to assign the nodes from the separation-node sets
to the identified community cores, subsequent experimental results yield a
proof of concept. This work hence displays a promising approach to NISQ ready
quantum community detection, catalyzing the application of quantum computers
for the network structure analysis of large scale, real world problem
instances.
- Abstract（参考訳）: ネットワーク構造の解析は、生物学から社会学まで、多くの科学分野に不可欠である。
これらのネットワークを分割にクラスタリングする計算タスク、すなわちコミュニティ検出問題の解決は一般にNPハードであり、ヒューリスティックな解は不可欠である。
迅速なヒューリスティックスの研究は、量子コンピューティングの新興技術における特に有望なアプローチの開発につながった。
確立された量子コミュニティ検出手法のハードウェア要求により,QUBOベースの新しいアプローチを導入し,ノード数のみを必要とし,QUBO行列を入力グラフの隣接行列としてスパースとして表現する。
QUBO行列の空間性は、典型的には非常に密集しているため、分離ノードという新しい概念によって大幅に改善される。
このアプローチは、すべてのノードをコミュニティに直接割り当てる代わりに、分離ノードセットの識別に依存します。
分離ノードセットから特定されたコミュニティコアにノードを割り当てるために欲深いヒューリスティックを用いることで、その後の実験結果は概念実証をもたらす。
この研究は、大規模実世界の問題インスタンスのネットワーク構造解析に対する量子コンピュータの応用を触媒する、nisqが準備した量子コミュニティ検出への有望なアプローチを示している。
関連論文リスト
- Sifting out communities in large sparse networks [2.666294200266662]
大規模ネットワークにおけるクラスタリングの結果の質を定量化するための直感的な客観的関数を導入する。
この領域に特に適したコミュニティを特定するために,2段階の手法を用いる。
数万のノードからなる大規模ネットワークにおける複雑な遺伝的相互作用を同定する。
論文 参考訳（メタデータ） (2024-05-01T18:57:41Z) - Unsupervised Graph Attention Autoencoder for Attributed Networks using
K-means Loss [0.0]
我々は、属性付きネットワークにおけるコミュニティ検出のための、教師なしのtextbfGraph Attention textbfAutotextbfEncoder に基づく、シンプルで効率的なクラスタリング指向モデルを提案する。
提案モデルは,ネットワークのトポロジと属性情報の両方から表現を十分に学習し,同時に2つの目的,すなわち再構築とコミュニティ発見に対処する。
論文 参考訳（メタデータ） (2023-11-21T20:45:55Z) - Architectures and circuits for distributed quantum computing [0.0]
この論文は、分散パラダイムに基づく量子計算を提供するネットワークを扱う。
この論文の主な貢献は、全体的な忠実度に対するテレゲートの影響を最小限に抑えるコンパイラの定義である。
論文 参考訳（メタデータ） (2023-07-16T00:03:59Z) - A Unified Framework for Exploratory Learning-Aided Community Detection
Under Topological Uncertainty [16.280950663982107]
META-CODEは、ソーシャルネットワークにおける重複コミュニティを検出する統合フレームワークである。
1)新たな再構築損失によってトレーニングされたグラフニューラルネットワーク(GNN)に基づくノードレベルのコミュニティアフィリエイト埋め込み,2)コミュニティアフィリエイトベースのノードクエリによるネットワーク探索,3)エッジ接続に基づくSiameseニューラルネットワークモデルを用いたネットワーク推論,の3つのステップで構成されている。
論文 参考訳（メタデータ） (2023-04-10T10:22:21Z) - QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional
Networks [124.7972093110732]
本稿では,ノード間の局所的なメッセージパッシングをクロスゲート量子演算のシーケンスで学習する量子グラフ畳み込みネットワーク(QuanGCN)を提案する。
現代の量子デバイスから固有のノイズを緩和するために、ノードの接続をスパーズするためにスパース制約を適用します。
我々のQuanGCNは、いくつかのベンチマークグラフデータセットの古典的なアルゴリズムよりも機能的に同等か、さらに優れている。
論文 参考訳（メタデータ） (2022-11-09T21:43:16Z) - High-order Order Proximity-Incorporated, Symmetry and Graph-Regularized
Nonnegative Matrix Factorization for Community Detection [6.573829734173933]
高次近似(HOP)、対称性、グラフ規則化NMF(HSGN)モデルの提案。
HSGNベースのコミュニティ検出器は、高い精度のコミュニティ検出結果を提供するために、ベンチマークと最先端のコミュニティ検出器の両方を著しく上回っている。
論文 参考訳（メタデータ） (2022-03-08T06:45:31Z) - Frequent Itemset-driven Search for Finding Minimum Node Separators in
Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。
頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。
特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文 参考訳（メタデータ） (2022-01-18T11:16:40Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - QD-GCN: Query-Driven Graph Convolutional Networks for Attributed
Community Search [54.42038098426504]
QD-GCNは、ACS問題を解決するために、コミュニティ構造とノード属性を統一するエンドツーエンドフレームワークである。
本稿では、QD-GCNが既存の属性付きコミュニティ検索アルゴリズムを効率性と有効性の両方で上回ることを示す。
論文 参考訳（メタデータ） (2021-04-08T07:52:48Z) - Graph Prototypical Networks for Few-shot Learning on Attributed Networks [72.31180045017835]
グラフメタ学習フレームワーク - Graph Prototypeal Networks (GPN) を提案する。
GPNは、属性付きネットワーク上でテキストミータ学習を行い、ターゲット分類タスクを扱うための高度に一般化可能なモデルを導出する。
論文 参考訳（メタデータ） (2020-06-23T04:13:23Z) - Detecting Communities in Heterogeneous Multi-Relational Networks:A
Message Passing based Approach [89.19237792558687]
コミュニティは、ソーシャルネットワーク、生物学的ネットワーク、コンピュータおよび情報ネットワークを含むネットワークの共通の特徴である。
我々は,全同種ネットワークのコミュニティを同時に検出する効率的なメッセージパッシングに基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-06T17:36:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。