確率的ブロックモデルのための差分プライベートコミュニティ検出【JST・京大機械翻訳】

Seif Mohamed; Nguyen Dung; Vullikanti Anil; Tandon Ravi

プレプリント

J-GLOBAL ID：202202219180393397 整理番号：22P0283248

確率的ブロックモデルのための差分プライベートコミュニティ検出【JST・京大機械翻訳】

Differentially Private Community Detection for Stochastic Block Models

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (4件)： , , ,
資料名：
発行年： 2022年01月31日プレプリントサーバーでの情報更新日： 2023年08月17日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

グラフ上のコミュニティ検出の目標は,ユーザ(グラフの隣接行列により表示される)間の接続性を与えるユーザ(例えば,政治的 ation)の根底にあるラベル/属性を回復することである。グラフが確率的ブロックモデル(SBM)から生成されるとき,コミュニティ検出の基本的限界を理解する上で著しい最近の進展があった。特に,シャープな情報理論的限界と効率的なアルゴリズムを,pとqの関数としてSBMに対して得て,それはコミュニティ内とコミュニティ間接続確率を表す。本論文では,頂点間の個々の接続(エッジ)のプライバシーを保存しながら,コミュニティ検出問題を研究した。(ε,δ)エッジ微分プライバシー(DP)の概念に焦点を合わせて,コミュニティラベルの正確な回復のための(p,q),DP予算(ε,δ)と計算効率の間の基本的トレードオフを理解することを追求する。この目的のために,著者らは,異なる個人コミュニティ回復機構(a)安定性ベースメカニズムの3つの広いクラスに対する関連情報理論的トレードオフを提示し,解析した。b)サンプリングベース機構;およびc)グラフ摂動機構。著者らの主な知見は,安定性とサンプリングベースのメカニズムが(p,q)とプライバシー予算(ε,δ)の間の優れたトレードオフをもたらすことである。しかし,これはより高い計算量を犠牲にする。一方,低い複雑性にもかかわらず,グラフ摂動機構は,正確な回復のためにΩ(log(n))としてスケールするプライバシー予算εを必要とする。知る限りでは,これはコミュニティ検出の基本的限界に対するプライバシー制約の影響を研究する最初の研究である。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , , 【Automatic Indexing@JST】

計算機網

, , ,

前のページに戻る