Influence Maximization & Misinformation Countermeasures
Online social networks (OSNs) like Facebook, Twitter, etc. are excellent media for viral marketing. One of the fundamental problems for viral marketing in OSNs is the influence maximization (IM) problem, where the company aims at reaching a widespread product adoption via the word-of-mouth effect by providing free samples of a product to a set of influential individuals. In a graph G, IM can be restate as finding at most k seed nodes (influential individuals) that can influence the maximum number of nodes, either directly or indirectly. A variation of IM, the threshold activation problem (TAP), does not restrict the number of seed nodes. Instead, it aims at using a minimum number of seed nodes to influence at least a fraction of all nodes. As the graph is usually gigantic and also probabilistic, exact solutions to neither IM or TAP are accessible with reasonable computational resources. Thus, the solutions rely on sampling methods and the main objective of research is to design approaches to use less samples while maintaining solution quality.
Objectives:
- Design efficient sampling methods for estimating influence spread in large-scale OSNs
- Study variations of IM, TAP (for example, by considering external influence or different diffusion models)
Selected Publications:
- Alan Kuhnle, J David Smith, Victoria Crawford, and My T. Thai. “Fast Maximization of Non-Submodular, Monotonic Functions on the Integer Lattice,” in Proceedings of ICML, 2018
- Xiang Li, J David Smith, Thang N. Dinh, and My T. Thai. “TipTop: Almost Exact Solutions for Influence Maximization in Billion-Scale Networks,” in IEEE/ACM Transactions on Networking, 2019
- Lan N. Nguyen, Kunxiao Zhou, and My T. Thai. “Influence Maximization at Community Level: A New Challenge with Non-Submodularity,” in IEEE ICDCS, 2019
Information Leakage in Online Social Networks
As an imperative channel for rapid information propagation, OSNs also have their disruptive effects. One of them is the leakage of information, i.e., information could be spread via OSNs to the users whom we may not be willing to share with. Thus, the problem of constructing a circle of trust to share the information with as many friends as possible without further spreading it to unwanted users has become a challenging research topic recently. Our work is the first attempt to study the Maximum Circle of Trust problem, which seek for a close set of friends such that the chance for information spread out to the unwanted users is the smallest. We propose a Fully Polynomial-Time Approximation Scheme (FPTAS)
Objectives:
- Develop and justify leakage models in online social networks
- Devise scalable and efficient methods to construct circles of trust for smart sharing on the fly, given the unwanted targets
Modeling and Analysis of Multiplex Social Networks
Overlapping users of social networks such as Facebook and Twitter link these online social networks into a multiplex of social networks. As different components of the multiplex may have different properties, the multiplex may exhibit emergent phenomena that aren’t present in the simpler case of single-layer social networks. For example, diffusion is likely to occur by different processes and with different speeds; therefore, one problem we consider is the diffusion of influence in a heterogeneous multiplex, where each layer has a different model of diffusion. Given this heterogeneity of diffusion, new approaches to problems such as Influence Maximization (IM) and Threshold Activation Problem (TAP) may be necessary.
Objectives:
- Determine emergent phenomena arising from the added multiplex complexity
- Study heterogeneous diffusion processes and related problems
- Study problems where the diffusion speed are different for networks
Selected Publications:
- D. T. Nguyen, H. Zhang, S. Das, M. T. Thai, and T. N. Dinh. “Least Cost Influence in Multiplex Social Networks: Model Representation and Analysis,” in Proceedings of the IEEE Int Conference on Data Mining (ICDM), 2013
- J David Smith and My T. Thai. “Supporting a Storm: The Impact of Community on GamerGate’s Lifespan,” in IEEE Transactions on Network Science and Engineering, 2019
- H. Zhang, D. T. Nguyen, S. Das, H. Zhang, and M. T. Thai. “Least Cost Influence Maximization Across Multiple Social Networks,” in IEEE Transactions on Networking (ToN), 2015