Finding and Visualizing Graph Clusters Using PageRank Optimization | SpringerLink
Skip to main content
Springer Nature Link
Log in

Finding and Visualizing Graph Clusters Using PageRank Optimization

  • Conference paper
Algorithms and Models for the Web-Graph (WAW 2010)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6516))

Included in the following conference series:

Abstract

We give algorithms for finding graph clusters and drawing graphs, highlighting local community structure within the context of a larger network. For a given graph G, we use the personalized PageRank vectors to determine a set of clusters, by optimizing the jumping parameter α subject to several cluster variance measures in order to capture the graph structure according to PageRank. We then give a graph visualization algorithm for the clusters using PageRank-based coordinates. Several drawings of real-world data are given, illustrating the partition and local community structure.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Albert, R., Barabási, A.-L., Jeong, H.: Diameter of the World Wide Web. Nature 401, 130–131 (1999)

    Article  Google Scholar 

  2. Andersen, R., Chung, F.: Detecting sharp drops in PageRank and a simplified local partitioning algorithm. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol. 4484, pp. 1–12. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  3. Andersen, R., Chung, F., Lang, K.: Local graph partitioning using PageRank vectors. In: Proceedings of the 47th Annual IEEE Symposium on Foundation of Computer Science (FOCS 2006), pp. 475–486 (2006)

    Google Scholar 

  4. Brandes, U., Cornelsen, S.: Visual ranking of link structures. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 222–233. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  5. Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30, 107–117 (1998)

    Article  Google Scholar 

  6. Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph structure in the Web. Computer Networks 33, 1–6 (2000)

    Article  Google Scholar 

  7. Chung, F., Horn, P., Tsiatas, A.: Distributing antidote using PageRank vectors. Internet Mathematics 6(2), 237–254 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chung, F., Zhao, W.: A sharp PageRank algorithm with applications to edge ranking and graph sparsification (Preprint), http://www.math.ucsd.edu/~fan/wp/sharp.pdf

  9. Dyer, M.E., Frieze, A.M.: A simple heuristic for the p-centre problem. Operations Research Letters 3(6), 285–288 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  10. Eades, P., Feng, Q.: Multilevel visualization of clustered graphs. In: Proceedings of the International Symposium on Graph Drawing, pp. 101–112 (1996)

    Google Scholar 

  11. Enright, A.J., Van Dongen, S., Ouzounis, C.A.: An efficient algorithm for large-scale detection of protein families. Nucleic Acids Research 30(7), 1575–1584 (2002)

    Article  Google Scholar 

  12. Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the Internet topology. In: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM 1999), pp. 251–262 (1999)

    Google Scholar 

  13. Fortune, S.: A sweepline algorithm for Voronoi diagrams. In: Proceedings of the Second Annual Symposium on Computational Geometry, pp. 313–322 (1986)

    Google Scholar 

  14. Gansner, E., North, C.: An open graph visualization system and its applications to software engineering. Software — Practice and Experience 30(11), 1203–1233 (2000)

    Article  MATH  Google Scholar 

  15. Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99(12), 7821–7826 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  16. Guruswami, V., Micciancio, D., Regev, O.: The complexity of the covering radius problem on lattices and codes. Computational Complexity 14(2), 90–120 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  17. Harel, D., Koren, Y.: Graph drawing by high-dimensional embedding. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 207–219. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  18. Jeh, G., Widom, J.: Scaling personalized Web search. In: Proceedings of the 12th International Conference on World Wide Web, pp. 271–279 (2003)

    Google Scholar 

  19. Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31(1), 7–15 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  20. Lloyd, S.: Least square quantization in PCM. IEEE Transactions on Information Theory 28(2), 129–137 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  21. Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E., Dawson, S.M.: The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology 54(4), 396–405 (2003)

    Article  Google Scholar 

  22. MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, pp. 281–297 (1967)

    Google Scholar 

  23. Mancoridis, S., Mitchell, B.S., Chen, Y., Gansner, E.R.: Bunch: a clustering tool for the recovery and maintenance of software system structures. In: Proceedings of the IEEE International Conference on Software Maintenance, pp. 50–59 (1999)

    Google Scholar 

  24. Moody, J.: Peer influence groups: identifying dense clusters in large networks. Social Networks 23(4), 261–283 (2001)

    Article  Google Scholar 

  25. Newman, M.E.J., Girvan, M.: Finding and evaluating community structure in networks. Physical Review E 69, 026113 (2004)

    Article  Google Scholar 

  26. Ng, A., Jordan, M., Weiss, Y.: On spectral clustering: analysis and an algorithm. Advances in Neural Information Processing Systems 14(2), 849–856 (2002)

    Google Scholar 

  27. Noack, A.: Modularity clustering is force-directed layout. Physical Review E 79, 026102 (2009)

    Article  Google Scholar 

  28. Parker, G., Franck, G., Ware, C.: Visualization of large nested graphs in 3D: navigation and interaction. Journal of Visual Languages and Computing 9(3), 299–317 (1998)

    Article  Google Scholar 

  29. Rudelson, M., Vershynin, R.: Sampling from large matrices: An approach through geometric functional analysis. Journal of the ACM 54(4), Article 21 (2007)

    Google Scholar 

  30. Schaeffer, S.E.: Graph clustering. Computer Science Review 1(1), 27–64 (2007)

    Article  MATH  Google Scholar 

  31. Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888–905 (2000)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, University of California, San Diego, USA

    Fan Chung Graham & Alexander Tsiatas

Authors
  1. Fan Chung Graham
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexander Tsiatas
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Yahoo! Research, 701 First Ave., 94089, Sunnyvale, CA, USA

    Ravi Kumar

  2. Google Research, 1600 Amphitheatre Parkway, 94043, Mountain View, CA, USA

    Dandapani Sivakumar

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Graham, F.C., Tsiatas, A. (2010). Finding and Visualizing Graph Clusters Using PageRank Optimization. In: Kumar, R., Sivakumar, D. (eds) Algorithms and Models for the Web-Graph. WAW 2010. Lecture Notes in Computer Science, vol 6516. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18009-5_9

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-18009-5_9

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-18008-8

  • Online ISBN: 978-3-642-18009-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation