IAI Colloquia Series at ISR: S. Raghavan, "Information and Influence Propagation on Social Networks"

Wednesday, November 7, 2012
4:00 p.m.
1146 A.V. Williams Building
Pam White
301 405 6615
pwhite@umd.edu

Intelligent Automation, Inc. Colloquia Series
@ The Institute for Systems Research

Information and Influence Propagation on Social Networks: The Least Cost Influence Problem

| video |

Professor S. "Raghu" Raghavan
Institute for Systems Research
and Robert H. Smith School of Business

Abstract
Motivated by problems that arise in the online marketing of products, we analyze the product diffusion process on a social network and allow for the provision of incentives to individuals that result in product adoption. The desire is to minimize the incentives paid out while ensuring that all nodes in the social network adopt the product. This problem is called the Least Cost Influence Problem (LCIP) and also has an application in epidemiology. We analyze the LCIP on a tree network, and show that when the neighbors equally influence an individual the problem is polynomially solvable via a dynamic programming (DP) algorithm. This DP can be nicely interpreted as a greedy algorithm. We also provide a polyhedral description of the LCIP. Specifically, a linear program whose constraint matrix is totally unimodular. We then consider the LCIP on a general graph, and enhance our formulation to address this situation. We develop a branch-and-cut method for the LCIP on a general graph. Preliminary computational results will be presented.

Biography
Dr. Raghavan is a Professor at the Smith School of Business as well as the Institute for Systems Research at the University of Maryland. His research interests and activities cover a broad domain including--- auction design, data mining, economics, information systems, computational marketing, networks, optimization, and telecommunications. He has published on a wide variety of topics (including telecommunications, electronic markets, and data mining) and numerous academic outlets such as Management Science, Operations Research, Decision Support Systems, and the INFORMS Journal on Computing. He holds two patents, and has won numerous awards for his research work. He is most proud of his Ph.D. students (8 graduated and 2 current) who have done outstanding research, and won several major awards for their doctoral dissertation work.

Audience: Clark School  Graduate  Undergraduate  Faculty  Post-Docs  Corporate 

 

May 2020

SU MO TU WE TH FR SA
26 27 28 29 30 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31 1 2 3 4 5 6
Submit an Event