Abstract
Large bipartite graphs which evolve and grow over time (e.g., new links arrive, old links die out, or link weights change) arise in many settings, such as social networks, co-citations, market-basket analysis, and collaborative filtering.
Our goal is to monitor (i) the centrality of an individual node (e.g., who are the most important authors?) and (ii) the proximity of two nodes or sets of nodes (e.g., who are the most important authors with respect to a particular conference?). Moreover, we want to do this efficiently and incrementally and to provide “any-time” answers. In this chapter we propose pTrack, which is based on random walks with restart, together with some important modifications to adapt these measures to a dynamic, evolving setting. Additionally, we develop techniques for fast, incremental updates of these measures that allow us to track them continuously, as link updates arrive. In addition, we discuss variants of our method that can handle batch updates, as well as place more emphasis on recent links. Based on proximity tracking, we further proposed cTrack, which enables us to track the centrality of the nodes over time. We demonstrate the effectiveness and efficiency of our methods on several real data sets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that in step 2 of GetQij, \(\textrm{1}(.)\) is the indicator function, i.e. it is 1 if the condition in \((.)\) is true and 0 otherwise.
- 2.
- 3.
- 4.
References
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, Hong Kong, 2002.
R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world wide web. Nature, 401:130–131, 1999.
L. Backstrom, D. P. Huttenlocher, J. M. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In KDD, pages 44–54, 2006.
A. Balmin, V. Hristidis, and Y. Papakonstantinou. Objectrank: Authority-based keyword search in databases. In VLDB, pages 564–575, 2004.
A. Broder, R. Kumar, F. Maghoul1, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web: experiments and models. In WWW Conf., 2000.
Y. Chi, X. Song, D. Zhou, K. Hino, and B. L. Tseng. Evolutionary spectral clustering by incorporating temporal smoothness. In KDD, pages 153–162, 2007.
S. Dorogovtsev and J. Mendes. Evolution of networks. Advances in Physics, 51:1079–1187, 2002.
C. Faloutsos, K. S. McCurley, and A. Tomkins. Fast discovery of connection subgraphs. In KDD, pages 118–127, 2004.
M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. SIGCOMM, pages 251–262, Aug-Sept. 1999.
G. Flake, S. Lawrence, C. L. Giles, and F. Coetzee. Self-organization and identification of web communities. IEEE Computer, 35(3), Mar. 2002.
F. Geerts, H. Mannila, and E. Terzi. Relational link-based ranking. In VLDB, pages 552–563, 2004.
D. Gibson, J. Kleinberg, and P. Raghavan. Inferring web communities from link topology. In 9th ACM Conference on Hypertext and Hypermedia, pages 225–234, New York, NY, 1998.
M. Girvan and M. E. J. Newman. Community structure is social and biological networks. In PNAS, pages 7821–7826, 2002.
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.
J. He, M. Li, H.-J. Zhang, H. Tong, and C. Zhang. Manifold-ranking based image retrieval. In ACM Multimedia, pages 9–16, 2004.
D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD, 2003.
Y. Koren, S. C. North, and C. Volinsky. Measuring and extracting proximity in networks. In KDD, 2006.
D. C. Kozen. The Design and Analysis Algorithms. Springer New York, NY 1992.
J. Leskovec, J. M. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD, pages 177–187, 2005.
D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In Proceeding of the 12th CIKM, 2003.
E. Minkov and W. W. Cohen. An email and meeting assistant using graph walks. In CEAS, 2006.
M. E. J. Newman. The structure and function of complex networks. In SIAM Review, 45:167–256, 2003.
L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998. Paper SIDL-WP-1999-0120 (version of 11/11/1999).
J.-Y. Pan, H.-J. Yang, C. Faloutsos, and P. Duygulu. Automatic multimedia cross-modal correlation discovery. In KDD, pages 653–658, 2004.
W. Piegorsch and G. E. Casella. Inverting a sum of matrices. In SIAM Review, vol. 32, pages 470–470, 1990.
J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu. Graphscope: Parameter-free mining of large time-evolving graphs. In KDD, pages 687–696, 2007.
J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos. Neighborhood formation and anomaly detection in bipartite graphs. In ICDM, pages 418–425, 2005.
J. Sun, D. Tao, and C. Faloutsos. Beyond streams and graphs: Dynamic tensor analysis. In KDD, pages 374–383, 2006.
H. Tong and C. Faloutsos. Center-piece subgraphs: Problem definition and fast solutions. In KDD, pages 404–413, 2006.
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.
H. Tong, C. Faloutsos, and Y. Koren. Fast direction-aware proximity for graph mining. In KDD, pages 747–756, 2007.
H. Tong, C. Faloutsos, and J.-Y. Pan. Random walk with restart: Fast solutions and applications. Knowledge and Information Systems: An International Journal (KAIS), 2007.
D. Xin, J. Han, X. Yan, and H. Cheng. Mining compressed frequent-pattern sets. In VLDB, pages 709–720, 2005.
Acknowledgments
This material is based on the work supported by the National Science Foundation under Grants No. IIS-0705359 IIS0808661 and under the auspices of the US Department of Energy by University of California Lawrence Livermore National Laboratory under contract DE-AC52-07NA27344. This work is also partially supported by an IBM Faculty Award, a Yahoo Research Alliance Gift, a SPRINT gift, with additional funding from Intel, NTT, and Hewlett-Packard. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, or other funding parties.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Tong, H., Papadimitriou, S., Yu, P.S., Faloutsos, C. (2010). Proximity Tracking on Dynamic Bipartite Graphs: Problem Definitions and Fast Solutions. In: Yu, P., Han, J., Faloutsos, C. (eds) Link Mining: Models, Algorithms, and Applications. Springer, New York, NY. https://doi.org/10.1007/978-1-4419-6515-8_8
Download citation
DOI: https://doi.org/10.1007/978-1-4419-6515-8_8
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4419-6514-1
Online ISBN: 978-1-4419-6515-8
eBook Packages: Biomedical and Life SciencesBiomedical and Life Sciences (R0)