Document Open Access Logo

Scalable Katz Ranking Computation in Large Static and Dynamic Graphs

Authors Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David A. Bader, Henning Meyerhenke

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.42.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Alexander van der Grinten
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany
Elisabetta Bergamini
  • Karlsruhe Institute of Technology (KIT), Germany
Oded Green
  • School of Computational Science and Engineering, Georgia Institute of Technology, USA
David A. Bader
  • School of Computational Science and Engineering, Georgia Institute of Technology, USA
Henning Meyerhenke
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany

Funding

Most of the work was done while AvdG was affiliated with University of Cologne, Germany, and HM with Karlsruhe Institute of Technology and University of Cologne. Additionally, EB, AvdG and HM were partially supported by grant ME 3619/3-2 within German Research Foundation (DFG) Priority Programme 1736. Funding was also provided by Karlsruhe House of Young Scientists via the International Collaboration Package. Funding for OG and DB was provided in part by the Defense Advanced Research Projects Agency (DARPA) under Contract Number FA8750-17-C-0086. The content of the information in this document does not necessarily reflect the position or the policy of the Government, and no official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.

Cite AsGet BibTex

Alexander van der Grinten, Elisabetta Bergamini, Oded Green, David A. Bader, and Henning Meyerhenke. Scalable Katz Ranking Computation in Large Static and Dynamic Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.42

Abstract

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. In this paper, we consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. While previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. We extend our algorithm to dynamic graphs while maintaining its correctness guarantees. Experiments demonstrate that our static graph algorithm outperforms both numerical approaches and heuristics with speedups between 1.5 x and 3.5 x, depending on the desired quality guarantees. Our dynamic graph algorithm improves upon the static algorithm for update batches of less than 10000 edges. We provide efficient parallel CPU and GPU implementations of our algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of nodes in fractions of seconds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
  • Theory of computation → Parallel algorithms
Keywords
  • network analysis
  • Katz centrality
  • top-k ranking
  • dynamic graphs
  • parallel algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. E. Acar, D. M. Dunlavy, and T. G. Kolda. Link prediction on evolving data using matrix and tensor factorizations. In 2009 IEEE International Conference on Data Mining Workshops, pages 262-269, Dec 2009. URL: http://dx.doi.org/10.1109/ICDMW.2009.54.
  2. Elisabetta Bergamini, Michele Borassi, Pierluigi Crescenzi, Andrea Marino, and Henning Meyerhenke. Computing top-k closeness centrality faster in unweighted graphs. In 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 68-80. Society for Industrial and Applied Mathematics, 2018. URL: http://dx.doi.org/10.1137/1.9781611974317.6.
  3. Patrick Bisenius, Elisabetta Bergamin, Eugenio Angriman, and Henning Meyerhenke. Computing top-k closeness centrality in fully-dynamic graphs. In 2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 21-35. Society for Industrial and Applied Mathematics, 2018. URL: http://dx.doi.org/10.1137/1.9781611975055.3.
  4. Francesco Bonchi, Pooya Esfandiar, David Gleich, Chen Greif, and Laks Lakshmanan. Fast matrix computations for pairwise and columnwise commute times and katz scores. Internet Mathematics, 8:73-112, 03 2012. Google Scholar
  5. Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1):107-117, 1998. Proceedings of the Seventh International World Wide Web Conference. URL: http://dx.doi.org/10.1016/S0169-7552(98)00110-X.
  6. F. Busato, O. Green, N. Bombieri, and D.A. Bader. Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs. In IEEE Proc. High Performance Extreme Computing (HPEC), Waltham, MA, 2018. Google Scholar
  7. Kurt C. Foster, Stephen Q. Muth, John J. Potterat, and Richard B. Rothenberg. A faster katz status score algorithm. Computational & Mathematical Organization Theory, 7(4):275-285, Dec 2001. URL: http://dx.doi.org/10.1023/A:1013470632383.
  8. O. Green and D.A. Bader. cuSTINGER: Supporting Dynamic Graph Algorithms for GPUs. In IEEE Proc. High Performance Embedded Computing Workshop (HPEC), Waltham, MA, 2016. Google Scholar
  9. Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-43, Mar 1953. URL: http://dx.doi.org/10.1007/BF02289026.
  10. J. Kepner, P. Aaltonen, D. Bader, A. Buluç, F. Franchetti, J. Gilbert, D. Hutchison, M. Kumar, A. Lumsdaine, H. Meyerhenke, S. McMillan, C. Yang, J. D. Owens, M. Zalewski, T. Mattson, and J. Moreira. Mathematical foundations of the graphblas. In 2016 IEEE High Performance Extreme Computing Conference (HPEC), pages 1-9, Sept 2016. URL: http://dx.doi.org/10.1109/HPEC.2016.7761646.
  11. Jérôme Kunegis. Konect: The koblenz network collection. In Proceedings of the 22Nd International Conference on World Wide Web, WWW '13 Companion, pages 1343-1350, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2487788.2488173.
  12. Min-Joong Lee, Sunghee Choi, and Chin-Wan Chung. Efficient algorithms for updating betweenness centrality in fully dynamic graphs. Information Sciences, 326:278-296, 2016. URL: http://dx.doi.org/10.1016/j.ins.2015.07.053.
  13. Min-Joong Lee and Chin-Wan Chung. Finding k-highest betweenness centrality vertices in graphs. In Proceedings of the 23rd International Conference on World Wide Web, WWW '14 Companion, pages 339-340, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2567948.2577358.
  14. Jure Leskovec and Rok Sosič. Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1, 2016. Google Scholar
  15. Eisha Nathan and David A. Bader. A dynamic algorithm for updating katz centrality in graphs. In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, ASONAM '17, pages 149-154, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3110025.3110034.
  16. Eisha Nathan and David A. Bader. Approximating personalized katz centrality in dynamic graphs. In Roman Wyrzykowski, Jack Dongarra, Ewa Deelman, and Konrad Karczewski, editors, Parallel Processing and Applied Mathematics, pages 290-302, Cham, 2018. Springer International Publishing. Google Scholar
  17. Eisha Nathan, Geoffrey Sanders, James Fairbanks, Van Emden Henson, and David A. Bader. Graph ranking guarantees for numerical approximations to katz centrality. Procedia Computer Science, 108:68-78, 2017. International Conference on Computational Science, ICCS 2017, 12-14 June 2017, Zurich, Switzerland. URL: http://dx.doi.org/10.1016/j.procs.2017.05.021.
  18. Mark Newman. Networks: An Introduction. Oxford University Press, Inc., New York, NY, USA, 2010. Google Scholar
  19. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. NetworKit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508–530, 2016. URL: http://dx.doi.org/10.1017/nws.2016.20.
  20. A. van der Grinten, E. Bergamini, O. Green, D.A. Bader, and Henning Meyerhenke. Scalable Katz ranking computation in large static and dynamic graphs. arXiv, 2018. URL: http://arxiv.org/abs/1807.03847.
  21. Justin Zhan, Sweta Gurung, and Sai Phani Krishna Parsa. Identification of top-k nodes in large networks using katz centrality. Journal of Big Data, 4(1):16, May 2017. URL: http://dx.doi.org/10.1186/s40537-017-0076-5.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact