Wiggins: Detecting Valuable Information in Dynamic Networks with Limited Resources

Posted on February 2, 2016
Teal Banner

Authors: Matteo Riondato (Two Sigma), Ahmad Mahmoody, Eli Upfal

Published in: Proceedings of the 9th ACM International Conference on Web Search and Data Mining (WSDM), pp. 677–686

Presented at: 9th ACM International Conference on Web Search and Data Mining (WSDM), February 22, 2016

Abstract: Detecting new information and events in a dynamic network by probing individual nodes has many practical applications: discovering new web pages, analyzing influence properties in network, and detecting failure propagation in electronic circuits or infections in public drinkable water systems. In practice, it is infeasible for anyone but the owner of the network (if existent) to monitor all nodes at all times. In this work we study the constrained setting when the observer can only probe a small set of nodes at each time step to check whether new pieces of information (items) have reached those nodes. We formally define the problem through an infinite time generating process that places new items in subsets of nodes according to an unknown probability distribution. Items have an exponentially decaying novelty, modeling their decreasing value. The observer uses a probing schedule (i.e., a probability distribution over the set of nodes) to choose, at each time step, a small set of nodes to check for new items. The goal is to compute a schedule that minimizes the average novelty of undetected items. We present an algorithm, Wiggins, to compute the optimal schedule through convex optimization, and then show how it can be adapted when the parameters of the problem must be learned or change over time. We also present a scalable variant of Wiggins for the MapReduce framework. The results of our experimental evaluation on real social networks demonstrate the practicality of our approach.

DOI: https://doi.org/10.1145/2835776.2835830

Download PDF — 1,000.59 KB
References

This is the author’s version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in the Proceedings of the Ninth ACM International Conference on Web Search and Data Mining. http://dx.doi.org/10.1145/2835776.2835830.

The views expressed above are not necessarily the views of Two Sigma Investments, LP or any of its affiliates (collectively, “Two Sigma”).  The information presented above is only for informational and educational purposes and is not an offer to sell or the solicitation of an offer to buy any securities or other instruments. Additionally, the above information is not intended to provide, and should not be relied upon for investment, accounting, legal or tax advice. Two Sigma makes no representations, express or implied, regarding the accuracy or completeness of this information, and the reader accepts all risks in relying on the above information for any purpose whatsoever. Click here for other important disclaimers and disclosures.