Node ranking based on graph curvature and PageRank

doi:10.1088/1674-1056/ad9a9b

中国物理B ›› 2025, Vol. 34 ›› Issue (2): 28901-028901.doi: 10.1088/1674-1056/ad9a9b

Node ranking based on graph curvature and PageRank

Hongbo Qu(曲鸿博)¹, Yu-Rong Song(宋玉蓉)^2,†, Ruqi Li(李汝琦)¹, Min Li(李敏)², and Guo-Ping Jiang(蒋国平)²

1 School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;
2 College of Automation & College of Artificial Intelligence, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

收稿日期:2024-09-30 修回日期:2024-11-16 接受日期:2024-12-05 出版日期:2025-02-15 发布日期:2025-01-15
通讯作者: Yu-Rong Song E-mail:songyr@njupt.edu.cn
基金资助:
Project partially supported by the National Natural Science Foundation of China (Grant Nos. 61672298 and 62373197), the Major Project of Philosophy and Social Science Research in Colleges and Universities in Jiangsu Province, China (Grant No. 2018SJZDI142), and the Postgraduate Research & Practice Innovation Program of Jiangsu Province, China (Grant No. KYCX23 1045).

Node ranking based on graph curvature and PageRank

Hongbo Qu(曲鸿博)¹, Yu-Rong Song(宋玉蓉)^2,†, Ruqi Li(李汝琦)¹, Min Li(李敏)², and Guo-Ping Jiang(蒋国平)²

1 School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;
2 College of Automation & College of Artificial Intelligence, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

Received:2024-09-30 Revised:2024-11-16 Accepted:2024-12-05 Online:2025-02-15 Published:2025-01-15
Contact: Yu-Rong Song E-mail:songyr@njupt.edu.cn
Supported by:
Project partially supported by the National Natural Science Foundation of China (Grant Nos. 61672298 and 62373197), the Major Project of Philosophy and Social Science Research in Colleges and Universities in Jiangsu Province, China (Grant No. 2018SJZDI142), and the Postgraduate Research & Practice Innovation Program of Jiangsu Province, China (Grant No. KYCX23 1045).

摘要/Abstract

摘要： Identifying key nodes in complex networks is crucial for understanding and controlling their dynamics. Traditional centrality measures often fall short in capturing the multifaceted roles of nodes within these networks. The PageRank algorithm, widely recognized for ranking web pages, offers a more nuanced approach by considering the importance of connected nodes. However, existing methods generally overlook the geometric properties of networks, which can provide additional insights into their structure and functionality. In this paper, we propose a novel method named Curv-PageRank (C-PR), which integrates network curvature and PageRank to identify influential nodes in complex networks. By leveraging the geometric insights provided by curvature alongside structural properties, C-PR offers a more comprehensive measure of a node's influence. Our approach is particularly effective in networks with community structures, where it excels at pinpointing bridge nodes critical for maintaining connectivity and facilitating information flow. We validate the effectiveness of C-PR through extensive experiments. The results demonstrate that C-PR outperforms traditional centrality-based and PageRank methods in identifying critical nodes. Our findings offer fresh insights into the structural importance of nodes across diverse network configurations, highlighting the potential of incorporating geometric properties into network analysis.

关键词: important nodes, graph curvature, complex networks, network geometry

Abstract: Identifying key nodes in complex networks is crucial for understanding and controlling their dynamics. Traditional centrality measures often fall short in capturing the multifaceted roles of nodes within these networks. The PageRank algorithm, widely recognized for ranking web pages, offers a more nuanced approach by considering the importance of connected nodes. However, existing methods generally overlook the geometric properties of networks, which can provide additional insights into their structure and functionality. In this paper, we propose a novel method named Curv-PageRank (C-PR), which integrates network curvature and PageRank to identify influential nodes in complex networks. By leveraging the geometric insights provided by curvature alongside structural properties, C-PR offers a more comprehensive measure of a node's influence. Our approach is particularly effective in networks with community structures, where it excels at pinpointing bridge nodes critical for maintaining connectivity and facilitating information flow. We validate the effectiveness of C-PR through extensive experiments. The results demonstrate that C-PR outperforms traditional centrality-based and PageRank methods in identifying critical nodes. Our findings offer fresh insights into the structural importance of nodes across diverse network configurations, highlighting the potential of incorporating geometric properties into network analysis.

Key words: important nodes, graph curvature, complex networks, network geometry

中图分类号: (Complex systems)

89.75.-k

89.75.Fb (Structures and organization in complex systems) 02.40.-k (Geometry, differential geometry, and topology)

Hongbo Qu(曲鸿博), Yu-Rong Song(宋玉蓉), Ruqi Li(李汝琦), Min Li(李敏), and Guo-Ping Jiang(蒋国平). Node ranking based on graph curvature and PageRank[J]. 中国物理B, 2025, 34(2): 28901-028901.

Hongbo Qu(曲鸿博), Yu-Rong Song(宋玉蓉), Ruqi Li(李汝琦), Min Li(李敏), and Guo-Ping Jiang(蒋国平). Node ranking based on graph curvature and PageRank[J]. Chin. Phys. B, 2025, 34(2): 28901-028901.

参考文献

[1] Artime O, Grassia M, DeDomenico M, Gleeson J P, Makse H A, Mangioni G, Perc M and Radicchi F 2024 Nat. Rev. Phys. 6 114
[2] Liu X M, Li D Q, Ma M Q, Szymanski B K, Stanley H E and Gao J X 2022 Phys. Rep. 971 1
[3] Watts D J and Strogatz S H 1998 Nature 393 440
[4] Newman M E 2002 Phys. Rev. E 66 016128
[5] Albert R, Albert I and Nakarado G L 2004 Phys. Rev. E 69 025103
[6] Bonacich P 1972 J. Math. Sociol. 2 113
[7] Brandes U 2001 J. Math. Sociol. 25 163
[8] Freeman L C, et al. 2002 Soc. Netw. 1 215
[9] Page L, Brin S, Motwani R and Winograd T Tech. Rep. 1999 66
[10] Lu L Y, Zhang Y C, Yeung C H and Zhou T 2011 PLoS One 6 e21202
[11] Boguna M, Bonamassa I, DeDomenico M, Havlin S, Krioukov D and Serrano M Á 2021 Nat. Rev. Phys. 3 114
[12] Mulder D and Bianconi G 2018 J. Stat. Phys. 173 783
[13] Lin Y, Lu L Y and Yau S T 2011 Tohoku Math. J. 63 605
[14] Ollivier Y 2009 J. Funct. Anal. 256 810
[15] DoCarmo M P and FlahertyFrancis J 1992 Riemannian geometry (Boston: Birkhäuser) p. 10
[16] Ollivier Y 2010 Adv. Stud. Pure Math. 57 343
[17] Wandelt S, Shi X, Sun X Q and Zanin M 2020 IEEE Access 8 111954
[18] Bedi P and Sharma C 2016 Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 6 115
[19] Barrio-Hernandez I, Schwartzentruber J, Shrivastava A, Del-Toro N, Gonzalez A, Zhang Q, Mountjoy E, Suveges D, Ochoa D, Ghoussaini M, Bradley G, Hermjakob H, Orchard S, Dunham I, Anderson C, Porras P and Beltrao P 2023 Nat. Genet. 55 389
[20] Heidemann J, Klier M and Probst F 2010 Proceedings of the International Conference on Information Systems, December 12-15, 2010, St. Louis, Missouri, USA, p. 79
[21] Nguyen P, Tomeo P, DiNoia T and DiSciascio E 2015 Proceedingsof the 24th International Conference on World Wide Web, May 18-22, 2015, Florence, Italy, p. 1477
[22] Morrison J L, Breitling R, Higham D J and Gilbert D R 2005 BMC Bioinformatics 6 233
[23] Monge G 1781 Mem. Math. Phys. Acad. Royale Sci. 1 666
[24] Galichon A 2018 Optimal transport methods in economics (Princeton: Princeton University Press) p.96
[25] Peyré G and Cuturi M 2019 Found. Trends Mach. Learn. 11 355
[26] Carmi S, Havlin S, Kirkpatrick S, Shavitt Y and Shir E 2007 Proc. Natl. Acad. Sci. USA 104 11150
[27] Fan C J, Zeng L, Sun Y Z and Liu Y Y 2020 Nat. Mach. Intell. 2 317
[28] Barabási A L and Albert R 1999 Science 286 509
[29] Lancichinetti A, Fortunato S and Radicchi F 2008 Phys. Rev. E 78 046110
[30] Watts D J 1999 Am. J. Sociol. 105 493
[31] Zachary W W 1977 J. Anthropol. Res. 33 452
[32] Lusseau D and Newman M E 2004 Proc. R. Soc. Lond. B Biol. Sci. 271 S477
[33] Leskovec J and Sosič R 2016 ACM Trans. Intell. Syst. Technol. 8 1
[34] Yang Z L, Cohen W and Salakhudinov R 2016 Proceedings of the 33rd International Conference on Machine Learning, June 19-24, New York, USA, p. 40
[35] Boguná M, Pastor-Satorras R, Díaz-Guilera A and Arenas A 2004 Phys. Rev. E 70 056122
[36] Clauset A, Newman M E and Moore C 2004 Phys. Rev. E 70 066111
[37] Cordasco G and Gargano L 2010 Proceedings of the IEEE International Workshop on Business Applications of Social Network Analysis, December 15, 2010, Bangalore, India, p. 1
[38] Pastor-Satorras R and Vespignani A 2001 Phys. Rev. Lett. 86 3200
[39] Rossi R A and Ahmed N K 2015 Proceedings of the AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas USA, p. 4292

Metrics

Viewed

Full text

103

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	0	0	103

来源	本网站	其他网站

次数	98	5
比例	95%	5%

Abstract

173

最新录用	在线预览	正式出版

0	0	173

	来源	本网站

	次数	173
	比例	100%

Cited

Web of Science	Crossref	ScienceDirect	Search for Citations in Google Scholar >>


This page requires you have already subscribed to WoS.

Shared

Node ranking based on graph curvature and PageRank

Node ranking based on graph curvature and PageRank

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Peng Yang(杨鹏), Ruguo Fan(范如国), Yibo Wang(王奕博), and Yingqing Zhang(张应青). Dynamic analysis of major public health emergency transmission considering the dual-layer coupling of community-resident complex networks[J]. 中国物理B, 2024, 33(7): 70206-070206.
[2]	Dongli Duan(段东立), Feifei Bi(毕菲菲), Sifan Li(李思凡), Chengxing Wu(吴成星), Changchun Lv(吕长春), and Zhiqiang Cai(蔡志强). Prediction of collapse process and tipping points for mutualistic and competitive networks with k-core method[J]. 中国物理B, 2024, 33(5): 50201-050201.
[3]	Fu-Zhong Nian(年福忠) and Yu Yang(杨宇). Effects of individual heterogeneity on social contagions[J]. 中国物理B, 2024, 33(5): 58705-058705.
[4]	Zhan Su(苏湛), Lei Chen(陈磊), Jun Ai(艾均), Yu-Yu Zheng(郑雨语), and Na Bie(别娜). Identifying influential spreaders in complex networks based on density entropy and community structure[J]. 中国物理B, 2024, 33(5): 58901-058901.
[5]	Yiwei Huang(黄羿炜), Shuqi Xu(徐舒琪), Shimin Cai(蔡世民), and Linyuan Lü(吕琳媛). A multilayer network diffusion-based model for reviewer recommendation[J]. 中国物理B, 2024, 33(3): 38901-038901.
[6]	Zhi-Wei Ma(马志伟), Lei Sun(孙蕾), Zhi-Guo Ding(丁智国), Yi-Zhen Huang(黄宜真), and Zhao-Long Hu(胡兆龙). Source localization in signed networks with effective distance[J]. 中国物理B, 2024, 33(2): 28902-028902.
[7]	Yuan-Zhang Deng(邓元璋), Zhao-Long Hu(胡兆龙), Feilong Lin(林飞龙), Chang-Bing Tang(唐长兵), Hui Wang(王晖), and Yi-Zhen Huang(黄宜真). Identify information sources with different start times in complex networks based on sparse observers[J]. 中国物理B, 2024, 33(11): 118901-118901.
[8]	Jia-Hui Song(宋家辉). Important edge identification in complex networks based on local and global features[J]. 中国物理B, 2023, 32(9): 98901-098901.
[9]	Dan Chen(陈单), Defu Cai(蔡德福), and Housheng Su(苏厚胜). Self-similarity of complex networks under centrality-based node removal strategy[J]. 中国物理B, 2023, 32(9): 98903-098903.
[10]	Yun Zhai(翟云), Xuan Wang(王璇), Jinghua Xiao(肖井华), and Zhigang Zheng(郑志刚). Stability and multistability of synchronization in networks of coupled phase oscillators[J]. 中国物理B, 2023, 32(6): 60503-060503.
[11]	Zijian Yan(严子健), Yongxiang Xia(夏永祥), Lijun Guo(郭丽君), Lingzhe Zhu(祝令哲), Yuanyuan Liang(梁圆圆), and Haicheng Tu(涂海程). Identification of key recovering node for spatial networks[J]. 中国物理B, 2023, 32(6): 68901-068901.
[12]	Peishi Yang(杨培实), Pengli Lu(卢鹏丽), and Teng Zhang(张腾). AG-GATCN: A novel method for predicting essential proteins[J]. 中国物理B, 2023, 32(5): 58902-058902.
[13]	Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Analysis of cut vertex in the control of complex networks[J]. 中国物理B, 2023, 32(2): 28902-028902.
[14]	Da Ai(艾达), Xin-Long Liu(刘鑫龙), Wen-Zhe Kang(康文哲), Lin-Na Li(李琳娜), Shao-Qing Lü(吕少卿), and Ying Liu(刘颖). SLGC: Identifying influential nodes in complex networks from the perspectives of self-centrality, local centrality, and global centrality[J]. 中国物理B, 2023, 32(11): 118902-118902.
[15]	Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding[J]. 中国物理B, 2023, 32(1): 18903-018903.