中文版 | English
题名

Efficient Approximation Algorithms for Spanning Centrality

作者
通讯作者Xiaokui Xiao; Bo Tang
DOI
发表日期
2023
会议名称
29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)
会议录名称
会议日期
AUG 06-10, 2023
会议地点
null,Long Beach,CA
出版地
1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES
出版者
摘要
Given a graph G, the spanning centrality (SC) of an edge.. measures the importance of e for G 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.
关键词
学校署名
通讯
语种
英语
相关链接[来源记录]
收录类别
资助项目
National Natural Science Foundation of China[U22B2060]
WOS研究方向
Computer Science
WOS类目
Computer Science, Information Systems ; Computer Science, Interdisciplinary Applications ; Computer Science, Theory & Methods
WOS记录号
WOS:001118896303039
来源库
Web of Science
引用统计
成果类型会议论文
条目标识符http://sustech.caswiz.com/handle/2SGJ60CL/646919
专题南方科技大学
工学院_计算机科学与工程系
作者单位
1.National University of Singapore, Singapore
2.Southern University of Science and Technology, Hong Kong
3.Hong Kong Baptist University, Hong Kong
4.The Hong Kong University of Science and Technology (Guangzhou), China
5.The Hong Kong University of Science and Technology, Hong Kong
第一作者单位南方科技大学
通讯作者单位南方科技大学
推荐引用方式
GB/T 7714
Shiqi Zhang,Renchi Yang,Jing Tang,et al. Efficient Approximation Algorithms for Spanning Centrality[C]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2023.
条目包含的文件
条目无相关文件。
个性服务
原文链接
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
导出为Excel格式
导出为Csv格式
Altmetrics Score
谷歌学术
谷歌学术中相似的文章
[Shiqi Zhang]的文章
[Renchi Yang]的文章
[Jing Tang]的文章
百度学术
百度学术中相似的文章
[Shiqi Zhang]的文章
[Renchi Yang]的文章
[Jing Tang]的文章
必应学术
必应学术中相似的文章
[Shiqi Zhang]的文章
[Renchi Yang]的文章
[Jing Tang]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
[发表评论/异议/意见]
暂无评论

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。