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