SNAPS · Social Networks: Algorithms, Privacy, and Security

A social network is a network where nodes correspond to individuals (usually, but they may be different entities, e.g. companies) and links indicate some relationship between them. This project is about the development of algorithms for online dynamic social networks, understanding influence processes, and the study of some issues related to security on social network. First we plan to build the algorithmic basis for the problems in the social networks. Our idea concentrates on stating basic combinatorial optimization problems in new settings that are driven by applications to real-time social networks. We plan to study NP-hard problems in a dynamic real-time setting and in the setting where a universal solution has to be stored in limited memory. The study of these problems is motivated by direct applications in social networks such as message broadcasting, clustering, and service localization. The ubiquitous connections through the various social networks put us on a continuous risk. First of all it becomes hard to retain privacy, as collectively these social networks contain sensitive private information. In addition, each social network we are contained in is a new possible threat for our computer system. It might be a source of spam or an entry point of a new virus. In this project we want to construct methods for data anonymization and game-theoretic models for virus and spam spreading in social networks. The applicant as well as the corresponding host form a unit well fit for the aforementioned tasks as they combine expertise related to all those topics.