Abstract: Many applications of social networks require link anonymity due to the sensitive nature of relationship, while link inference used by attackers in social networks could lead to link disclosure. To disclose the sensitive link relationship between nodes, attackers always depend on graph structure features to carry out their attacking objectives. The previous work only focuses on single structure feature as the background knowledge as well as overlooks the structural proximity of nodes, which will result in inferior inference. Therefore, this paper proposes an efficient inference framework based on node proximity in large-scale social networks. This framework includes matrix decomposition based on graph-clustering, computing proximity of nodes by singular value decomposition for every cluster. The paper also proposes an efficient algorithm, called LinkIn, which uses node proximity as the inferring condition of Bayes’ theorem to boost the posterior probability of links. Experimental results show that the framework outperforms the single methods, and is efficient and scalable in boosting the accuracy of link inference.

Key words: social network, sensitive link, link disclosure, proximity measure

摘要： 社会网络中许多应用需要对敏感链接关系进行匿名保护，然而攻击者利用基于推理的攻击可以披露个体之间的链接隐私关系。当前许多基于网络结构的推理攻击方法尽管能够找出链接关系，但由于没有考虑节点之间的相似度量特征而导致推理效率较低，并且也不适用于推理大规模网络节点的链接关系。提出了一种大规模社会网络中基于节点相似度量特征的敏感链接推理框架。该框架包括基于图聚类的特征矩阵划分，针对每个类进行奇异值分解，进而计算出各节点对之间的相似度量值，再以相似度量值为贝叶斯推理条件来计算节点对之间链接存在性的后验概率。实验结果表明，所提出的敏感链接推理方法有较高的推理准确性，增强了推理效果，尤其是在大规模社会网络中，优势更加明显。

关键词: 社会网络, 敏感链接, 链接披露, 相似度量