poster

iPoG: fast interactive proximity querying on graphs

Authors:

Christos FaloutsosAuthors Info & Claims

CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

Pages 1673 - 1676

https://doi.org/10.1145/1645953.1646201

Published: 02 November 2009 Publication History

Abstract

Given an author-conference graph, how do we answer proximity queries (e.g., what are the most related conferences for John Smith?); how can we tailor the search result if the user provides additional yes/no type of feedback (e.g., what are the most related conferences for John Smith given that he does not like ICML?)? Given the potential computational complexity, we mainly devote ourselves to addressing the computational issues in this paper by proposing an efficient solution (referred to as iPoG-B) for bipartite graphs. Our experimental results show that the proposed fast solution (iPoGB) achieves significant speedup, while leading to the same ranking result.

References

[1]

B. Aditya, G. Bhalotia, S. Chakrabarti, A. Hulgeri, C. Nakhe, and S. S. Parag. Banks: Browsing and keyword searching in relational databases. In VLDB, pages 1083--1086, 2002.

Digital Library

[2]

A. Agarwal, S. Chakrabarti, and S. Aggarwal. Learning to rank networked entities. In KDD, pages 14--23, 2006.

Digital Library

[3]

A. Balmin, V. Hristidis, and Y. Papakonstantinou. Objectrank: Authority-based keyword search in databases. In VLDB, pages 564--575, 2004.

Digital Library

[4]

H. Cheng, P.-N. Tan, J. Sticklen, and W. F. Punch. Recommendation via query centered random walk on k-partite graph. In ICDM, pages 457--462, 2007.

Digital Library

[5]

C. Faloutsos, K. S. McCurley, and A. Tomkins. Fast discovery of connection subgraphs. In KDD, pages 118--127, 2004.

Digital Library

[6]

F. Geerts, H. Mannila, and E. Terzi. Relational link-based ranking. In VLDB, pages 552--563, 2004.

Digital Library

[7]

M. Grötschel, C. L. Monma, and M. Stoer. Design of survivable networks. In Handbooks in Operations Research and Management Science 7: Network Models. North Holland, 1993.

[8]

J. He, M. Li, H.-J. Zhang, H. Tong, and C. Zhang. Manifold-ranking based image retrieval. In ACM Multimedia, pages 9--16, 2004.

Digital Library

[9]

Y. Koren, S. C. North, and C. Volinsky. Measuring and extracting proximity in networks. In KDD, pages 245--255 2006.

Digital Library

[10]

J.-Y. Pan, H.-J. Yang, C. Faloutsos, and P. Duygulu. Automatic multimedia cross-modal correlation discovery. In KDD, pages 653--658, 2004.

Digital Library

[11]

H. Tong and C. Faloutsos. Center-piece subgraphs: problem definition and fast solutions. In KDD, pages 404--413, 2006.

Digital Library

[12]

H. Tong, C. Faloutsos, B. Gallagher, and T. Eliassi-Rad. Fast best-effort pattern matching in large attributed graphs. In KDD, pages 737--746, 2007.

Digital Library

[13]

H. Tong, C. Faloutsos, and Y. Koren. Fast direction-aware proximity for graph mining. In KDD, pages 747--756, 2007.

Digital Library

[14]

H. Tong, C. Faloutsos, and J.-Y. Pan. Random walk with restart: Fast solutions and applications. Knowledge and Information Systems: An International Journal (KAIS), 2008.

Digital Library

[15]

H. Tong, S. Papadimitriou, P. S. Yu, and C. Faloutsos. Proximity tracking on time-evolving bipartite graphs. In SDM, pages 704--715, 2008.

[16]

H. Tong, H. Qu, and H. Jamjoom. Measuring proximity on graphs with side information. In ICDM, pages 598--607, 2008.

Digital Library

Cited By

Li CShan MLin S(2015)On team formation with expertise query in collaborative social networksKnowledge and Information Systems10.1007/s10115-013-0695-x42:2(441-463)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1007/s10115-013-0695-x
Tong HChung CBroder AShim KSuel T(2014)Query complex graph patternsProceedings of the 23rd International Conference on World Wide Web10.1145/2567948.2579029(1195-1196)Online publication date: 7-Apr-2014
https://dl.acm.org/doi/10.1145/2567948.2579029
Bogdanov PSingh AHe QIyengar ANejdl WPei JRastogi R(2013)Accurate and scalable nearest neighbors in large networks based on effective importanceProceedings of the 22nd ACM international conference on Information & Knowledge Management10.1145/2505515.2505522(1009-1018)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2505515.2505522
Show More Cited By

Index Terms

iPoG: fast interactive proximity querying on graphs
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Measuring and extracting proximity graphs in networks

Measuring distance or some other form of proximity between objects is a standard data mining tool. Connection subgraphs were recently proposed as a way to demonstrate proximity between nodes in networks. We propose a new way of measuring and extracting ...
Measuring Proximity on Graphs with Side Information
ICDM '08: Proceedings of the 2008 Eighth IEEE International Conference on Data Mining

This paper studies how to incorporate side information (such as users' feedback) in measuring node proximity on large graphs. Our method (ProSIN) is motivated by the well-studied random walk with restart (RWR). The basic idea behind ProSIN is to ...
Nordhaus-Gaddum relations for proximity and remoteness in graphs

The transmission of a vertex in a connected graph is the sum of all distances from that vertex to the others. It is said to be normalized if divided by n-1, where n denotes the order of the graph. The proximity of a graph is the minimum normalized ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

November 2009

2162 pages

ISBN:9781605585123

DOI:10.1145/1645953

General Chairs:
David Cheung
University of Hong Kong, Hong Kong
,
Il-Yeol Song
Drexel University, USA
,
Program Chairs:
Wesley Chu
UCLA, USA
,
Xiaohua Hu
Drexel University, USA
,
Jimmy Lin
University of Maryland, USA

Copyright © 2009 ACM.

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: 02 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

CIKM '09

Sponsor:

CIKM '09: Conference on Information and Knowledge Management

November 2 - 6, 2009

Hong Kong, China

Acceptance Rates

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

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
285
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li CShan MLin S(2015)On team formation with expertise query in collaborative social networksKnowledge and Information Systems10.1007/s10115-013-0695-x42:2(441-463)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1007/s10115-013-0695-x
Tong HChung CBroder AShim KSuel T(2014)Query complex graph patternsProceedings of the 23rd International Conference on World Wide Web10.1145/2567948.2579029(1195-1196)Online publication date: 7-Apr-2014
https://dl.acm.org/doi/10.1145/2567948.2579029
Bogdanov PSingh AHe QIyengar ANejdl WPei JRastogi R(2013)Accurate and scalable nearest neighbors in large networks based on effective importanceProceedings of the 22nd ACM international conference on Information & Knowledge Management10.1145/2505515.2505522(1009-1018)Online publication date: 27-Oct-2013
https://dl.acm.org/doi/10.1145/2505515.2505522
Li CShan M(2013)X2-SearchProceedings of the 2013 Conference on Technologies and Applications of Artificial Intelligence10.1109/TAAI.2013.44(176-181)Online publication date: 6-Dec-2013
https://dl.acm.org/doi/10.1109/TAAI.2013.44
Farhadi FHoseini EHashemi SHamzeh A(2012)TeamFinderProceedings of the 2012 IEEE 12th International Conference on Data Mining Workshops10.1109/ICDMW.2012.54(107-114)Online publication date: 10-Dec-2012
https://dl.acm.org/doi/10.1109/ICDMW.2012.54
Farhadi FSorkhi MHashemi SHamzeh A(2012)An Effective Framework for Fast Expert Mining in Collaboration Networks: A Group-Oriented and Cost-Based MethodJournal of Computer Science and Technology10.1007/s11390-012-1245-927:3(577-590)Online publication date: 19-May-2012
https://doi.org/10.1007/s11390-012-1245-9
Lee WLee JSong JEom C(2011)Maximum Reliable Tree for Social Network SearchProceedings of the 2011 IEEE Ninth International Conference on Dependable, Autonomic and Secure Computing10.1109/DASC.2011.201(1243-1249)Online publication date: 12-Dec-2011
https://dl.acm.org/doi/10.1109/DASC.2011.201
Li CShan M(2010)Team Formation for Generalized Tasks in Expertise Social NetworksProceedings of the 2010 IEEE Second International Conference on Social Computing10.1109/SocialCom.2010.12(9-16)Online publication date: 20-Aug-2010
https://dl.acm.org/doi/10.1109/SocialCom.2010.12

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents