Influence maximization on families of graphs

Show full item record

Title: Influence maximization on families of graphs
Author: Mouravski, Andrei
Abstract: We examine computing the maximum expected influence on paths and trees using the independent cascade model. We designed a polynomial time method for determining the expected influence from any initial state on the independent cascade model on acyclic influence graphs in O(|V(G)|² · max {|V(G)|,|V(E)|}) time. We designed a polynomial time program that would computes the maximum expected influence and optimal initially selected nodes on arbitrary paths in O(|V(T)|⁶/[epsilon]) on approximating the maximum expected influence on arbitrary trees with absolute error of at most ([epsilon] · 2|V(T)|).
Record URI: http://hdl.handle.net/1850/13576
Date: 2011

Files in this item

Files Size Format View
AMouravskiThesis2-24-2011.pdf 336.1Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse