research-article

Open access

Efficient Approximation Algorithms for Spanning Centrality

Authors:

Bo TangAuthors Info & Claims

KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

Pages 3386 - 3395

https://doi.org/10.1145/3580305.3599323

Published: 04 August 2023 Publication History

Abstract

Given a graph \mathcalG, the spanning centrality (SC) of an edge e measures the importance of e for \mathcalG to be connected. In practice, SC has seen extensive applications in computational biology, electrical networks, and combinatorial optimization. However, it is highly challenging to compute the SC of all edges (AESC) on large graphs. Existing techniques fail to deal with such graphs, as they either suffer from expensive matrix operations or require sampling numerous long random walks. To circumvent these issues, this paper proposes TGT and its enhanced version TGT+, two algorithms for AESC computation that offers rigorous theoretical approximation guarantees. In particular, TGT remedies the deficiencies of previous solutions by conducting deterministic graph traversals with carefully-crafted truncated lengths. TGT+ further advances TGT in terms of both empirical efficiency and asymptotic performance while retaining result quality, based on the combination of TGT with random walks and several additional heuristic optimizations. We experimentally evaluate TGT+ against recent competitors for AESC using a variety of real datasets. The experimental outcomes authenticate that TGT+ outperforms state of the arts often by over one order of magnitude speedup without degrading the accuracy.

Supplementary Material

MP4 File (rtfp0571-2min-promo.mp4)

Promotional video

Download
2.85 MB

References

[1]

Dimitris Achlioptas. 2001. Database-friendly random projections. In PODS. 274--281.

[2]

Reid Andersen, Fan Chung, and Kevin Lang. 2006. Local graph partitioning using pagerank vectors. In FOCS. 475--486.

[3]

Andrey Bernstein, Daniel Bienstock, David Hay, Meric Uzunoglu, and Gil Zussman. 2014. Power grid vulnerability to geographically correlated failures-Analysis and control implications. In INFOCOM. 2634--2642.

[4]

Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng. 2011. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In STOC. 273--282.

[5]

Alfredo Cuzzocrea, Alexis Papadimitriou, Dimitrios Katsaros, and Yannis Manolopoulos. 2012. Edge betweenness centrality: A novel algorithm for QoS-based topology control over wireless sensor networks. Journal of Network and Computer Applications, Vol. 35, 4 (2012), 1210--1217.

Digital Library

[6]

Peter G Doyle and J Laurie Snell. 1984. Random walks and electric networks. Vol. 22. American Mathematical Soc.

[7]

Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás Sarlós. 2005. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Math., Vol. 2, 3 (2005), 333--358.

[8]

Francois Fouss, Alain Pirotte, Jean-Michel Renders, and Marco Saerens. 2007. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. TKDE, Vol. 19, 3 (2007), 355--369.

Digital Library

[9]

Linton C Freeman. 1977. A set of measures of centrality based on betweenness. Sociometry (1977), 35--41.

[10]

Arpita Ghosh, Stephen Boyd, and Amin Saberi. 2008. Minimizing effective resistance of a graph. SIAM review, Vol. 50, 1 (2008), 37--66.

[11]

Michelle Girvan and Mark EJ Newman. 2002. Community structure in social and biological networks. PNAS, Vol. 99, 12 (2002), 7821--7826.

[12]

Linqi Guo, Chen Liang, and Steven H Low. 2017. Monotonicity properties and spectral characterization of power redistribution in cascading failures. SIGMETRICS, Vol. 45, 2 (2017), 103--106.

Digital Library

[13]

John M Harris, Jeffry L Hirst, and Michael J Mossinghoff. 2000. Combinatorics and graph theory. Springer Science & Business Media.

[14]

Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. 2016. Efficient Algorithms for Spanning Tree Centrality. In IJCAI, Vol. 16. 3733--3739.

[15]

Wassily Hoeffding. 1963. Probability Inequalities for Sums of Bounded Random Variables. J. Amer. Statist. Assoc., Vol. 58, 301 (1963), 13--30.

[16]

Guanhao Hou, Xingguang Chen, Sibo Wang, and Zhewei Wei. 2021. Massively parallel algorithms for personalized PageRank. PVLDB, Vol. 14, 9 (2021), 1668--1680.

Digital Library

[17]

Arun Jambulapati and Aaron Sidford. 2018. Efficient O$(n/ε)$ Spectral Sketches for the Laplacian and its Pseudoinverse. In SODA. 2487--2503.

[18]

Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2014. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In SODA. 217--226.

Digital Library

[19]

Richard B Lehoucq, Danny C Sorensen, and Chao Yang. 1998. ARPACK users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM.

[20]

Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: densification laws, shrinking diameters and possible explanations. In SIGKDD. 177--187.

[21]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.

[22]

Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, Vol. 6, 1 (2009), 29--123.

[23]

Dandan Lin, Raymond Chi-Wing Wong, Min Xie, and Victor Junqiu Wei. 2020. Index-free approach with theoretical guarantee for efficient random walk with restart query. In ICDE. 913--924.

[24]

Wenqing Lin. 2019. Distributed algorithms for fully personalized pagerank on large graphs. In WWW. 1084--1094.

[25]

Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. 2016. Personalized pagerank estimation and search: A bidirectional approach. In WSDM. 163--172.

[26]

Peter Lofgren and Ashish Goel. 2013. Personalized pagerank to a target node. arXiv (2013).

[27]

Siqiang Luo, Xiaokui Xiao, Wenqing Lin, and Ben Kao. 2019a. Baton: Batch one-hop personalized pageranks with efficiency and accuracy. TKDE, Vol. 32, 10 (2019), 1897--1908.

[28]

Siqiang Luo, Xiaokui Xiao, Wenqing Lin, and Ben Kao. 2019b. Efficient batch one-hop personalized pageranks. In ICDE. 1562--1565.

[29]

Charalampos Mavroforakis, Richard Garcia-Lebron, Ioannis Koutis, and Evimaria Terzi. 2015. Spanning edge centrality: Large-scale computation and applications. In WWW. 732--742.

[30]

Julian J McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks. In NeurIPS. 548--56.

[31]

Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized algorithms. Cambridge University Press.

Digital Library

[32]

Mark EJ Newman and Michelle Girvan. 2004. Finding and evaluating community structure in networks. Physical review E, Vol. 69, 2 (2004), 026113.

[33]

Beresford N Parlett. 1998. The symmetric eigenvalue problem. SIAM.

[34]

Pan Peng, Daniel Lopatta, Yuichi Yoshida, and Gramoz Goranci. 2021. Local Algorithms for Estimating Effective Resistance. In SIGKDD. 1329--1338.

[35]

Benedek Rozemberczki and Rik Sarkar. 2021. Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings. arxiv: 2101.03091 [cs.SI]

[36]

Gerta Rücker. 2012. Network meta-analysis, electrical networks and graph theory. Research synthesis methods, Vol. 3, 4 (2012), 312--324.

[37]

Jan Scheurer and Sergio Porta. 2006. Centrality and connectivity in public transport networks and their significance for transport sustainability in cities. In World Planning Schools Congress, Global Planning Association Education Network.

[38]

Jieming Shi, Renchi Yang, Tianyuan Jin, Xiaokui Xiao, and Yin Yang. 2019. Realtime top-k personalized pagerank over large graphs on gpus. PVLDB, Vol. 13, 1 (2019), 15--28.

Digital Library

[39]

Daniel A Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. In STOC. 563--568.

[40]

Andreia Sofia Teixeira, Pedro T Monteiro, Jo ao A Carricc o, Mário Ramirez, and Alexandre P Francisco. 2013. Spanning edge betweenness. In MLG, Vol. 24. 27--31.

[41]

Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. 2006. Fast random walk with restart and its applications. In ICDM. 613--622.

[42]

William Thomas Tutte and William Thomas Tutte. 2001. Graph theory. Vol. 21. Cambridge university press.

[43]

Hanzhi Wang, Zhewei Wei, Junhao Gan, Sibo Wang, and Zengfeng Huang. 2020. Personalized PageRank to a Target Node, Revisited. In SIGKDD. 657--667.

[44]

Sibo Wang, Youze Tang, Xiaokui Xiao, Yin Yang, and Zengxiang Li. 2016. HubPPR: effective indexing for approximate personalized pagerank. PVLDB, Vol. 10, 3 (2016), 205--216.

Digital Library

[45]

Sibo Wang, Renchi Yang, Runhui Wang, Xiaokui Xiao, Zhewei Wei, Wenqing Lin, Yin Yang, and Nan Tang. 2019. Efficient algorithms for approximate single-source personalized pagerank queries. TODS, Vol. 44, 4 (2019), 1--37.

Digital Library

[46]

Sibo Wang, Renchi Yang, Xiaokui Xiao, Zhewei Wei, and Yin Yang. 2017. FORA: simple and effective approximate single-source personalized pagerank. In SIGKDD. 505--514.

[47]

EL Wilmer, David A Levin, and Yuval Peres. 2009. Markov chains and mixing times. American Mathematical Soc., Providence (2009).

[48]

David Bruce Wilson. 1996. Generating random spanning trees more quickly than the cover time. In STOC. 296--303.

[49]

Hao Wu, Junhao Gan, Zhewei Wei, and Rui Zhang. 2021. Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push. In SIGMOD. 1996--2008.

[50]

Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities Based on Ground-Truth. In ICDM. 745--754.

[51]

Shiqi Zhang, Renchi Yang, Jing Tang, Xiaokui Xiao, and Bo Tang. 2023. Efficient Approximation Algorithms for Spanning Centrality. arxiv: 2305.16086io

Cited By

Xia HZhang Z(2024)Efficient Approximation of Kemeny's Constant for Large GraphsProceedings of the ACM on Management of Data10.1145/36549372:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654937
Liao MZhou JLi RDai QChen HWang G(2024)Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based ApproachProceedings of the ACM on Management of Data10.1145/36549362:3(1-27)Online publication date: 30-May-2024
https://doi.org/10.1145/3654936

Index Terms

Efficient Approximation Algorithms for Spanning Centrality
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Approximation algorithms
      2. Graph algorithms
  2. Probability and statistics
    1. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods

Recommendations

Efficient algorithms for spanning tree centrality
IJCAI'16: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence

In a connected graph, spanning tree centralities of a vertex and an edge measure how crucial they are for the graph to be connected. In this paper, we propose efficient algorithms for estimating spanning tree centralities with theoretical guarantees on ...
An improved approximation algorithm for spanning star forest in dense graphs
COCOA'10: Proceedings of the 4th international conference on Combinatorial optimization and applications - Volume Part II

A spanning subgraph of a given graph G is called a spanning star forest of G if it is a collection of node-disjoint trees of depth at most 1 (such trees are called stars). The size of a spanning star forest is the number of leaves in all its components. ...
Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs

Let G be a graph in which each vertex v has a positive integer weight b ( v ) and each edge ( v , w ) has a nonnegative integer weight b ( v , w ) . A bandwidth consecutive multicoloring, simply called a b-coloring of G, assigns each vertex v a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 2023

5996 pages

ISBN:9798400701030

DOI:10.1145/3580305

General Chairs:
Ambuj Singh
UC Santa Barbara, USA
,
Yizhou Sun
UC Los Angeles, USA
,
Program Chairs:
Leman Akoglu
Carnegie Mellon University, USA
,
Dimitrios Gunopulos
University of Athens, Greece
,
Xifeng Yan
UC Santa Barbara, USA
,
Ravi Kumar
Google, USA
,
Fatma Ozcan
Google, USA
,
Jieping Ye
Alibaba DAMO Academy

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 August 2023

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China
Guangzhou Municipal Science and Technology Bureau
Shenzhen Fundamental Research Program

Conference

KDD '23

Sponsor:

KDD '23: The 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 6 - 10, 2023

CA, Long Beach, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
430
Total Downloads

Downloads (Last 12 months)388
Downloads (Last 6 weeks)37

Reflects downloads up to 19 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xia HZhang Z(2024)Efficient Approximation of Kemeny's Constant for Large GraphsProceedings of the ACM on Management of Data10.1145/36549372:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654937
Liao MZhou JLi RDai QChen HWang G(2024)Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based ApproachProceedings of the ACM on Management of Data10.1145/36549362:3(1-27)Online publication date: 30-May-2024
https://doi.org/10.1145/3654936

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents