[Title] Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem
[Speaker] S. (Raghu) Raghavan, University of Maryland
[Host] Dr. Xiaolei Xie
[Time] 13:00-14:00, Aug. 14, 2018 (Tuesday)
[Venue]  Shunde Bldg., Rm. 510
[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)
[Bio] Dr. Raghavan is passionate about using quantitative methods for better decision making. He enjoys teaching business analytics courses, and is a recipient of many teaching awards. These include (i) the INFORMS Prize for the Teaching of OR/MS Practice, (ii) the Legg-Mason Teaching Innovation award at the Smith School, and (iii) several Smith School Distinguished Teaching Awards. His research interests and activities cover a broad domain including---auction design, data mining, economics, information systems, computational marketing, logistics, networks, optimization, and telecommunications. He has published on a wide variety of topics and numerous academic outlets such as Computers & Operations Research, Decision Sciences, Discrete Applied Mathematics, INFORMS Journal on Computing, Management Science, Networks, Operations Research, and Transportation Science. He holds two patents, and has won numerous awards for his work. These include (i) the Dantzig award for the best doctoral dissertation, (ii) the INFORMS Computing Society Prize (twice); once for innovative contributions to the field of data mining, and a second time for his contributions to public sector auction design, (iii) the Glover-Klingman Prize for the best paper in the journal Networks, (iv) the Management Science Strategic Innovation Prize by the European Operations Research Society, (v) the INFORMS Telecommunications Section Best Paper Award, (vi) 2nd Prize in the INFORMS Junior Faculty Paper Competition, (vii) Finalist for the European Operations Research Society Excellence in Practice Award, and (viii) Finalist for the Wagner Prize for Excellence in Operations Research Practice. Prior to joining the Smith School he led the Optimization Group at U S WEST Advanced Technologies.
All interested are welcome!