Title: Social Connectivity Optimization Problems on Random Graphs

Speaker: Thomas M. DuBois, University of Maryland

Date/Time: Monday, January 31, 2011, 11:00 am in NM & 10:00 am in CA       

Location: CSRI/90 in SNL/NM & 915/S101 in SNL/CA

Brief Abstract: Network connectivity and propagation problems arise naturally in many social networks. We examine problems where some property, such as an infection or influence, starts from some initially seeded set of nodes and every affected node transmits the property to its neighbors with a probability determined by the connecting edge. Thus the core problem becomes one of connectivity in a random-graph – the probability of a node v being affected is the probability that there is a path to it in the random graph from one of the seed nodes. We may wish to aid, disrupt, or simply monitor this connectivity. To that end we study several combinatorial optimization problems on random graphs, and derive heuristics whose effectiveness we will show through simulation, mathematical proof, or both.

BIO:  Thomas DuBois is a Ph.D. candidate at the University of Maryland, Department of Computer Science where he works closely with his advisor, Aravind Srinivasan.  He graduated with a B.S from Carnegie Mellon and worked in industry as a software developer before returning to school and researching algorithms for and analysis of large (often randomized) networks.  His main contributions involve large social networks with randomized edges, these include applications in network-aware epidemic minimization and social network trust inference.  His additional interests include combinatorial optimization as well as randomized, distributed, and parallel algorithms, particularly those with direct, real-world applications.

CSRI POC: Jean-Paul Watson, 505-845-8887