GRAPH PROPERTIES AND ALGORITHMS IN SOCIAL NETWORKS: PRIVACY, SYBIL ATTACKS, AND THE COMPUTER SCIENCE COMMUNITY

Abstract

Several issues in social graphs are investigated: privacy, security, and community structure. The privacy-utility tradeoff in social networks is investigated, and two graph restrictions are proposed allowing the service provider to control the tradeoff. The link privacy attack where an attacker attempts to obtain the link structure of the social graph is investigated; this thesis shows that such attack can be amplified with degree inference. The Sybil (fake accounts) attack is a fundamental attack on online social networks. We propose a new attack model to investigate Sybil attack under a large number of attack edges. Furthermore, strong link graph, a framework for Sybil defenses is proposed to increase their effectiveness in detecting Sybil attacks. A relatedness measure is proposed based on the community structure of CS conferences and is shown to be well-aligned with conference rating and topics, which in turn is useful for automatic conference categorization.