document: Identifying early buyers from purchase data Market research has shown that consumers exhibit a variety of different purchasing behaviors ; specifically , some tend to purchase products earlier than other consumers . Identifying such early buyers can help personalize marketing strategies , potentially improving their effectiveness . In this paper , we present a non-parametric approach to the problem of identifying early buyers from purchase data . Our formulation takes as inputs the detailed purchase information of each consumer , with which we construct a weighted directed graph whose nodes correspond to consumers and whose edges correspond to purchases consumers have in common ; the edge weights indicate how frequently consumers purchase products earlier than other consumers . Identifying early buyers corresponds to the problem of finding a subset of nodes in the graph with maximum difference between the weights of the outgoing and incoming edges . This problem is a variation of the maximum cut problem in a directed graph . We provide an approximation algorithm based on semidefinite programming ( SDP ) relaxations pioneered by Goemans and Williamson , and analyze its performance . We apply the algorithm to real purchase data from Amazon.com , providing new insights into consumer behaviors .
doc_bio_tags: O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O