論文の概要: Local Differential Privacy for Number of Paths and Katz Centrality

• arxiv url: http://arxiv.org/abs/2310.14000v1
• Date: Sat, 21 Oct 2023 13:00:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 01:44:24.070379
• Title: Local Differential Privacy for Number of Paths and Katz Centrality
• Title（参考訳）: 経路数とカッツ中心性に対する局所微分プライバシー
• Authors: Louis Betzer, Vorapong Suppakitpaisarn, Quentin Hillebrand,
• Abstract要約: 局所微分プライバシー(LDP)の下で経路数とカッツ中心性を公開するアルゴリズムを提案する。 理論的および実験的評価から,我々のアルゴリズムは,クリッピングを回避したアルゴリズムよりもはるかに少ない,許容バイアスと分散を示すことが示された。 我々のカッツ中心性推定は、カッツ中心性が最も高いノードの90%をリコールすることができる。
• 参考スコア（独自算出の注目度）: 1.9749268648715583
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we give an algorithm to publish the number of paths and Katz centrality under the local differential privacy (LDP), providing a thorough theoretical analysis. Although various works have already introduced subgraph counting algorithms under LDP, they have primarily concentrated on subgraphs of up to five nodes. The challenge in extending this to larger subgraphs is the cumulative and exponential growth of noise as the subgraph size increases in any publication under LDP. We address this issue by proposing an algorithm to publish the number of paths that start at every node in the graph, leading to an algorithm that publishes the Katz centrality of all nodes. This algorithm employs multiple rounds of communication and the clipping technique. Both our theoretical and experimental assessments indicate that our algorithm exhibits acceptable bias and variance, considerably less than an algorithm that bypasses clipping. Furthermore, our Katz centrality estimation is able to recall up to 90% of the nodes with the highest Katz centrality.
• Abstract（参考訳）: 本稿では,局所微分プライバシ(LDP)に基づく経路数とカッツ中心性(Katz centrality)のパブリッシュアルゴリズムを提案する。 様々な研究が既にLPPの下でサブグラフカウントアルゴリズムを導入しているが、それらは主に最大5ノードのサブグラフに集中している。 これをより大きな部分グラフに拡張する際の課題は、LPPの下での出版物において、サブグラフのサイズが増加するにつれて、ノイズの累積的および指数的増加である。 この問題に対処するために、グラフ内の各ノードから始まるパスの数をアルゴリズムでパブリッシュし、すべてのノードのKatz集中性をパブリッシュするアルゴリズムを提案する。 このアルゴリズムは複数ラウンドの通信とクリッピング技術を採用している。 我々の理論的および実験的評価は、我々のアルゴリズムが許容されるバイアスとばらつきを示しており、クリッピングをバイパスするアルゴリズムよりもかなり少ないことを示している。 さらに、我々のKatz集中度推定は、最大90%のノードを、最も高いKatz集中度でリコールすることができる。

関連論文リスト

• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。 我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
  論文  参考訳（メタデータ） (2024-03-21T11:57:16Z)
• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [8.15681999722805]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• Communication-Efficient Decentralized Federated Learning via One-Bit Compressive Sensing [52.402550431781805]
  分散連合学習(DFL)は、様々なアプリケーションにまたがる実用性によって人気を博している。 集中型バージョンと比較して、DFLの多数のノード間で共有モデルをトレーニングするのはより難しい。 我々は,iADM (iexact alternating direction method) の枠組みに基づく新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-08-31T12:22:40Z)
• Degree-Based Random Walk Approach for Graph Embedding [0.0]
  計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。 提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
  論文  参考訳（メタデータ） (2021-10-21T19:16:16Z)
• Correlation Clustering in Constant Many Parallel Rounds [42.10280805559555]
  相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。 本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。 我々のアルゴリズムは,ノード数にメモリサブリニアを持つマシンを使用し,一定回数のラウンドでのみ実行しながら,一定の近似を返す。
  論文  参考訳（メタデータ） (2021-06-15T21:45:45Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• The Generalized Mean Densest Subgraph Problem [30.33731479053404]
  1つのパラメータ$p$でパラメータ化された、高密度なサブグラフ対象の新しいファミリーを導入する。 我々の目的は、標準の高密度部分グラフ問題と特別な場合の最大$k$-coreの両方をキャプチャする。 我々の研究の大きな貢献は、理論と実践の両方において、密接な部分グラフに対する様々な種類の剥離アルゴリズムの性能を分析することである。
  論文  参考訳（メタデータ） (2021-06-02T02:58:35Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。 この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。 1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
  論文  参考訳（メタデータ） (2020-08-18T16:22:06Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Quantized Decentralized Stochastic Learning over Directed Graphs [52.94011236627326]
  有向グラフ上で通信する計算ノード間でデータポイントが分散される分散学習問題を考える。 モデルのサイズが大きくなるにつれて、分散学習は、各ノードが隣人にメッセージ(モデル更新)を送信することによる通信負荷の大きなボトルネックに直面します。 本稿では,分散コンセンサス最適化におけるプッシュサムアルゴリズムに基づく有向グラフ上の量子化分散学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-23T18:25:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。