TY - JOUR

T1 - Structural position vectors and symmetries in complex networks

AU - Long, Yong Shang

AU - Zhai, Zheng Meng

AU - Tang, Ming

AU - Liu, Ying

AU - Lai, Ying Cheng

N1 - Funding Information: This work was supported by the National Ten Thousand Talents Plan Youth Top Talent project, the National Natural Science Foundation of China (Grant Nos. 82161148012, 11975099, and 61802321), and the Science and Technology Commission of Shanghai Municipality (Grant No. 14DZ2260800). The work at Arizona State University was supported by the Office of Naval Research through Grant No. N00014-21-1-2323. Publisher Copyright: © 2022 Author(s).

PY - 2022/9/1

Y1 - 2022/9/1

N2 - Symmetries, due to their fundamental importance to dynamical processes on networks, have attracted a great deal of current research. Finding all symmetric nodes in large complex networks typically relies on automorphism groups from algebraic-group theory, which are solvable in quasipolynomial time. We articulate a conceptually appealing and computationally extremely efficient approach to finding and characterizing all symmetric nodes by introducing a structural position vector (SPV) for each node in networks. We establish the mathematical result that symmetric nodes must have the same SPV value and demonstrate, using six representative complex networks from the real world, that all symmetric nodes in these networks can be found in linear time. Furthermore, the SPVs not only characterize the similarity of nodes but also quantify the nodal influences in propagation dynamics. A caveat is that the proved mathematical result relating the SPV values to nodal symmetries is not sufficient; i.e., nodes having the same SPV values may not be symmetric, which arises in regular networks or networks with a dominant regular component. We point out with an analysis that this caveat is, in fact, shared by the known existing approaches to finding symmetric nodes in the literature. We further argue, with the aid of a mathematical analysis, that our SPV method is generally effective for finding the symmetric nodes in real-world networks that typically do not have a dominant regular component. Our SPV-based framework, therefore, provides a physically intuitive and computationally efficient way to uncover, understand, and exploit symmetric structures in complex networks arising from real-world applications.

AB - Symmetries, due to their fundamental importance to dynamical processes on networks, have attracted a great deal of current research. Finding all symmetric nodes in large complex networks typically relies on automorphism groups from algebraic-group theory, which are solvable in quasipolynomial time. We articulate a conceptually appealing and computationally extremely efficient approach to finding and characterizing all symmetric nodes by introducing a structural position vector (SPV) for each node in networks. We establish the mathematical result that symmetric nodes must have the same SPV value and demonstrate, using six representative complex networks from the real world, that all symmetric nodes in these networks can be found in linear time. Furthermore, the SPVs not only characterize the similarity of nodes but also quantify the nodal influences in propagation dynamics. A caveat is that the proved mathematical result relating the SPV values to nodal symmetries is not sufficient; i.e., nodes having the same SPV values may not be symmetric, which arises in regular networks or networks with a dominant regular component. We point out with an analysis that this caveat is, in fact, shared by the known existing approaches to finding symmetric nodes in the literature. We further argue, with the aid of a mathematical analysis, that our SPV method is generally effective for finding the symmetric nodes in real-world networks that typically do not have a dominant regular component. Our SPV-based framework, therefore, provides a physically intuitive and computationally efficient way to uncover, understand, and exploit symmetric structures in complex networks arising from real-world applications.

UR - http://www.scopus.com/inward/record.url?scp=85139142135&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85139142135&partnerID=8YFLogxK

U2 - 10.1063/5.0107583

DO - 10.1063/5.0107583

M3 - Article

C2 - 36182361

SN - 1054-1500

VL - 32

JO - Chaos

JF - Chaos

IS - 9

M1 - 093132

ER -