A complex system is composed of many components that interact with each other. In general, the nodes of a complex network are used to represent the elements in the system, and the edges between nodes are used to represent the interactions, social system, economic system, and biological system, which are all complex systems. The dependence of nodes in systems is complex. How to mine the network structure of the complex system to help us better understand the behavior of the system has always been a research and challenging problem. This paper aims to study the problem of network structure inference under the absence of system node information–network completion. The existing research on network completion is to infer the complete network structure in the complex system from the observed information. According to the information obtained, the existing studies can be divided into three categories: one is to use rich node feature information, the second is to use observed structural information, and the third is to make inferences under the scenario in which only temporal sequence information can be observed. Most of the current research assumes that all the node information can be observed, and there is less discussion about the missing information of multiple nodes due to artificial or technical constraints. The contribution of this paper is that it proposes a data-driven, end-to-end method to solve the problem of network completion and puts forward the application of subgraph matching algorithm to the network completion method, which effectively solves the evaluation problem in network completion.
Inferring Network Structure with Unobservable Nodes from Time Series Data
- Mengyuan Chen ,
- Yan Zhang ,
- Zhang Zhang ,
- Lun Du ,
- Shuo Wang ,
- Jiang Zhang
Chaos: An Interdisciplinary Journal of Nonlinear Science | , Vol 32(1)
Network structures play important roles in social, technological, and biological systems. However, the observable nodes and connections in real cases are often incomplete or unavailable due to measurement errors, private protection issues, or other problems. Therefore, inferring the complete network structure is useful for understanding human interactions and complex dynamics. The existing studies have not fully solved the problem of inferring network structure with partial information about connections or nodes. In this paper, we tackle the problem by utilizing time-series data generated by network dynamics. We regard the network inference problem based on dynamical time series data as a problem of minimizing errors for predicting states of observable nodes and proposed a novel data-driven deep learning model called Gumbel-softmax Inference for Network (GIN) to solve the problem under incomplete information. The GIN framework includes three modules: a dynamics learner, a network generator, and an initial state generator to infer the unobservable parts of the network. We implement experiments on artificial and empirical social networks with discrete and continuous dynamics. The experiments show that our method can infer the unknown parts of the structure and the initial states of the observable nodes with up to 90% accuracy. The accuracy declines linearly with the increase of the fractions of unobservable nodes. Our framework may have wide applications where the network structure is hard to obtain and the time series data is rich.