Authenticity Verification on Social Data Outsourcing

Abstract In the social data transaction model, online social networks sell their collected social data to a third-party data service provider, which commonly resells such social data to data users for further mining potential information. However, the data service provider may not be trustworthy and collude with others to return fake data to users. To prevent such malicious activities, data users should verify the correctness and completeness of social data purchased from the data service provider to make sure that no data would tamper and no qualifying results would be omitted. Accordingly, we first propose an authenticity verification scheme, called FakeDetection, for one-dimensional data query. To make our scheme becoming efficient, we further devise an enhanced probabilistic scheme FakeDetection + , which takes partial vertices and neighbors with the identical profile value to generate auxiliary information. To evaluate the efficiency of our schemes, we utilize the real Twitter datasets with 1.6M twitters to perform the experiments. The Twitter with FakeDetection + , takes 69K edges (47M in FakeDetection) into account to detect fake activities with a probability of more than 99%. For the computation overhead, the FakeDetection + scheme only consumes 27.9s (3.8% of that in FakeDetection) to generate auxiliary information for a social graph with 1.6M twitters and their social network.