Location-and Relation-Based Clustering on Privacy-Preserving Social Networks  

作　　者：Dan Yin Yiran Shen 

机构地区：[1]College of Computer Science and Technology, Harbin Engineering University

出　　处：《Tsinghua Science and Technology》2018年第4期453-462,共10页清华大学学报（自然科学版（英文版）

基　　金：supported by the National Natural Science Foundation of China (Nos. 61602129, 61702132, and 61702133);the Natural Science Foundation of Heilongjiang Province (Nos. QC2017069 and QC2017071);Fundamental Research Funds for the Central Universities (Nos. HEUCFJ170602 and HEUCFJ160601);the China Postdoctoral Science Foundation (No. 166875);Heilongjiang Postdoctoral Fund (No. LBH-Z16042)

摘　　要：Graph clustering has a long-standing problem in that it is difficult to identify all the groups of vertices that are cohesively connected along their internal edges but only sparsely connected along their external edges. Apart from structural information in social networks, the quality of the location-information clustering has been improved by identifying clusters in the graph that are closely connected and spatially compact. However, in real-world scenarios, the location information of some users may be unavailable for privacy reasons, which renders existing solutions ineffective. In this paper, we investigate the clustering problem of privacy-preserving social networks, and propose an algorithm that uses a prediction-and-clustering approach. First, the location of each invisible user is predicted with a probability distribution. Then, each user is iteratively assigned to different clusters. The experimental results verify the effectiveness and efficiency of our method, and our proposed algorithm exhibits high scalability on large social networks.Graph clustering has a long-standing problem in that it is difficult to identify all the groups of vertices that are cohesively connected along their internal edges but only sparsely connected along their external edges. Apart from structural information in social networks, the quality of the location-information clustering has been improved by identifying clusters in the graph that are closely connected and spatially compact. However, in real-world scenarios, the location information of some users may be unavailable for privacy reasons, which renders existing solutions ineffective. In this paper, we investigate the clustering problem of privacy-preserving social networks, and propose an algorithm that uses a prediction-and-clustering approach. First, the location of each invisible user is predicted with a probability distribution. Then, each user is iteratively assigned to different clusters. The experimental results verify the effectiveness and efficiency of our method, and our proposed algorithm exhibits high scalability on large social networks.

关 键 词：CLUSTERING location prediction PRIVACY-PRESERVING social networks 

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术] TP311.13[自动化与计算机技术—计算机科学与技术]