With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
Probabilistic connectivity problems arise naturally in many social networks. In particular the spread of an epidemic across a population and social trust inference motivate much of our work. 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. Many problems in this area involve connectivity in a random-graph - the probability of a node 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. In our core applications, public health officials wish to minimize an epidemic’s spread over a population, and connectivity in a social network suggests how closely tied its users are. In support of these and other applications, we study several combinatorial optimization problems on random-graphs. We derive algorithms and demonstrate their effectiveness through simulation, mathematical proof, or both.
Advisor: | Srinivasan, Aravind |
Commitee: | Gasarch, William, Golbeck, Jennifer, Makowski, Armand, Marathe, Madhav, Mount, David |
School: | University of Maryland, College Park |
Department: | Computer Science |
School Location: | United States -- Maryland |
Source: | DAI-B 72/10, Dissertation Abstracts International |
Source Type: | DISSERTATION |
Subjects: | Social structure, Computer science |
Keywords: | Probabilistic connectivity, Social network, Social trust inference, Trust inference |
Publication Number: | 3461511 |
ISBN: | 978-1-124-74955-6 |