Event
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
http://www.isr.umd.edu/events/ISR_Colloquia_Series/index.htm
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.
