Managing Information Diffusion in Online Social Networks via Structural Analysis
COM1 Level 2
SR7, COM1-02-07
Abstract:
With the advent of Web 2.0, social networks like Facebook and Twitter offer a platform for millions of users to share information, accelerating the diffusion of information among web users. Many studies have been conducted to understand as well as control the information diffusion process. This thesis seeks to address the challenge of developing methods for expanding as well as preventing information diffusion in highly dynamic and time-sensitive online social networks.
To maximize the influence of good information, we first consider the task of maximizing the number of participants in an event via propagating the event information in a location-based social network. Consider an event that is taking place at a specific position after a few days, we wish to propagate the event information to the users that are located near the event venue before the event taking place. In this thesis, we formalize the problem of targeted influence maximization problem in social networks. We adopt a login model where each user is associated with a login probability and he can be influenced by his neighbors only when he is online. We develop a sampling based algorithm that returns a (1-1=e-")- approximate solution.
We then examine the users that are located between remote clusters in social networks. The theory of brokerage in sociology suggests if contacts between two parties are enabled through a third party, the latter occupies a strategic position of controlling information flows. Such individuals are called brokers and they play a key role in disseminating information. However, there is no systematic approach to identify brokers in online social networks. We formally define the problem of detecting top-k brokers given a social network and show that it is NP-hard. We develop a heuristic algorithm to find these brokers based on the weak tie theory. We further design incremental algorithms to identify brokers to handle the dynamic nature of online social networks.
To minimize the influence of misinformation, we first consider locating nodes to immunize in computer/social networks to control the spread of virus or rumors. In real-world contagions, nodes may get infected by external sources when the propagation is underway. While most studies formalize the problem in a setting where contagion starts at one time point, we model a more realistic situation where there are likely to be many breakouts of contagions over a time window. We call this the node immunization over infectious period (NIIP) problem. We propose a heuristic algorithm to select k nodes to immunize over a time period.
Furthermore, we realize it is more effective to identify nodes to start a truth campaign to block the spreading of rumor. Existing works on limiting misinformation propagation do not take into account the delays of information diffusion or the time point beyond which propagation of misinformation is no longer critical. In this paper, we consider information is propagated with delays and the goal is to reduce the number of rumor-infected users before a deadline. We call this the Temporal Influence Blocking (TIB) problem, and propose a two-phase solution called TIB-Solver to select k nodes to start a truth campaign such that the number of users reached by a rumor is minimized.