Graph Properties and Algorithms in Social Networks: Privacy, Sybil Attacks, and the Computer Science Community
COM2 Level 4
Executive Classroom, COM2-04-02
Abstract:
Any relationship between individuals or organizations can be modeled by a social graph. One prime example where social graph emerges is an online social network. Naturally, general questions about graphs may arise in the social graph; however, because of the semantics of the specific social graph, new and specific problems also arise. There are three different issues in social graphs investigated in this thesis: privacy, security, and utilization of community structure.
This thesis investigates the privacy-utility tradeoff between the online social network owner (as a policymaker) and a crawler whose goal is to gather as much data as possible. Online social networks, depending on their nature, may reveal user relationship information up to more than one degree of separation. Privacy attacks can cause significant privacy leakage, and we investigate the effectiveness of such attacks and their mitigation.
One notable attack in online social networks is the sybil attack, where an attacker creates multiple fake accounts to gain a disproportional advantage in the system. Many graph-based sybil defenses have been proposed to detect or mitigate the attack, however, most of them rely on the assumption that there are only a few attack edges between honest users and sybil nodes. To enable the investigation of the effect of a large number attack edges, a new attack model is proposed in this thesis. Furthermore, a graph transformation called the strong link graph is proposed as a framework for sybil defenses with the goal to increase the effectiveness of sybil detection techniques when there are a larger number of attack edges. Comprehensive evaluation suggests that the strong link graph is able to significantly increase the effectiveness of sybil defenses in detecting sybil nodes.
We investigate how to exploit the community structure of researchers and authors to measure the relatedness between conferences. The proposed relatedness measure is well-aligned with conference topic and rating. Several methods are proposed in this thesis to predict conference rating and categorize conferences based on the relatedness measure.