Viewing the minimum dominating set and maximum coverage problems motivated by "word of mouth marketing" in a problem decomposition context

Files in This Item:
 File SizeFormat
Downloaducd-csi-2009-5.pdf203.99 kBAdobe PDF
Title: Viewing the minimum dominating set and maximum coverage problems motivated by "word of mouth marketing" in a problem decomposition context
Authors: Narasimhamurthy, AnandCunningham, PádraigGreene, Derek
Permanent link:
Date: 2009
Online since: 2021-08-05T16:24:28Z
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? In this report we pose the above questions with respect to two graph theoretic problems namely the minimum dominating set and maximum coverage. We partition the graphs using the normalised cut and present results that suggest that the normalised cut provides a “good partitioning” with respect to the defined objective.
Funding Details: Enterprise Ireland
Science Foundation Ireland
Type of material: Technical Report
Publisher: University College Dublin. School of Computer Science and Informatics
Series/Report no.: UCD CSI Technical Reports; ucd-csi-2009-5
Copyright (published version): 2009 the Authors
Keywords: Social network analysisMarketingInfluencersMathematical modelsMinimum dominating set problemMaximum coverage problem
Other versions:
Language: en
Status of Item: Not peer reviewed
This item is made available under a Creative Commons License:
Appears in Collections:CLARITY Research Collection
CASL Research Collection
Computer Science and Informatics Technical Reports

Show full item record

Page view(s)

Last Week
Last month
checked on Sep 20, 2021


checked on Sep 20, 2021

Google ScholarTM


If you are a publisher or author and have copyright concerns for any item, please email and the item will be withdrawn immediately. The author or person responsible for depositing the article will be contacted within one business day.