Network Connectivity and Related Optimization Problems on Random Graphs

Date Added: Dec 2009
Format: PDF

Network connectivity and propagation problems arise naturally in many social networks. The authors 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. They may wish to aid, disrupt, or simply monitor this connectivity.