skip to main content
10.1145/1321440.1321526acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Finding dense and isolated submarkets in a sponsored search spending graph

Published: 06 November 2007 Publication History

Abstract

Methods for improving sponsored search revenue are often tested or deployed within a small submarket of the larger marketplace. For many applications, the ideal submarket contains a small number of nodes, a large amount of spending within the submarket, and a small amount of spending leaving the submarket. We introduce an efficient algorithm for finding submarkets that are optimal for a user-specified tradeoff between these three quantities. We apply our algorithm to find submarkets that are both dense and isolated in a large spending graph from Yahoo! sponsored search.

References

[1]
Z. Abrams, O. Mendelevitch, J. Tomlin. Optimal Delivery of Sponsored Search Advertisements Subject to Budget Constraints. In ACM Conference on Electronic Commerce, pages 282--278, 2007.
[2]
S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. In STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 222--231, New York, NY, USA, 2004. ACM Press.
[3]
M. Babenko, J. Derryberry, A. V. Goldberg, R. E. Tarjan, and Y. Zhou. Experimental Evaluation of Parametric Maximum Flow Algorithms. Workshop on Experimental Algorithms (WEA), Rome, Italy, June 6-8, 2007.
[4]
M. L. Balinksi. On a selection problem. Management Science, 17:3, 230--231. 1970.
[5]
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[6]
J. Joseph, M. Carrasco, D. Fain, K. Lang, and L. Zhukov. Clustering of bipartite advertiser-keyword graph. Workshop on Large Scale Clustering at IEEE ICDM 2003.
[7]
M. Charikar. Greedy approximation algorithms for finding dense components in a graph. In APPROX, pp. 84--95, 2000.
[8]
B. V. Cherkassky and A. V. Goldberg. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19(4):390--410, 1997.
[9]
I. S. Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In ACM SIGKDD International Conference on Knowledge discovery and data mining, pages 269--274, San Francisco, August 2001.
[10]
I. Dhillon, Y. Guan, and B, Kulis, A Fas tKernel-based Multilevel Algorithm for Graph Clustering, In SIGKDD, 2005.
[11]
W. E. Donath and A. J. Hoffman. Lower bounds for partitioning of graphs. IBM J. Res. Develop., 17:420--425, 1973.
[12]
U. Feige and R. Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection. SIAM J. Comput. 31(4): 1090--1118 (2002)
[13]
U. Feige, D. Peleg, and G. Kortsarz. The dense k-subgraph problem. Algorithmica, 29(3), 410--421, 2001.
[14]
U. Feige and M. Seltser. On the densest k-subgraph problem. Weizmann Institute Technical Report CS 97-16, (1997).
[15]
G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18:30--55, 1989.
[16]
A. V. Goldberg. Finding a maximum density subgraph. Technical report, UCB CSD 84/71, University of California, Berkeley, 1984.
[17]
R. Kannan, S. Vempala, and A. Vetta. On clusterings: Good, bad and spectral. J. ACM, 51(3):497--515, 2004.
[18]
Dorit S. Hochbaum. The Pseudoflow Algorithm and the Pseudoflow-based Simplex for the Maximum Flow Problem. In IPCO, pages 325--337, 1998.
[19]
R. Kannan and V. Vinay. Analyzing the Structure of Large Graphs. Manuscript, (1999).
[20]
G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput., 20(1):359--392, 1998.
[21]
G. Kortsarz and D. Peleg. Generating sparse 2-spanners. J. Algorithms, 17(2):222--236, 1994.
[22]
Y. Kluger, R. Basri, J. T. Chang, and M. Gerstein. Spectral biclustering of microarray data: Coclustering genes and conditions. Genome Research, 13(4):703--716, April 2003.
[23]
K. Lang and S. Rao. A flow-based method for improving the expansion or conductance of graph cuts. In IPCO, pages 325--337, 2003.
[24]
T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM (JACM), 46(6):787--832, 1999.
[25]
H. Narayanan, S. Roy, and S. Patkar, Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach, Journal of Algorithms, v. 21 n. 2, p.306--330, Sept. 1996
[26]
S. B. Patkar and H. Narayanan. Improving graph partitions using submodular functions. Discrete Appl. Math. 131, 2 (Sep. 2003), 535--553.
[27]
J. C. Picard, M. Queyeranne, Selected applications of minimum cuts in networks, INFOR-Canada J. Oper. Res. Inform. Process. 20 (1982) 394--422.
[28]
A. Pothen, H. Simon, and K. Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM Journal of Matrix Analysis and Applications, 11:430--452, 1990.
[29]
J. M. W. Rhys. A selection problem of shared fixed costs and network flows. Management Science, 17:3, 200--207. 1970.
[30]
J. Shi and J. Malik. Normalized cuts and image segmentation. PAMI, 22(8):888--905, 2000.
[31]
B. Zhang, J. Ward, and Q. Feng. A Simultaneous Maximum Flow Algorithm for the Selection Model INFORMS 2004.
[32]
B. Zhang, J. Ward, and Q. Feng, A Simultaneous Maximum Flow Algorithm, Hewlett-Packard Research Laboratories Technical Report HPL-2004-189.

Cited By

View all
  • (2024)Game Theoretic Clustering for Finding Strong CommunitiesEntropy10.3390/e2603026826:3(268)Online publication date: 18-Mar-2024
  • (2022)Finding Top-r Influential Communities under Aggregation Functions2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00191(1941-1954)Online publication date: May-2022
  • (2020)Dense Sub-Circuit Reduction in RC Circuits2020 15th International Conference on Computer Engineering and Systems (ICCES)10.1109/ICCES51560.2020.9334616(1-6)Online publication date: 15-Dec-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management
November 2007
1048 pages
ISBN:9781595938039
DOI:10.1145/1321440
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. dense subgraphs
  2. e-commerce
  3. parametric flow
  4. pareto-optimality
  5. sparse cuts
  6. sponsored search
  7. vector-valued optimization

Qualifiers

  • Research-article

Conference

CIKM07

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Game Theoretic Clustering for Finding Strong CommunitiesEntropy10.3390/e2603026826:3(268)Online publication date: 18-Mar-2024
  • (2022)Finding Top-r Influential Communities under Aggregation Functions2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00191(1941-1954)Online publication date: May-2022
  • (2020)Dense Sub-Circuit Reduction in RC Circuits2020 15th International Conference on Computer Engineering and Systems (ICCES)10.1109/ICCES51560.2020.9334616(1-6)Online publication date: 15-Dec-2020
  • (2019)Response Prediction for Low-Regret AgentsWeb and Internet Economics10.1007/978-3-030-35389-6_3(31-44)Online publication date: 3-Dec-2019
  • (2015)Robust local community detectionProceedings of the VLDB Endowment10.14778/2752939.27529488:7(798-809)Online publication date: 1-Feb-2015

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media