A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node Identification
Identifying influential nodes in complex networks is essential for a wide range of applications, from social network analysis to enhancing infrastructure resilience. While quantum walk-based methods offer potential advantages, existing approaches face challenges in dimensionality, computational effi...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-06-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/27/6/634 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850167998552211456 |
|---|---|
| author | Wen Liang Yifan Wang Qiwei Liu Wenbo Zhang |
| author_facet | Wen Liang Yifan Wang Qiwei Liu Wenbo Zhang |
| author_sort | Wen Liang |
| collection | DOAJ |
| description | Identifying influential nodes in complex networks is essential for a wide range of applications, from social network analysis to enhancing infrastructure resilience. While quantum walk-based methods offer potential advantages, existing approaches face challenges in dimensionality, computational efficiency, and accuracy. To address these limitations, this study proposes a novel method inspired by the one-dimensional discrete-time quantum walk (IOQW). This design enables the development of a simplified shift operator that leverages both self-loops and the network’s structural connectivity. Furthermore, degree centrality and path-based features are integrated into the coin operator, enhancing the accuracy and scalability of the IOQW framework. Comparative evaluations against state-of-the-art quantum and classical methods demonstrate that IOQW excels in capturing both local and global topological properties while maintaining a low computational complexity of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>N</mi><mo>⟨</mo><mi>k</mi><mo>⟩</mo><mo>)</mo></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>⟨</mo><mi>k</mi><mo>⟩</mo></mrow></semantics></math></inline-formula> denotes the average degree. These advancements establish IOQW as a powerful and practical tool for influential node identification in complex networks, bridging quantum-inspired techniques with real-world network science applications. |
| format | Article |
| id | doaj-art-d8a61d94880242289fcad87390e043b7 |
| institution | OA Journals |
| issn | 1099-4300 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj-art-d8a61d94880242289fcad87390e043b72025-08-20T02:21:06ZengMDPI AGEntropy1099-43002025-06-0127663410.3390/e27060634A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node IdentificationWen Liang0Yifan Wang1Qiwei Liu2Wenbo Zhang3College of Information Science and Engineering, Shenyang Ligong University, Shenyang 110159, ChinaCollege of Information Science and Engineering, Shenyang Ligong University, Shenyang 110159, ChinaSchool of Public Administration and Policy, Dalian University of Technology, Dalian 116081, ChinaCollege of Information Science and Engineering, Shenyang Ligong University, Shenyang 110159, ChinaIdentifying influential nodes in complex networks is essential for a wide range of applications, from social network analysis to enhancing infrastructure resilience. While quantum walk-based methods offer potential advantages, existing approaches face challenges in dimensionality, computational efficiency, and accuracy. To address these limitations, this study proposes a novel method inspired by the one-dimensional discrete-time quantum walk (IOQW). This design enables the development of a simplified shift operator that leverages both self-loops and the network’s structural connectivity. Furthermore, degree centrality and path-based features are integrated into the coin operator, enhancing the accuracy and scalability of the IOQW framework. Comparative evaluations against state-of-the-art quantum and classical methods demonstrate that IOQW excels in capturing both local and global topological properties while maintaining a low computational complexity of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>N</mi><mo>⟨</mo><mi>k</mi><mo>⟩</mo><mo>)</mo></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>⟨</mo><mi>k</mi><mo>⟩</mo></mrow></semantics></math></inline-formula> denotes the average degree. These advancements establish IOQW as a powerful and practical tool for influential node identification in complex networks, bridging quantum-inspired techniques with real-world network science applications.https://www.mdpi.com/1099-4300/27/6/634complex networksinfluential nodesquantum computingquantum walks |
| spellingShingle | Wen Liang Yifan Wang Qiwei Liu Wenbo Zhang A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node Identification Entropy complex networks influential nodes quantum computing quantum walks |
| title | A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node Identification |
| title_full | A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node Identification |
| title_fullStr | A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node Identification |
| title_full_unstemmed | A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node Identification |
| title_short | A Method Inspired by One-Dimensional Discrete-Time Quantum Walks for Influential Node Identification |
| title_sort | method inspired by one dimensional discrete time quantum walks for influential node identification |
| topic | complex networks influential nodes quantum computing quantum walks |
| url | https://www.mdpi.com/1099-4300/27/6/634 |
| work_keys_str_mv | AT wenliang amethodinspiredbyonedimensionaldiscretetimequantumwalksforinfluentialnodeidentification AT yifanwang amethodinspiredbyonedimensionaldiscretetimequantumwalksforinfluentialnodeidentification AT qiweiliu amethodinspiredbyonedimensionaldiscretetimequantumwalksforinfluentialnodeidentification AT wenbozhang amethodinspiredbyonedimensionaldiscretetimequantumwalksforinfluentialnodeidentification AT wenliang methodinspiredbyonedimensionaldiscretetimequantumwalksforinfluentialnodeidentification AT yifanwang methodinspiredbyonedimensionaldiscretetimequantumwalksforinfluentialnodeidentification AT qiweiliu methodinspiredbyonedimensionaldiscretetimequantumwalksforinfluentialnodeidentification AT wenbozhang methodinspiredbyonedimensionaldiscretetimequantumwalksforinfluentialnodeidentification |