Limiting the Spread of Misinformation in Social Networks

In recent project, we studied the notion of competing campaigns in a social network and address the problem of influence limitation where a “bad” campaign starts propagating from a certain node in the network and use the notion of limiting campaigns to counteract the effect of misinformation. The problem can be summarized as identifying a subset of individuals that need to be convinced to adopt the competing (or “good”) campaign so as to minimize the number of people that adopt the “bad” campaign at the end of both propagation processes. We show that this optimization problem is NP-hard and provide approximation guarantees for a greedy solution for various definitions of this problem by proving that they are submodular. We experimentally compare the performance of the greedy method to various heuristics. The experiments reveal that in most cases inexpensive heuristics such as degree centrality compare well with the greedy approach. We also study the influence limitation problem in the presence of missing data where the cur- rent states of nodes in the network are only known with a certain probability. We propose a prediction algorithm that is based on generating random spanning trees and evaluate the performance of this approach. The experiments reveal that using the prediction algorithm, we are able to tolerate about 90% missing data before the performance of the algorithm starts degrading and even with large amounts of missing data the performance degrades only to 75% of the performance that would be achieved with complete data.

Related paper: Ceren Budak, Divyakant Agrawal, Amr El Abbadi "Limiting the Spread of Misinformation in Social Networks" WWW 2011. pdf

Detecting influentials in a social network

Why is it that some ideas or products become unusually successful and get adopted widely while others don’t? This question has been puzzling many social scientists, economists, politicians and educators for a long time. Knowing the answer to this question can help deliberately start such successful cascades. In social sciences, many theories have been introduced by economists and social scientists and those theories have been backed by small numbers of case studies. In a recent work, we focused on the popular theories introduced in “The Tipping Point” by Malcolm Gladwell. The basic idea is the crucial effect of three types of “fascinating” people that the author calls Mavens, Connectors and Salesmen on the effectiveness of a cascade. Those people are claimed to “play a critical role in the word-of-mouth epidemics that dictate our tastes, trends and fashions”. We investigated existence of Mavens, Connectors and Salesmen in the blogosphere. We formally defined what it means to be a Maven, Connector or a Salesman and study their effect on the success of cascades in the blogosphere. We also studied the effect of a fourth type of interesting actor that we call Translator, an actor that acts as a bridge between different interest groups and communities. We observe that those four types of important players do in fact exist in the blogosphere. More interestingly, we show that the impact of most of those actors on the effectiveness of cascades is more pronounced when those actors act as intermediaries rather than initiators of cascades.

The paper can be found here

New Trend Definitions and Scalable Solutions for Social Networks

Social networks provide a large-scale information infrastructure for people to discuss and exchange ideas about variety of topics. Detecting trends of such topics is of significant interest for many reasons. For one, it can be used to detect emergent behavior in the network, for instance a sudden increase in the number of people talking about explosives or biological warfare. Information trends can also be viewed as a reflection of societal concerns or even as a consensus of collective decision making. Understanding how a community decides that a topic is trendy can help us better understand how ad-hoc communities are formed and how decisions are made in such communities. In general, constructing “useful” trend definitions and providing scalable solutions that detect such trends will contribute towards a better understanding of human interactions in the context of social media.

As part of an ongoing project, we investigate scalable solutions for various trend definitions that incorporate various important aspects such as the spatiotemporal dimensions of human interaction and the network structure. More precisely, we study trends from two different perspectives; ontology-based trends analysis that depends on features such as temporal and spatial properties of the content that is broadcast and structural trend analysis that depend on structural connections between the users who are broadcasting. Our ultimate goal is to develop a flexible solution that incorporates all such aspects into one framework.

Related paper: Ceren Budak, Divyakant Agrawal, Amr El Abbadi "Structural Trend Analysis for Online Social Networks" VLDB 2011. pdf