Dissimilarity-based filtering and compression of complex weighted networks

School of Systems Science, Beijing Normal University - Beijing 100875, China and Beijing Normal University - Zhuhai 519000, China

^(a) zdi@bnu.edu.cn (corresponding author)

Received: 5 September 2021
Accepted: 20 July 2022

Abstract

As a classical problem, network filtering or compression, obtaining a subgraph by removing certain nodes and edges in the network, has great significance in revealing the important information under the complex network. Some present filtering approaches adopting local properties usually use limited or incomplete network information, resulting in missing or underestimating a lot of information in the network. In this paper, we propose a new network filtering and compression algorithm based on network similarity. This algorithm aims at finding a subnetwork with the minimum dissimilarity from the original one. In the meantime, it will retain comprehensively structural and functional information of the original network as much as possible. In detail, we use a simulated annealing algorithm to find an optimal solution of the above minimum problem. Compared with several existing network filtering algorithms on synthetic and real-world networks, the results show that our method can retain the properties better, especially on distance-dependent attributes and network with stronger heterogeneity.