Research On Mining Key Nodes In Complex Networks Based On Higher-order Interaction Analysis

The key nodes of complex networks are some special nodes that can have a significant impact on network structure and function,such as super-spreader,online marketing anchors,Weibo big V users,etc.Mining key nodes in complex networks is an important supporting technology for tasks such as network attack and defense,infectious disease control,network cognitive warfare,and network public opinion supervision.Network modeling and node representation are important steps in mining key nodes,and existing modeling and representation methods are mainly based on the binary interaction between two individuals.However,with the in-depth exploration of real systems,researchers have found that in most real complex systems,there are not only binary interactions between two individuals,but also widely existing interactions between multiple individuals,that is,higher-order interactions phenomena.For example,in the paper collaboration network,a paper often involves multiple authors;A user’s viewpoint on the internet may be forwarded or commented on by multiple users simultaneously.The higher-order structure of complex networks can clearly describe higher-order interactions.Formally,higher-order interaction refers to the interaction behavior of multiple individuals acting on the higher-order structure of a network.Compared to binary interaction,higher-order interaction characterizes the interaction behavior of multiple individuals in a system.Research based on higher-order interaction analysis can explain complex propagation phenomena from a new perspective,study the relationship between higher-order structure and function of networks,and discover missing dynamic properties from a binary interaction perspective.These are also crucial for mining key nodes in complex networks.However,the existing researches on key node mining in complex networks do not make full use of higher-order interaction information and higher-order interaction dynamics properties,resulting in inaccurate key node mining results in complex networks.In response to the above issues,this paper focuses on the characteristics of static networks,dynamic networks,and multi-layer uncertain networks,and adopts modeling methods such as hypernetworks,directed networks,asynchronous interactive temporal networks,synchronous interactive temporal networks,multi-layer temporal networks,and multiplex networks,through in-depth analysis of the interaction forms between multiple nodes in various complex networks,the network topology is modeled and analyzed using complex higher-order correlation structures such as hypergraph,motif,temporal motif,simplex,then design methods suitable for mining key nodes of various complex networks such as hypernetworks,directed networks,asynchronous interactive temporal networks,synchronous interactive temporal networks,multi-layer temporal networks and multiplex networks,and provide theoretical basis and technical support for network attack and defense,infectious disease control,network cognitive warfare and network public opinion supervision.The main contributions of this dissertation are as follows:1.Propose a method for measuring node centrality in hypernetworks based on hyperedge participation ratio.Aiming at the problem that the existing measurement methods of node centrality in the hypernetworks tend to focus on the target node itself,only considering the contribution of neighbor nodes to the target node,but ignoring the contribution of target node to the structure and dynamics of neighbor nodes,which leads to inaccurate mining results of key nodes in the hypernetworks,this research uses incidence matrix to represent the relationship between nodes and hyperedges in the non-uniform hypergraph,on this basis,and gives the definition of hyperadjacency matrix;Considering the importance of hyperedges in maintaining connectivity and interaction dynamics,the nodes that participate in many hyperedges should be important.Inspired by this idea,the hyperedge participation ratio can be obtained by summing the normalized node weights that depend on hyperedges,and the nodes in the hypernetworks are sorted using hyperedge participation ratio.Finally,by conducting experiments on four real hypernetwork datasets,and the results show that compared with four classic hypernetworks node centrality measurement methods,the proposed hypernetworks node centrality measurement method improved the accuracy of key node mining under different Top-k node granularity.2.Propose a directed network node centrality measurement method based on the motif attention mechanism.In response to the problem of although existing methods for mining key nodes in directed networks consider network structure and node features,they do not fully utilize the higher-order interaction characteristics between multiple nodes in directed networks,resulting in inaccurate mining results of key nodes in directed networks,this dissertation starts from the perspective of higher-order interaction analysis and uses motifs to characterize the interaction patterns between multiple nodes in directed networks,and adopt the weighted motif adjacency matrix to encode the motif-based adjacency relationship between nodes in the network;In order to enable different neighbors to learn different weights,a higher-order neural network model(i.e.HONNMA)is designed by combining graph attention networks.Specifically,attention weights are learned through the motif attention mechanism,and node embeddings are obtained through skip connections,then multiple feedforward layers are used to predict the critical scores of nodes,finally nodes are sorted based on the critical scores.This dissertation validates the accuracy of the node centrality measurement method for directed network on four real-world datasets.The experimental results show that the accuracy of the proposed node centrality measurement method for directed network is superior to the existing state-of-the-art benchmark models.3.Propose a method for measuring node centrality in asynchronous interactive temporal networks based on temporal motifs.In response to the current methods for mining key nodes in temporal networks that only focus on the first-order interaction relationship between nodes,but do not fully utilize the higher-order interaction characteristics of sequential interactions between multiple nodes across time,resulting in inaccurate mining results of key nodes in asynchronous interactive temporal networks,this dissertation considers that temporal patterns are repetitive,connected,and important network connection patterns,they can fully capture the temporal information and higher-order interaction relationships in the temporal networks,so employ temporal motifs to represent the sequential interaction patterns between multiple nodes across time;To obtain the most relevant temporal motifs,first perform temporal motifs pattern matching and select the most relevant temporal motifs based on the frequency matrix of the motifs;In order to obtain the most relevant temporal motif instances,a temporal motif instance extraction algorithm is designed;On this basis,in order to encode the adjacency relationship between nodes based on temporal motifs,a matrix calculation algorithm is designed to obtain the weighted motif adjacency matrix and diagonal motif out-degree matrix;In order to mine the key nodes in the temporal network,the motif transition matrix is defined,which contains the personalized information,higher-order interaction information and time information of nodes.Based on this,according to Perron-Frobenius theorem,and combined with PageRank algorithm,the personalized temporal motifs PageRank score of nodes is calculated,so as to sort the nodes in the temporal networks.By conducting steady-state analysis on the temporal motifs PageRank algorithm,and comparing it with the state-of-the-art benchmark models for key node mining in static and dynamic networks on four real-world datasets,the experimental results show that the asynchronous interactive temporal network node centrality measurement method can accurately mine rich key nodes.4.Propose a method for measuring node centrality in synchronous interactive temporal networks based on simplex and memory.In view of the problem that the existing researches on key node mining in synchronous interactive temporal networks do not fully consider the simultaneous interaction between multiple nodes in the temporal networks,and the nodes tend to establish contact with the nodes they have interacted with,which leads to the inaccurate results of key node mining in synchronous interactive temporal networks,this research uses simplex structure to describe the simultaneous interaction mode between multiple nodes,define memory to accurately describe repetitive interaction phenomena,and thus construct a simplex activation driven model with memory(SADM);On this basis,in order to obtain the aggregated degree of nodes,the aggregated degree of nodes can be derived based on the generation process of the SADM model.This aggregation degree can be used as a node centrality measurement in synchronous interactive temporal networks.On the basis of node aggregation,in order to explore how the SADM model affects the propagation process,this dissertation is based on the Susceptibility Infection Recovery(SIR)model and uses the temporal heterogeneous mean field method to calculate the SIR epidemic threshold of the SADM model.The simulation experiment results show that the memory in node connection mode reduces the aggregated degree of nodes by limiting the propagation process between nodes with repeated communication modes,and shifts the epidemic threshold to a larger value,thereby reducing the density of infected nodes and ultimately making the system less susceptible to the spread of diseases.5.Propose a higher-order supercentricity measurement method for multi-layer temporal networks and multiplex networks based on motifs.The existing researches on key node mining in multi-layer temporal networks and multiplex networks only focus on the first-order interaction relationships between nodes in the time or relationship layers,while underutilizing the higher-order interaction characteristics between multiple nodes at the same granularity(time/relationship),resulting in inaccurate key node mining results in multi-layer temporal networks and multiplex networks.This research considers the importance of ternary closures in networks,and uses motifs to represent higher-order interaction patterns between multiple nodes;In order to encode the adjacency relationship based on the motifs in the network,the weighted motifs adjacency matrix corresponding to different motifs types is obtained according to the weighted motifs adjacency matrix algorithm;Considering that both edge based and motifs based relationships are closely related to the centrality of nodes,carry on the linear combination of the weighted motifs adjacency matrix and the first order adjacency matrix,and then combine with the centrality of eigenvectors,the intra-layer centrality matrix is obtained;On this basis,in order to couple the centrality matrix of the time/relationship layer and the inter layer relationship,a higher-order supercentricity matrix is designed,which can simultaneously encode the inter-layer interaction relationship and inter-layer coupling relationship;In order to obtain the centrality of nodes and/or layers,the joint centrality of node layer pairs,the marginal centrality of nodes and layers,and the conditional centrality of nodes and layers are obtained by solving the right principal eigenvalue equation.The uniqueness and positive definiteness of higher-order supercentricity are theoretically analyzed and proved.Finally,to verify the accuracy of the higher-order supercentricity measurement method based on motifs,experiments are conducted on two real-world datasets.The results show that the higher-order supercentricity measurement method for multi-layer temporal networks and multiplex networks can accurately mine rich key nodes.