Submodularity

This is a technical method discussed in Social Media Analysis 10-802 in Spring 2010.

Submodularity is a property of cost functions that explains the utility of greedy methods and is able to speed up performance when used on cost functions that have this trait.

For the sets $A\subseteq B$ and an additional element $s$ that is not $B$. A cost (or reward) function on these sets is said to be sumbodular if

$R(A\cup \{s\})-R(A)\geq R(B\cup \{s\})-R(B)$

Submodularity can be thought of as diminishing returns. In the sensor placement problem, this can be thought of as getting less bang for your buck. As you continue to add senors the network, each new sensor is more likely to overlap in coverage with existing ones. Because of this, greedy methods that place sensors according minimizing cost at every step perform relatively well.

Related Papers

• The paper by Cost Effective Outbreak Detection in Networks uses submodularity to efficiently place sensors in a Water Sensor Network and determine which blogs to read in a Network of Blogs
• The paper by Khalid El-Arini et al Turning Down the Noise in the Blogosphere uses submodularity to improve web-search results with customizable preferences.