You are here:
Viewing the minimum dominating set and maximum coverage problems motivated by word-of-mouth marketing in a problem decomposition context
Viewing the minimum dominating set and maximum coverage problems motivated by word-of-mouth marketing in a problem decomposition context
| Publication Type | Report | |
| Year of Publication | 2009 | |
| Authors | Anand Narasimhamurthy; Pádraig Cunningham; Derek Greene | |
| Abstract | Modelling and analyzing the flow of influence is a key challenge in social network analysis. In scenarios where the network is too large to analyze in detail for computational reasons graph partitioning is a useful aid to decompose the large graph into manageable subgraphs. The question that arises in such a situation is, how to partition a given graph such that the the solution obtained by combining the solutions from the individual subgraphs is as close as possible to the optimal solution obtained from the full graph (with respect to a particular objective). While graph cuts such as the min cut, ratio cut and normalised cut are a useful aid in breaking down the large problem into tractable subproblems, they may not yield the optimal graph partitioning with respect to a given objective. A natural question that arises in this scenario is "How close is the solution given by the graph cut to that of the optimal partitioning?'' or in other words "Are the above graph cuts good heuristics?" | |
| Export | Tagged XML BibTex |
| Attachment | Size |
|---|---|
| GraphCoverage_TechReport05.pdf | 203.99 KB |
- Login to post comments
