Title: Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem

Speaker: S. (Raghu) Raghavan, University of Maryland (Dean’s Professor of Management Science & Operations Management, The Robert H. Smith School of Business & Institute for Systems Research, University of Maryland)

Date/Place: 13 February at 11H, room A02, Télécom SudParis, 9 rue Charles Fourier 91011 Evry

Abstract: Motivated by applications arising on social networks, we study a problem called the Positive Influence Dominating Set (PIDS) problem that generalizes the dominating set problem. Given a graph G = (V,E), each node i in V has a weight, denoted by b(i), and a neighbor requirement, denoted by g(i). We seek a subset P of V such that a node i not in P is adjacent to at least g(i) members of P and the sum of weights of those nodes in P is minimized. Notice, when g(i)=k for all nodes in the graph we obtain the k-dominating set problem, where k=1 gives the dominating set problem. We discuss two formulations for the PIDS problem that follow directly from the dominating set problem. Then based on a novel edge splitting idea we derive a strong and compact extended formulation for the PIDS problem. By projecting the extended formulation, we obtain an equivalent formulation with fewer variables. Both of these formulations are tight on trees, showing that we have a complete description of the polytope of the PIDS problem on trees. We build upon these two formulations, and experiment on a large set of real-world social networks. Our projected formulation significantly outperforms the other formulations and can solve problems on real-world social networks with up to 2.5 million edges and 7.9 million nodes.

(Joint work with Professor Rui Zhang, University of Colorado)