Mapping network symmetries with structural position vectors
Mapping network symmetries with structural position vectors lead image
Recognizing and understanding symmetry is essential for studying physical systems, as the existence of a continuous symmetry implies the conservation of a physical quantity. The same is true in complex networks, where identifying symmetries can reveal details of the network’s structure and dynamics. Typically, this is done using methods from algebraic group theory, which solve these problems in quasipolynomial time, limiting their application in large networks.
Long et al. developed a method to identify symmetric network nodes by introducing a structural position vector (SPV), which can identify symmetric nodes in linear time and dramatically speed up calculations.
“Nodes having equal SPV values is a strong necessary condition for them being symmetric to each other,” said author Ming Tang. “In real networks, the SPV of nodes is often equal to the symmetry of nodes.”
By more quickly identifying symmetric nodes, the authors aim to make studying these networks easier for researchers. Symmetric nodes can be used to develop coarse-grained simulations, identify the evolution law of the network, and determine the network’s synchronization dynamics.
“Depicting the symmetry of nodes through statistical measures of nodes provides a new way of thinking for the study of network symmetry, which may make scholars’ research on symmetrical structures in networks more in-depth,” said Tang. “Almost all real networks can use this method.”
The researchers tested their algorithm on several real-world networks to demonstrate its efficacy. These include the social network Facebook, a biological network involving yeast, and the voting network Wiki-Vote. They plan to expand their method to reveal more of the higher-order structure of these networks, such as edge structure.
Source: “Structural position vectors and symmetries in complex networks,” by Yong-Shang Long, Zheng-Meng Zhai, Ming Tang, Ying Liu, and Ying-Cheng Lai, Chaos (2022). The article can be accessed at https://doi.org/10.1063/5.0107583 .
