【论文记录】小应用

【论文记录】小应用

《Bounding User Contributions: A Bias-Variance Trade-off in Differential Privacy》

• 背景：trade-off
  解决方法：limiting the contributions of individual users in order to reduce the sensitivity.

• 举例 · 从数学原理上解释应用差分隐私时需要 trade-off 的原因 ：
  S = { x 1 , x 2 , . . . , x n } mathcal{S} = { x_1,x_2,...,x_n } S={x1​,x2​,...,xn​} quad g ( S ) = ∑ i x i g( mathcal S ) = sum_ix_i g(S)=∑i​xi​ quad 由于 Δ g Delta g Δg发散 , 故设置bound T , 采用 g T ( S ) = ∑ i m i n ( x i , T ) g_T( mathcal S ) = sum_i min(x_i,T) gT​(S)=∑i​min(xi​,T) , 则使 Δ g T = T Delta g_T=T ΔgT​=T
  quadquadquadquad

• 设置 bound 的方法：根据 F-utility 导出 τ 0 ∈ ( 0 , 1 ] tau_0in(0,1] τ0​∈(0,1]
  

《Structural-Based Graph Publishing Under Differential Privacy》

• 背景 : previous methods, such as adjacency matrix, hierarchical random graph, quadtree, etc are often applicable in small-scale graph datasets. However, real graphs are generally large and sparse, leading to high computational expense.

• 算法框架 :1.Fast-unfolding community detection algorithm ,,, 2.The framework of differential privacy based on hierarchical representation

• Fast-unfolding algorithm : 不断划分 , community使得划分后的整个网络的模块度 Q=··· 不断增大。具体的算法过程为：
  1.初始化，将每个点划分在不同的社区中；
  2.对每个节点，将每个点尝试划分到与其邻接的点所在的社区中，计算此时的模块度，判断划分前后的模块度的差值ΔQ是否为正数，若为正数，则接受本次的划分，若不为正数，则放弃本次的划分；
  3.重复以上的过程，直到不能再增大模块度为止；
  4.构造新图，新图中的每个点代表的是步骤3中划出来的每个社区，继续执行步骤2和步骤3，直到社区的结构不再改变为止。

• Hierarchical Structure : hierarchical graph中的叶子结点为原图中的结点，非叶子结点的权值由 P r = e r / ( n L r ⋅ n R r ) P_r=e_r/(n_{L_r}·n_{R_r}) Pr​=er​/(nLr​​⋅nRr​​)计算。举例如 :
  
  a hierarchical graph with higher L L L is a better representation of the network structure than those with lower likelihoods.
  

• computing the probabilities stored in internal nodes with applying Laplace noise.