social network

Efficient presolving methods for the influence maximization problem in social networks

  • Sheng-Jie Chen
  • Wei-Kun Chen
  • Yu-Hong Dai
  • Jian-Hua Yuan
  • Hou-Shan Zhang
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    We consider the influence maximization problem (IMP) which asks for identifying a limited number of key individuals to spread influence in a social network such that the expected number of influenced individuals is maximized. The stochastic maximal covering location problem (SMCLP) formulation is a mixed integer programming formulation that effectively approximates the IMP by the … Read more

    Convex relaxation for finding planted influential nodes in a social network

  • Lisa Elkin
  • Ting Kei Pong
  • Stephen A. Vavasis
    • Categories Convex Optimization, Data-Mining Tags , ,

    We consider the problem of maximizing influence in a social network. We focus on the case that the social network is a directed bipartite graph whose arcs join senders to receivers. We consider both the case of deterministic networks and probabilistic graphical models, that is, the so-called “cascade” model. The problem is to find the … Read more