RWE: A Random Walk Based Graph Entropy for the Structural Complexity of Directed Networks
文献类型：期刊论文
| 作者 | Zhang, Chong1; Deng, Cheng2; Fu, Luoyi2; Wang, Xinbing2; Chen, Guihai2; Zhou, Lei3; Zhou, Chenghu4 |
| 刊名 | IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
 |
| 出版日期 | 2024-03-01 |
| 卷号 | 11期号:2页码:2264-2278 |
| 关键词 | Entropy Complexity theory Laplace equations Directed graphs Receivers Social networking (online) Extraterrestrial measurements Directed graph graph entropy random walk structural complexity von Neumann entropy |
| ISSN号 | 2327-4697 |
| DOI | 10.1109/TNSE.2023.3342197 |
| 通讯作者 | Wang, Xinbing(xwang8@sjtu.edu.cn) |
| 英文摘要 | This paper studies a graph entropy measure to characterize the structural complexity of directed networks. Since the von Neumann entropy (VNE) has found applications in many tasks by networked data, but suffers from a high computational complexity in computing the Laplacian spectrum, we aim to propose a simple yet effective alternative method. Considering that local nodal interactions collectively induce the information flow of the entire graph, we are motivated to use the probability flow of random walks as the proxy of information flow in real-world digraphs, and correspondingly propose a random walk based entropy (RWE) to measure the average information that the random walker reaches each node. Inspired by the close relation between Laplacian spectrum and the Perron vector, we prove that RWE serves as a good approximation for the VNE in digraphs with a guaranteed entropy gap. This approximation is further applied to a digraph similarity measure based on the Jensen-Shannon divergence. Therefore, RWE exhibits interpretability, scalability and capability of well capturing the structural complexity of digraphs as empirically verified. We further extend RWE to two dimensions by incorporating community structures, which characterizes information flow both between and within communities. By proving that the difference between the one-dimensional and two-dimensional RWE reflects the extent to which the community structure is preserved, we convert the community detection problem into the minimization of two-dimensional RWE, and design a greedy algorithm. Various experiments confirm the superiority of our approach over the baselines. |
| WOS关键词 | SEARCH |
| 资助项目 | National Key Ramp;D Program of China |
| WOS研究方向 | Engineering ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:001175221000006 |
| 出版者 | IEEE COMPUTER SOC |
| 资助机构 | National Key Ramp;D Program of China |
| 源URL | [http://ir.igsnrr.ac.cn/handle/311030/204140]  |
| 专题 | 中国科学院地理科学与资源研究所 |
| 通讯作者 | Wang, Xinbing |
| 作者单位 | 1.Xi An Jiao Tong Univ, Sch Comp Sci & Technol, Xian 710049, Shaanxi, Peoples R China 2.Shanghai Jiao Tong Univ, Sch Elect Informat & Elect Engn, Shanghai 200240, Peoples R China 3.Shanghai Jiao Tong Univ, Sch Oceanog, Shanghai 200240, Peoples R China 4.Chinese Acad Sci, Inst Geog Sci & Nat Resources Res, State Key Lab Resources & Environm Informat Syst, Beijing 100045, Peoples R China |
| 推荐引用方式 GB/T 7714 | Zhang, Chong,Deng, Cheng,Fu, Luoyi,et al. RWE: A Random Walk Based Graph Entropy for the Structural Complexity of Directed Networks[J]. IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING,2024,11(2):2264-2278. |
| APA | Zhang, Chong.,Deng, Cheng.,Fu, Luoyi.,Wang, Xinbing.,Chen, Guihai.,...&Zhou, Chenghu.(2024).RWE: A Random Walk Based Graph Entropy for the Structural Complexity of Directed Networks.IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING,11(2),2264-2278. |
| MLA | Zhang, Chong,et al."RWE: A Random Walk Based Graph Entropy for the Structural Complexity of Directed Networks".IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 11.2(2024):2264-2278. |
入库方式： OAI收割
来源：地理科学与资源研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。