Associated Structure Mining And Dynamic Link Prediction In Complex Networks And Their Applications

The associated structure mining and dynamic link prediction are important means of understanding complex systems.Among them,associated structure is used to represent complex system,and dynamic link prediction can predict the future network.They can also describe the structure dynamics of the system and have been widely used financial risk control anti-fraud,social relationship evolution,disease spread and other fields.To mine the associated structure,it is necessary to establish the associated relationship network to analyze the topology structure.The dynamic link prediction needs to predict the future link by modeling historical data and capturing time and topological features.Due to the characteristics of the high complexity,large amount of data,random uncertainty,it brings great difficulties to network construction and dynamic link prediction.At present,methods based on structural similarity and combining graph neural networks have made great progress.However,there are still many challenges in some application scenarios and the theoretical of the model itself:(1)The complex associated data,the large number of associated structures,and the unbalanced distribution lead to slow search,time-consuming and single mining structure for constructing the associated relationship network.(2)The temporal correlation exists in periods of different lengths,there are different link patterns between nodes.(3)The link prediction is vulnerable to adversarial attacks,and it is difficult to capture the topology change of the associated relationship network,resulting in poor stability of the model.Based on the above difficulties,this thesis firstly proposes the associated structure mining method based on Map Reduce.We utilize it to establish the associated relationship network of shipping transactions,and successfully mine three potential associated structures.Based on the construction of the associated relationship network,dynamic link prediction models based on weak association smoothing strategy and adaptive stable gating are proposed to predict the future link by learning the evolution mode of the historical network.Finally,they are used for predicting of the associated relationship network of shipping transactions and analyzing the evolution of topological attributes.The main contents are as follows:(1)Aiming at the problems of high complexity and large amount of data in associated relationship network analysis,the structure mining method based on Map Reduce is constructed.Firstly,a pedigree classification algorithm is proposed to construct an associated relationship network.By introducing a new 2-tuple list,the adjacency matrix is replaced by an array to simulate the adjacency list,and combining the path compression strategy to reduce time and space complexity of the algorithm.Secondly,a associated structure mining method is proposed to analyze the associated relationship network.By introducing a pruning strategy and sufficient and necessary conditions,the calculated structural similarity is guaranteed to be non-redundant,and the corresponding proof is given.Finally,the method is applied to the associated relationship network based on shipping transactions,successfully finding three associated structures in the network: transaction pedigree,transaction group,and structural hole.The experimental results show that the proposed method in this thesis is fast in searching,less time-consuming,and can efficiently mine the potential associated structure in the network.(2)Aiming at the problems of network dynamic change over time,weak correlation and non-stationary,the dynamic link prediction model based on weak correlation smoothing strategy is proposed to capture network dynamics and predict future links.Firstly,the spatio-temporal semi-variogram is defined to characterize the correlation between network snapshots.Then,the spatio-temporal semi-variogram is used to obtain spatio-temporal correlations from the dynamic network and help determine the hyper-parameters of the model.Secondly,based on the spatio-temporal semi-variogram,a weak correlation smoothing strategy is introduced for the continuous snapshots with large temporal semi-variation,which ensures the continuity between network snapshots and smooths the noise with weak temporal correlation.Finally,we introduce the memory cell structure which embeds GCN into the input gate of LSTM.So that GCN can directly obtain the structural features of dynamic networks and the stacked memory cell structures capture the network dynamics,further predicting the future association relationship.Experimental results show that the proposed method can guarantee the correlation of network snapshots and improve the accuracy of prediction.(3)Aiming at the vulnerability to adversarial attack and poor stability of dynamic link prediction,the dynamic link prediction model based on self-adaptive stable gating is proposed to capture network dynamics and predict future links.Firstly,the high-order topology feature of each node are introduced to capture the local topology of nodes in each network snapshot,and distinguish nodes from different network snapshots.Then,to reduce the influence of noise caused by random addition and deletion of links in the associated relationship network over time,a self-adaptive stable gating is introduced to ensure the stability of the network change,and the model is proved to be stable to the small disturbance of the network structure.Secondly,an adaptive strategy based on reinforcement learning is introduced to select a stable gating network architecture.The optimal representation of temporal and structural features of a dynamic network is learned through corresponding rewards,thereby capturing the dynamics of the network.Finally,the proposed method is applied to predict future shipping transaction network,and the predicted network is analyzed by topological properties.Experimental results show that the proposed method in this thesis guarantees the stability of the network.In this thesis,aiming at the key problems in associated structure mining and dynamic link prediction,we design a corresponding method based on big data and deep learning technology.The problems such as slow in searching and time-consuming in the associated structure mining,as well as the weak correlation,vulnerability to adversarial attacks,and poor stability in dynamic link prediction are solved.They are applied to the mining and evolution analysis tasks of shipping transaction networks,which verifies that the research of this thesis has important theoretical significance and practical application value.