The node importance evaluation method based on graph convolution in multilayer heterogeneous networks

ABSTRACT

Node importance evaluation is a hot issue in complex network analysis. Existing node importance evaluation methods are mainly oriented to homogeneous networks, which ignore the heterogeneity of node types and edges. We propose an MLN critical node evaluation method based on graph convolution. In this paper, we generate the feature matrix of nodes. Considering the diversity of node types in the network, we design an adapted node sampling method based on the meta path. An MLN node embedding model is constructed based on a graph convolutional network (MGC). Besides, the negative sampling technique is used to complete MGC training. Metrics of critical node evaluation are constructed by combining the node embedding vectors and local structural features to evaluate the node's importance. The experimental results show that the proposed method has better evaluation accuracy than the K-Shell algorithm (K-Shell), K-shell-based gravity model ranking algorithm (KSDG), the Page Rank algorithm in MLN (PR), influence maximization based on network embedding (IMNE) and the node ranking algorithm based on information entropy (ERM).

KEYWORDS:

• Multi-layer network
• critical node evaluation
• graph convolution
• meta path

1. Introduction

Most real networks are usually composed of a large number of different types of nodes and edges (Shi et al., 2021), such as social networks, computer networks and biological networks. To better analyse such networks, most research scholars usually regard them as a homogeneous network (HON). HON does not consider the heterogeneity of object types and relationships. Therefore, networks with rich types of nodes and edges are regarded as a heterogeneous information network (HIN) as shown in Figure 1.

Figure 1. Illustration of HIN.

Scholars have done a lot of research on the basic problems of HIN, such as basic metrics (Yang et al., 2022; Huang, Zhou, et al., 2022), community structure detection (Huang, Chen, et al., 2022; Contisciani et al., 2020; Sun et al., 2020) and diffusion (Wang et al., 2021 ). Recent years have seen a growing interest in graph contrastive Learning, such as Zhao et al. (2021) consider that directly applying existing graph self-supervised learning methods to heterogeneous graphs can not fully capture the rich semantics and their correlations in heterogeneous graphs. They investigate self-supervised learning on heterogeneous graphs and propose a novel model named Multi-View Self-supervised heterogeneous graph Embedding (MVSE). By encoding information from different views defined by meta paths and optimising both intra-view and inter-view contrastive learning tasks, MVSE comprehensively utilises unlabelled information and learns node embeddings. Zhu et al. (2022) present a novel heterogeneous graph contrastive Learning method and generate multiple semantic views for HGs based on meta-paths and propose a novel multi-view contrastive aggregation objective to adaptively distil information from each view. Chen et al. (2023) propose heterogeneous graph contrastive learning method which enhances heterogeneous graph contrastive learning with meta networks to allow the personalised knowledge transformer with adaptive contrastive augmentation. It can incorporate heterogeneous relational semantics into the user-item interaction modelling with contrastive learning-enhanced knowledge transfer across different views.

Node importance evaluation is an important branch of HIN analysis. Evaluating critical nodes in HIN can effectively control the process of information propagation, such as accurately placing e-commerce advertisements to promote products, controlling the forwarding of information to suppress the spread of rumours, etc. However, most existing methods model the networks as aggregated structures without considering the inter-layer interactions, which lose semantic information. Multilayer structure pays more attention to heterogeneity in multilayer heterogeneous networks (MLN) (Kivela et al., 2014). A multilayer structure not only directly reflects the interactions between different layers but also preserves the more detailed information of the network. Node importance can be evaluated more comprehensively by extracting structural and semantic information.

Node importance evaluation has become a research hotspot in many fields. For example, finding out the most influential users can effectively regulate the spread of public opinions (Liu & He, 2020). Traffic congestion can be effectively reduced by finding critical traffic hubs (Liu et al., 2022). In the disease transmission network, finding the superinfection source can effectively block the infection source in time and prevent the spread of the disease (Li et al., 2021).

In this paper, we propose a node importance evaluation model based on a graph convolution network in MLN. The feature matrix of nodes is constructed based on topological structure attributes and semantic information. The node embedding model is constructed, which includes intra-graph semantic aggregation and inter-graph semantic aggregation. We evaluate the critical node by metrics, which are constructed based on node embeddings and structural features.

The main contributions of this paper include two aspects:

• An adapted node sampling method based on meta path is designed. Considering the unbalanced distribution number of different type nodes in MLN, we define a formula for calculating the coverage rate of sampling nodes.

• A node importance evaluation method in a multilayer network based on graph convolution is proposed, which is an effective method of identifying important nodes in MLN. It includes a node embedding model and metrics based on node embeddings and structural features.

The paper’s overall structure is organised as follows. Section 2 reviews some related work. Section 3 illustrates the basic concepts of multilayer networks. Section 4 introduces the method proposed in the paper. Section 5 discusses the results obtained in the experimental part. Section 6 summarises the method and points out the future research direction.

2. Related work

Because of the various types of nodes and connections in HIN (Zhou et al., 2022), scholars have done a lot of research on node importance evaluation. The node importance evaluation methods of HIN fall into two categories: meta path structure and multilayer structure.

2.1. Node importance evaluation methods based on the meta path method

The method usually constructs evaluation metrics based on the meta path to get node importance ranking. Yang et al. (2019) proposed a method based on meta path information entropy (MPIE). They transformed HIN into several homogeneous networks. Information entropy was used to describe the complexity and uncertainty of social impact. The ultimate node importance was calculated by integrating nodes’ influence in different meta paths. However, this method needs to traverse all public paths between node pairs when calculating the indirect influence of nodes, leading to high time complexity. Cun and Zhou (2021) proposed the adjacent information entropy model based on meta path and meta graph. This method integrated the structure and semantic information to measure node importance. Liu et al. (2020) considered the semantic information captured by a meta path is not enough to measure the importance of a node in HIN. They proposed a method based on the main meta path and auxiliary meta path. An auxiliary meta path was added to supplement the semantic information of the main meta path. The node correlation ranking was calculated by the main meta path. The node internal ranking was calculated by the auxiliary meta path. Molaei et al. (2020) proposed a method based on information entropy (ERM). ERM defined three different types of probability entropy according to the meta path. The ultimate node importance was calculated by integrating the entropy in different meta paths. ERM focused on the information of first-order neighbours and high-order neighbours of nodes but ignored the node characteristics influence. Yang, Zhou, et al. (2021) The nodes’ direct influence was constructed based on the nodes’ embedding vectors. The indirect influence is constructed based on the number of nodes’ common neighbours. The ultimate node importance was fused according to nodes’ direct influence and indirect influence. Those methods are faced with some problems, such as evaluating node importance based on specific meta paths or ignoring the node characteristics.

2.2. Node importance evaluation methods based on the multilayer structure

Node importance evaluation methods based on the multilayer structure can make full use of the rich node attribution information and comprehensive structure information in the network. Pedroche et al. (2016) defined the PageRank of MLN based on the inter-layer interactions. Shu et al. (2022) proposed a method for multiplex heterogeneous networks based on graph embedding. For one type and different types of edges, the nodes’ features were aggregated after random walk sampling neighbour nodes. The nodes’ features were mapped to the embedding space by multilayer perceptron to obtain the embedding vectors. Then, the node importance evaluation metrics were constructed by the nodes’ embedding vectors and local structure features. Besides, some researchers have focused more on how inter-layer connectivity affects the node importance of MLN. Rahmede et al. (2018) proposed a method based on network structure. They designed equations to calculate layers’ influences and nodes’ centrality. Wu et al. (2019) used a tensor framework to calculate the node’s eigenvector centrality. For a given form of inter-layer influence, they proved the uniqueness of the existence of eigenvector centrality. Luo et al. (2020) defined the local clustering coefficient with the ternary closure obtained by random walks in different layers. Then, they calculated node importance in the directed weighted network and the undirected weighted network with D-S evidence theory. Wan et al. (2022) divided nodes into core and auxiliary layers based on relational characteristics. The auxiliary layer nodes’ importance was quantified by designing the interlayer influence. The different interlayer influence was fused according to different weights. The nodes’ importance was fused according to the node transmission characteristics in the core layer and auxiliary layer. Wang et al. (2023) evaluated nodes’ importance by calculating nodes’ local structure entropy. They considered the nodes’ importance of intra-layer and inter-layer. Most of the above methods build multilayer homogeneous networks and quantify the importance of nodes through inter-layer connections and intra-layer topology information.

The node importance evaluation methods of multilayer homogeneous networks ignore the deep mining of multitype edges and nodes’ information in MLN. In addition, those methods also face the problem of how to quantify the inter-layer influence according to the inter-layer connectivity. Thus, we use a multilayer structure to model MLN, considering the interaction between different node types. Besides, random walk sampling based on meta path is used to construct a semantic graph, which includes the inter-layer and intra-layer interactions. We consider not only the nodes’ local information but also the different semantic information. Node features in the semantic graph are aggregated by using the attention mechanism and average pooling. In addition, we construct the metrics of critical node evaluation based on node embedding vectors and structural features.

3. Relate concepts

This section introduces the basic definitions of HIN. Aiming at the various types of nodes and edges in the original network, the paper uses a multilayer structure to model MLN.

3.1. Basic definition

Definition 3.1:

Heterogeneous network (Luo et al., 2014). HIN is a directed graph $\mathit{G}=(\mathit{V},\mathit{E})$ with an object-type mapping function $\mathit{\phi }:\mathit{V}\to \mathit{A}$ and a relationship-type mapping function $\mathit{\psi }:\mathit{E}\to \mathit{R}$. Each object $v\in \mathit{V}$ belongs to one particular object type in the object type set $\mathit{A}:\mathit{\phi }(\mathit{v})\in \mathit{A}$, and each relationship $e\in \mathit{E}$ belongs to a particular relationship type in the relationship type set $\mathit{R}:\mathit{\psi }(\mathit{e})\in \mathit{R}$, When the number of relationship types |R| > 1 or the number of object types |A| > 1 in the network, the network is heterogeneous.

Definition 3.2:

Network schema (Sun et al., 2011). The network schema is defined as ${\mathit{T}}_{\mathit{g}}=(\mathit{A},\mathit{R})$, which is a meta-description of the network $\mathit{G}=(\mathit{V},\mathit{E})$. Network schema is also a constraint used to define object types and relationship types, which makes HIN has the characteristics of a semi-semantic structure.

Definition 3.3:

Meta path (Sun et al., 2011). A meta path $\mathit{P}$ is a set of nodes defined on the network schema ${\mathit{T}}_{\mathit{g}}=(\mathit{A},\mathit{R})$, which have predecessor and successor connections. Meta path is expressed as ${\mathit{A}}_1\stackrel{{\mathit{R}}_2}{\to }{\mathit{A}}_2\stackrel{{\mathit{R}}_3}{\to }{\mathit{A}}_3\stackrel{{\mathit{R}}_4}{\to }{\mathit{A}}_4\dots .\stackrel{{\mathit{R}}_{\mathit{l}}}{\to }{\mathit{A}}_{\mathit{l}+1}$. $\mathit{R}={\mathit{R}}_1\circ {\mathit{R}}_2\circ \dots \circ {\mathit{R}}_{\mathit{l}}$ defines a compound relationship between types ${\mathit{A}}_1$ and ${\mathit{A}}_{\mathit{l}+1}$, where the combination operator $\circ$ on the relationship is represented.

Definition 3.4:

Semantic graph (Luo et al., 2014). The semantic graph $\mathit{M}$ is a directed acyclic graph with a single source node ${\mathit{v}}_{\mathit{i}}$ and a single target node ${\mathit{v}}_{\mathit{j}}$, which is defined on $\mathit{G}$ with the network schema ${\mathit{T}}_{\mathit{g}}$. The semantic graph is a set of interactive nodes based on a specific type of meta path, which expresses specific semantic information.

3.2. Multilayer network

A multilayer network (Kivela et al., 2014) with a multilayer structure is often used to model complex interaction structures between nodes. According to the definition of a multilayer network proposed by Boccaletti et al. (2014), the multilayer network is expressed as $\mathcal{M}=(\mathfrak{S},\mathcal{C})$, where $\mathfrak{S}=\{{\mathcal{G}}_{\alpha };\alpha \in \{1,\dots ,\text{n}\}\}$ is the set of subgraphs, ${\mathcal{G}}_{\alpha }=({\mathrm{X}}_{\alpha },E_{\alpha })$, ${\mathrm{X}}_{\alpha }$ is the node set of the subgraph ${\mathcal{G}}_{\alpha }$ and $E_{\alpha }$ is the edge set of subgraph ${\mathcal{G}}_{\alpha }$ where $\mathcal{C}=\{E_{\alpha \beta }\subseteq {\mathrm{X}}_{\alpha }\times {\mathrm{X}}_{\beta }\}$ is the set of edges between different subgraphs ${\mathrm{X}}_{\beta }$, $\alpha ,\beta \subseteq \{1,\dots ,n\}$, $\alpha \ne \beta$ and $E_{\alpha \beta }$ are the edges between subgraph ${\mathcal{G}}_{\alpha }$ and subgraph ${\mathcal{G}}_{\beta }$. To clearly show the relationship between different types of nodes in the network, it is usually modelled as MLN, as shown in Figure 2. In Figure 2, the nodes on the inter-layer share the same type, and nodes on different layers have different types. $E_{\alpha }$ is an edge on the $\text{layer }\alpha$, and $E_{\alpha \beta }$ is an edge between the layer $\alpha$ and the $\text{layer }\beta$.

Figure 2. Illustration of MLN.

4. Construction of the evaluation model

This section will address the construction of an evaluation model for critical nodes of MLN. The node feature matrix $\mathit{F}$ and adjacency matrix $\mathbf{\Lambda }$ are used as the inputs of multilayer graph convolution (MGC). The output of the model is the embeddings of nodes. Finally, the evaluation index of critical nodes is constructed and the importance ranking of nodes is obtained according to the importance scores of nodes.

4.1. Model structure

The overall structure of MLN node importance evaluation (MNIE) is shown in Figure 3. MNIE consists of three parts: the construction of the feature matrix and adjacency matrix, the multilayer graph convolution model (MGC) and node importance calculation. The inputs of the MGC model are the adjacency matrix $\mathrm{\Lambda }\in {\mathbb{R}}^{N\times N}$ and node feature matrix $F\in {\mathbb{R}}^{N\times d}$, where $N$ is the number of nodes and $\mathit{d}$ is the dimension of the feature vector. In Figure 3, $z_i^{{\mathit{M}}_k}$ represents the embeddings of nodes ${\mathit{v}}_{\mathit{i}}$ after intra-graph semantic aggregation. ${\mathit{Z}}_{\mathit{i}}$ represents the embeddings of the node ${\mathit{v}}_{\mathit{i}}$ after inter-semantic graph aggregation. $\mathit{T}\mathit{S}$ is the evaluation index of information propagation ability. $\mathit{I}\mathit{N}$ is the evaluation index of influence. $\mathit{G}\mathit{I}(\mathit{i})$ is the importance score of the node $v_i$.

Figure 3. Structure of the MLN node importance evaluation model.

4.2. Construction of feature matrix and adjacency matrix

4.2.1. Feature matrix

In the paper, the feature matrix $\mathit{F}$ includes two parts: topological features and semantic features. Centrality indexes are employed to construct topological features. The four centrality indexes are K-shell value $(KS)$ (Kitsak et al., 2010), local agglomeration coefficient $(LC)$ (Freeman, 2002), degree centrality $(DC)$ (Sabidussi, 1966) and feature vector centrality $(EC)$ (Bonacich & Lloyd, 2001). The semantic features are constructed based on the information entropy, which is based on the first-order neighbour information of the node and the neighbour information on the meta path (Cun & Zhou, 2021). Therefore, the feature matrix $\mathit{F}$ can be achieved by formula (1)(1) $\begin{array}{r}\mathit{F}=\left[\begin{array}{ccccc}L{C}_1& D{C}_1& E{C}_1& K{S}_1& I{E}_1\\ L{C}_2& D{C}_2& E{C}_2& K{S}_2& I{E}_2\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ L{C}_i& D{C}_i& E{C}_i& K{S}_i& I{E}_i\end{array}\right]\end{array}$(1) . (1) $\begin{array}{r}\mathit{F}=\left[\begin{array}{ccccc}L{C}_1& D{C}_1& E{C}_1& K{S}_1& I{E}_1\\ L{C}_2& D{C}_2& E{C}_2& K{S}_2& I{E}_2\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ L{C}_i& D{C}_i& E{C}_i& K{S}_i& I{E}_i\end{array}\right]\end{array}$(1)

Information entropy $IE$ is calculated by formula (2)(2) $\begin{array}{r}IE={\mathbb{E}}^L+{\mathbb{E}}^I\end{array}$(2) (Cun & Zhou, 2021). (2) $\begin{array}{r}IE={\mathbb{E}}^L+{\mathbb{E}}^I\end{array}$(2) where link entropy ${\mathbb{E}}^L$ is calculated by formula (3)(3) $\begin{array}{r}{\mathbb{E}}^{\mathit{L}}=-\sum _{\mathbf{\Theta }\in \mathit{R}}\sum _{\mathit{j}\in {\mathit{N}}^{\mathbf{\Theta }}(\mathit{i})}({\mathcal{P}}_{\mathit{i}\mathit{j}}\mathit{l}\mathit{o}{\mathit{g}}_2{\mathcal{P}}_{\mathit{i}\mathit{j}})\end{array}$(3) (Cun & Zhou, 2021). (3) $\begin{array}{r}{\mathbb{E}}^{\mathit{L}}=-\sum _{\mathbf{\Theta }\in \mathit{R}}\sum _{\mathit{j}\in {\mathit{N}}^{\mathbf{\Theta }}(\mathit{i})}({\mathcal{P}}_{\mathit{i}\mathit{j}}\mathit{l}\mathit{o}{\mathit{g}}_2{\mathcal{P}}_{\mathit{i}\mathit{j}})\end{array}$(3) where $\mathit{R}$ is the relation set, ${\mathit{N}}^{\mathbf{\Theta }}(\mathit{i})$ is the neighbour node set of the node ${\mathit{v}}_{\mathit{i}}$ on the relation $\mathbf{\Theta }$ and ${\mathcal{P}}_{\mathit{i}\mathit{j}}$ is the selection probability of neighbour nodes ${\mathit{v}}_{\mathit{j}}$. ${\mathcal{P}}_{\mathit{i}\mathit{j}}=D_i/\sum D_{{\mathit{N}}^{\mathbf{\Theta }}(\mathit{j})}$, where $D_i$ is the degree of the node ${\mathit{v}}_{\mathit{i}}$, ${\mathit{N}}^{\mathbf{\Theta }}(\mathit{j})$ is the neighbour nodes of the node ${\mathit{v}}_{\mathit{j}}$ on the relation $\mathbf{\Theta },\sum D_{{\mathit{N}}^{\mathbf{\Theta }}(\mathit{j})}$ is all degree of ${\mathit{N}}^{\mathbf{\Theta }}(\mathit{j})$. For example, the node ${\mathit{v}}_{\mathit{i}}$ has a neighbour node ${\mathit{v}}_{\mathit{j}}$, node ${\mathit{v}}_{\mathit{j}}\text{have neighbor nodes}$ {${\mathit{v}}_{\mathit{j}1}$, ${\mathit{v}}_{\mathit{j}2}$}. When $D_{{\mathit{v}}_{\mathit{i}}}=1$, $D_{\mathit{j}1}=1$, $D_{\mathit{j}1}=2$, we can calculate ${\mathcal{P}}_{\mathit{i}\mathit{j}}=0.528$.

Interactive entropy ${\mathbb{E}}^I$ is calculated by formula (4)(4) $\begin{array}{r}{\mathbb{E}}^{\mathit{I}}=-\sum _{\mathit{p}\in \mathit{P}}\sum _{\mathit{j}\in {\mathit{N}}^{\mathit{p}}(\mathit{i})}{\mathcal{P}}_{\mathit{i}\mathit{j}}\mathit{l}\mathit{o}\mathit{g}{\mathcal{P}}_{\mathit{i}\mathit{j}}\end{array}$(4) (Cun & Zhou, 2021). (4) $\begin{array}{r}{\mathbb{E}}^{\mathit{I}}=-\sum _{\mathit{p}\in \mathit{P}}\sum _{\mathit{j}\in {\mathit{N}}^{\mathit{p}}(\mathit{i})}{\mathcal{P}}_{\mathit{i}\mathit{j}}\mathit{l}\mathit{o}\mathit{g}{\mathcal{P}}_{\mathit{i}\mathit{j}}\end{array}$(4) where $\mathbf{P}$ is the meta path set, $\mathbf{p}$ is the meta path of $\mathit{P}$, ${\mathit{N}}^{\mathit{p}}(\mathit{i})$ is the neighbour node set of node ${\mathit{v}}_{\mathit{i}}$ in the meta path $\mathit{p}$. ${\mathcal{P}}_{\mathit{i}\mathit{j}}=D_i/\sum D_{{\mathit{N}}^{\mathit{p}}(\mathit{j})}$, where $D_{{\mathit{N}}^{\mathit{p}}(\mathit{j})}$ is all degree of the neighbour nodes of the node ${\mathit{v}}_{\mathit{j}}$ in the meta path $p$.

To make different features be the same order of magnitude, the features need to be normalised. The feature $\mathit{v}\mathit{a}{\mathit{l}}_{\mathit{i}}$ of the node ${\mathit{v}}_{\mathit{i}}$ is normalised by formula (5)(5) $\begin{array}{r}va{l}_i=\frac{rank}{N}\end{array}$(5) . (5) $\begin{array}{r}va{l}_i=\frac{rank}{N}\end{array}$(5) where $\mathit{r}\mathit{a}\mathit{n}\mathit{k}$ is the rankings of node $v_i$ scores according indexes $LC$, $DC$, $EC$, $KS$ and $IE$ , and $\mathit{N}$ is the total number of nodes.

4.2.2. Adjacency matrix

We sample nodes according to different meta paths to construct different semantic graphs. The adjacency matrix is constructed according to the semantic graph.

Considering different types of node number in MLN is different (Chen et al., 2018), random sampling will lead to over-sampling nodes with a small number and under-sampling nodes with a large number. Therefore, considering the unbalanced distribution of different types of nodes, we propose an adapted node sampling method based on meta path (AS-BMP) to achieve a semantic graph. AS-BMP is shown in algorithm 1. The semantic graph is shown in Figure 4.

Figure 4. Construction of the semantic graph.

Table

Algorithm 1: The pseudocode of AS-BMP

Input:              multilayer network $\mathcal{M}$, meta path $p_k$      Number of nodes sampled $N_i$, Adjacency matrix $\mathrm{\Lambda }$,

Node set of the semantic graph $m_k$

Output: semantic graph ${\mathit{M}}_k$

Step 1: Initialise parameters, $N_i=0,m_k(i)=\mathrm{\varnothing }$, we select the node $v_i$ of the starting sampling operation according to the meta path, and the wandering node $v^{\alpha }$ is defined as $v_i$.

Step 2: When $N_i$ is not satisfied, $v^{\alpha }$ walks to its first-order neighbour node $v_j$ based on the meta path $p_k$, where $1\le i\le n$ and $v^{\alpha }=v_j$. If $v_i\ne v_j$, then $m_k(i)=m_k(i)\cup \{v_j\}$ and $N_i$ is incremented by 1.

Step 3: When $N_i$ is satisfied, $v^{\alpha }=v_{i+1}$, we repeat step 2 and start the sampling of the next node. When all the target nodes are sampled, we calculate the node types and nodes number in $m_k$, and go to step 4.

Step 4: When the coverage $\mu$ is not satisfied, we set $N_i=0$, $v^{\alpha }=v_i$, and repeat steps 2 and 3; When the coverage $\mu$ is satisfied, the semantic graph is constructed according to the connection of nodes in the wandering sequence in the semantic graph node-set $m_k$.

Step 5: When all the sample operations of the meta path type $p_k$ are complete, the ${\mathit{M}}_k$ and the adjacency matrix $\mathrm{\Lambda }$ are output.

The calculation of the coverage $\mu$ in algorithm 1 is shown in formula (6)(6) $\begin{array}{r}\mu =\frac{{\mathcal{B}}_1}{N}+\frac{{\mathcal{B}}_2}{N}+\dots +\frac{{\mathcal{B}}_i}{N}\end{array}$(6) . (6) $\begin{array}{r}\mu =\frac{{\mathcal{B}}_1}{N}+\frac{{\mathcal{B}}_2}{N}+\dots +\frac{{\mathcal{B}}_i}{N}\end{array}$(6) where $N$ is the total number of nodes in $\mathcal{M}$, ${\mathcal{B}}_i$ is the number of nodes in $m_k$ with type $i$.

4.3. MGC model

Heterogeneous network embedding aims to embed nodes into low-dimensional vector space by using topological structure information and node attribute information of the network while retaining the inherent structural and semantic features of the network (Zhou et al., 2022). If only the first-order neighbour information is aggregated in the embeddings of MLN, the information of nodes of all types cannot be captured. For example, in the scientific cooperation network, there is no direct connection between the authors’ nodes, but there is a close cooperative relationship among the authors under the semantics of co-writing papers. Such semantic features cannot be obtained by first-order neighbours (Liang et al., 2022). Therefore, we design the MGC model, which aggregates neighbour node information on different semantic graphs to construct different semantic features. Then the semantic features on different semantic graphs are aggregated to obtain the final feature vectors of nodes. The MGC model includes intra-graph semantic aggregation and inter-graph semantic aggregation. The intra-graph semantic aggregation employs the attention mechanism (Zhang et al., 2019) to aggregate the features of neighbour nodes of the node ${\mathit{v}}_{\mathit{i}}$. The inter-graph semantic aggregation takes average pooling to aggregate the semantic features of neighbour nodes of the node ${\mathit{v}}_{\mathit{i}}$, which are on different semantic graphs.

4.3.1. Intra-graph semantic aggregation

The neighbouring nodes of the node ${\mathit{v}}_{\mathit{i}}$ on the same semantic graph have different importance. Thus, a self-attention mechanism (Zhang et al., 2019) is employed to aggregate neighbour features.

In Figure 5, ${\mathit{N}}_{\mathit{i}}^{{\mathit{M}}_{\mathit{k}}}=\{{\mathit{a}}_{\mathit{i}1}^{{\mathit{M}}_{\mathit{k}}},{\mathit{a}}_{\mathit{i}2}^{{\mathit{M}}_{\mathit{k}}}\dots {\mathit{a}}_{\mathit{i}\mathit{j}}^{{\mathit{M}}_{\mathit{k}}}\}$ represents the neighbour node set of the node ${\mathit{v}}_{\mathit{i}}$ on the semantic graph ${\mathit{M}}_{\mathit{k}}$. The embedding $z_i^{{\mathit{M}}_k}$ of nodes ${\mathit{v}}_{\mathit{i}}$ is computed by formula (7)(7) $\begin{array}{r}{\mathit{z}}_{\mathit{i}}=\sum _{\mathit{j}\in {\mathbf{\Gamma }}_{{\mathit{M}}_{\mathit{k}}}({\mathit{v}}_{\mathit{i}})}{\mathit{\omega }}_{\mathit{i}\mathit{j}}^{{\mathit{M}}_{\mathit{k}}}{\mathit{F}}_{\mathit{j}}\end{array}$(7) . (7) $\begin{array}{r}{\mathit{z}}_{\mathit{i}}=\sum _{\mathit{j}\in {\mathbf{\Gamma }}_{{\mathit{M}}_{\mathit{k}}}({\mathit{v}}_{\mathit{i}})}{\mathit{\omega }}_{\mathit{i}\mathit{j}}^{{\mathit{M}}_{\mathit{k}}}{\mathit{F}}_{\mathit{j}}\end{array}$(7) where ${\mathbf{\Gamma }}_{{\mathit{M}}_{\mathit{k}}}({\mathit{v}}_{\mathit{i}})$ is the neighbour set of the node ${\mathit{v}}_{\mathit{i}}$ on ${\mathit{M}}_{\mathit{k}}$, ${\mathit{F}}_{\mathit{j}}$ is the feature vector of the neighbour node ${\mathit{a}}_{\mathit{i}\mathit{j}}^{{\mathit{M}}_{\mathit{k}}}$. The calculation of neighbour feature weight ${\mathit{\omega }}_{\mathit{i}\mathit{j}}^{{\mathit{M}}_{\mathit{k}}}$ is shown in formula (8)(8) $\begin{array}{r}{\mathit{\omega }}_{\mathit{i}\mathit{j}}^{{\mathit{M}}_{\mathit{k}}}=\frac{\mathbf{e}\mathbf{x}\mathbf{p}\{\mathit{\sigma }(ϵ\cdot [{\mathit{F}}_{\mathit{i}}\otimes {\mathit{F}}_{\mathit{j}}])\}}{{\sum }_{\mathit{\lambda }\in {\mathbf{\Gamma }}_{{\mathit{M}}_{\mathit{k}}}({\mathit{v}}_{\mathit{i}})}\mathbf{e}\mathbf{x}\mathbf{p}\{\mathit{\sigma }(ϵ\cdot [{\mathit{F}}_{\mathit{i}}\otimes {\mathit{F}}_{\mathit{\lambda }}])\}}\end{array}$(8) . (8) $\begin{array}{r}{\mathit{\omega }}_{\mathit{i}\mathit{j}}^{{\mathit{M}}_{\mathit{k}}}=\frac{\mathbf{e}\mathbf{x}\mathbf{p}\{\mathit{\sigma }(ϵ\cdot [{\mathit{F}}_{\mathit{i}}\otimes {\mathit{F}}_{\mathit{j}}])\}}{{\sum }_{\mathit{\lambda }\in {\mathbf{\Gamma }}_{{\mathit{M}}_{\mathit{k}}}({\mathit{v}}_{\mathit{i}})}\mathbf{e}\mathbf{x}\mathbf{p}\{\mathit{\sigma }(ϵ\cdot [{\mathit{F}}_{\mathit{i}}\otimes {\mathit{F}}_{\mathit{\lambda }}])\}}\end{array}$(8) where $\mathit{\sigma }$ is the activation function, $\otimes$ is the dot product operation and $ϵ$ is the attention weight matrix. Then, through intra-graph semantic aggregation, the embeddings of the nodes are $z=\{z_1^{{\mathit{M}}_{\mathit{k}}},z_2^{{\mathit{M}}_{\mathit{k}}},z_4^{{\mathit{M}}_{\mathit{k}}},\dots ,z_{\mathit{i}}^{{\mathit{M}}_{\mathit{k}}}\}$.

Figure 5. Intra-graph semantic aggregation.

4.3.2. Inter-graph semantic aggregation

Considering that nodes have different semantic features on different semantic graphs, the average pooling method, as shown in Figure 6, is used to aggregate the features of the node ${\mathit{v}}_{\mathit{i}}$. The embedding ${\mathit{Z}}_{\mathit{i}}\text{of nodes }{\mathit{v}}_{\mathit{i}}$ after inter-graph semantic aggregation is calculated by (9)(9) $\begin{array}{r}{\mathit{Z}}_{\mathit{i}}=\frac{{\sum }_{\mathit{k}\in |\mathit{M}(\mathit{i})|}{z}_{\mathit{i}}^{{\mathit{M}}_{\mathit{k}}}}{|\mathit{M}(\mathit{i})|}\end{array}$(9) . (9) $\begin{array}{r}{\mathit{Z}}_{\mathit{i}}=\frac{{\sum }_{\mathit{k}\in |\mathit{M}(\mathit{i})|}{z}_{\mathit{i}}^{{\mathit{M}}_{\mathit{k}}}}{|\mathit{M}(\mathit{i})|}\end{array}$(9) where $|\mathit{M}(\mathit{i})|$ is the number of semantic graphs containing the node ${\mathit{v}}_{\mathit{i}}$. After inter-graph semantic aggregation, the embeddings of nodes are $\mathit{Z}=\{{\mathit{Z}}_1,{\mathit{Z}}_2,\dots ,{\mathit{Z}}_{\mathit{i}}\}$.

Figure 6. Inter-graph semantic aggregation.

4.4. Model training

To improve the convergence speed of the MGC model, the negative sampling technology is used to optimise the model parameters by comparing positive and negative samples to complete the training of the MGC model.

According to the type of meta path, node sampling is carried out to obtain the node-set $\mathit{P}\mathit{a}\mathit{t}\mathit{h}=\{\mathit{p}\mathit{a}\mathit{t}{\mathit{h}}_{\mathit{i}}|1\le \mathit{i}\le |\mathit{V}||\}$, where $\mathit{p}\mathit{a}\mathit{t}{\mathit{h}}_{\mathit{i}}$ is the path generated by sampling started from the node ${\mathit{v}}_{\mathit{i}}$. For the node ${\mathit{v}}_{\mathit{i}}$, the positive sample ${\mathit{v}}^{\mathit{r}}$ is obtained by randomly sampling the neighbouring nodes within the third-order neighbours of ${\mathit{v}}_{\mathit{i}}$ on $\mathit{p}\mathit{a}\mathit{t}{\mathit{h}}_{\mathit{i}}$, and the negative sample ${\mathit{v}}^{\mathit{n}}$ is obtained by randomly sampling a node on another path. Therefore, the training sample set ${\mathit{S}}_{\mathit{p}\mathit{a}\mathit{t}\mathit{h}}$ of the MGC model composed of all triples $({\mathit{v}}^{\mathit{r}},{\mathit{v}}_{\mathit{i}},{\mathit{v}}^{\mathit{n}})$ is obtained. The loss function of MGC is shown in formula (10)(10) $\begin{array}{r}\mathit{l}=\sum _{({\mathit{v}}^{\mathit{r}},{\mathit{v}}_{\mathit{j}},{\mathit{v}}^{\mathit{n}})\in {\mathit{S}}_{\mathit{p}\mathit{a}\mathit{t}\mathit{h}}}\{\mathit{l}{{\mathit{n}}^{\mathit{\sigma }[{\mathit{Z}}_{{\mathit{v}}^{\mathit{r}}}\cdot {\mathit{z}}_{{\mathit{v}}_{\mathit{i}}}]}}_{+}\mathit{l}{\mathit{n}}^{\mathit{\sigma }[-{\mathit{Z}}_{{\mathit{v}}^{\mathit{n}}}\cdot {\mathit{Z}}_{{\mathit{v}}_{\mathit{j}}}]}\}\end{array}$(10) . (10) $\begin{array}{r}\mathit{l}=\sum _{({\mathit{v}}^{\mathit{r}},{\mathit{v}}_{\mathit{j}},{\mathit{v}}^{\mathit{n}})\in {\mathit{S}}_{\mathit{p}\mathit{a}\mathit{t}\mathit{h}}}\{\mathit{l}{{\mathit{n}}^{\mathit{\sigma }[{\mathit{Z}}_{{\mathit{v}}^{\mathit{r}}}\cdot {\mathit{z}}_{{\mathit{v}}_{\mathit{i}}}]}}_{+}\mathit{l}{\mathit{n}}^{\mathit{\sigma }[-{\mathit{Z}}_{{\mathit{v}}^{\mathit{n}}}\cdot {\mathit{Z}}_{{\mathit{v}}_{\mathit{j}}}]}\}\end{array}$(10) where $\mathit{\sigma }$ is the sigmoid activation function and $\mathit{Z}$ is the embeddings of nodes after inter-graph semantic aggregation.

4.5. Node importance

This section mainly introduces the metric construction of critical node evaluation, including node propagation ability and node influence. The node importance score is obtained by the node propagation ability and node influence.

4.5.1. Node propagation ability

In MLN, the ability of propagation is affected by the local structure of nodes. The K-shell value represents the compactness of the topological structure around the node. The tighter the structure, the higher the node efficiency in spreading information (Kitsak et al., 2010). In addition, information entropy $\mathit{I}\mathit{E}$ can describe the complexity and uncertainty of information propagation among nodes in social networks (Cun & Zhou, 2021). Thus, we combine the K-shell and information entropy to construct the propagation ability of a node. The propagation ability of any node ${\mathit{v}}_{\mathit{i}}$ is calculated as shown in formula (11)(11) $\begin{array}{r}\mathit{T}\mathit{S}(\mathit{i})=\mathit{K}{\mathit{s}}_{\mathit{i}}\sum _{\mathit{j}\in \mathbf{\Gamma }(\mathit{i})}\mathit{K}{\mathit{s}}_{\mathit{j}}\times {\mathit{e}}^{\mathit{I}{\mathit{E}}_{\mathit{j}}}\end{array}$(11) . (11) $\begin{array}{r}\mathit{T}\mathit{S}(\mathit{i})=\mathit{K}{\mathit{s}}_{\mathit{i}}\sum _{\mathit{j}\in \mathbf{\Gamma }(\mathit{i})}\mathit{K}{\mathit{s}}_{\mathit{j}}\times {\mathit{e}}^{\mathit{I}{\mathit{E}}_{\mathit{j}}}\end{array}$(11) where $\mathit{K}{\mathit{s}}_{\mathit{i}}$ is the k-shell of the node ${\mathit{v}}_{\mathit{i}}$, $I{E}_{\mathit{j}}$ is the information entropy of the node ${\mathit{v}}_{\mathit{j}}$, and $\mathbf{\Gamma }(\mathit{i})$ is the first-order neighbour node set of the node ${\mathit{v}}_{\mathit{i}}$ on different semantic graphs.

4.5.2. Node influence

In MLN, the more the similar features, the more likely there is information interaction between nodes. The embeddings retain the structural features of the network (Freeman, 2002). In addition, the interaction between nodes will decrease when the Euclidean distance between embedding vectors becomes longer (Kitsak et al., 2010). Moreover, the more paths through the target node, the greater the influence of the target node (Liu et al., 2019). Thus, we take the ratio of the number of paths through the node ${\mathit{v}}_{\mathit{i}}$ and the total number of paths as the influence coefficient ${\mathit{\lambda }}_{\mathit{i}}$ of the node ${\mathit{v}}_{\mathit{i}}$. The influence $\mathit{I}\mathit{N}(\mathit{i})$ of the node ${\mathit{v}}_{\mathit{i}}$ is calculated by formula (12)(12) $\begin{array}{r}\mathit{I}\mathit{N}(\mathit{i})=\sum _{\mathit{j}\in \hat{\mathbf{\Gamma }}(\mathit{i})}{\mathit{\lambda }}_{\mathit{i}}{\mathit{e}}^{-{\mathbf{\Omega }}_{\mathit{i}\mathit{j}}}\end{array}$(12) . (12) $\begin{array}{r}\mathit{I}\mathit{N}(\mathit{i})=\sum _{\mathit{j}\in \hat{\mathbf{\Gamma }}(\mathit{i})}{\mathit{\lambda }}_{\mathit{i}}{\mathit{e}}^{-{\mathbf{\Omega }}_{\mathit{i}\mathit{j}}}\end{array}$(12) where ${\mathbf{\Omega }}_{\mathit{i}\mathit{j}}$ is the Euclidean distance between embeddings, $\hat{\mathbf{\Gamma }}(\mathit{i})$ is the set of neighbour nodes sharing the same type within the third order on different semantic graphs. ${\mathit{\lambda }}_{\mathit{i}}$ is computed by formula (13)(13) $\begin{array}{r}{\mathit{\lambda }}_{\mathit{i}}=\frac{{\mathit{p}}_{\mathit{v}\mathit{i}\mathit{a}}}{{\mathit{p}}_{\mathit{n}\mathit{u}\mathit{m}}}\end{array}$(13) (Liu et al., 2019). (13) $\begin{array}{r}{\mathit{\lambda }}_{\mathit{i}}=\frac{{\mathit{p}}_{\mathit{v}\mathit{i}\mathit{a}}}{{\mathit{p}}_{\mathit{n}\mathit{u}\mathit{m}}}\end{array}$(13) where ${\mathit{p}}_{\mathit{n}\mathit{u}\mathit{m}}$ is the total path number passing through the node ${\mathit{v}}_{\mathit{i}}$, and $p_{via}$ is the number of paths passing through its neighbour $v_j$.

4.5.3. Node importance calculation

The node importance $\mathit{G}\mathit{I}(\mathit{i})$ is obtained by the propagation ability and influence of nodes. $\mathit{G}\mathit{I}(\mathit{i})$ is calculated by formula (14)(14) $\begin{array}{r}\mathit{G}\mathit{I}(\mathit{i})=\mathit{r}\mathit{T}\mathit{S}(\mathit{i})+(1-\mathit{r})\mathit{I}\mathit{N}(\mathit{i})\end{array}$(14) . (14) $\begin{array}{r}\mathit{G}\mathit{I}(\mathit{i})=\mathit{r}\mathit{T}\mathit{S}(\mathit{i})+(1-\mathit{r})\mathit{I}\mathit{N}(\mathit{i})\end{array}$(14) where $\mathit{r}$ is the weight of node propagation ability. $\mathit{r}$ is determined by experiment, which can be seen in detail in the next section.

4.5.4. Time complexity analysis

The time complexity of preprocessing the node sampling probability based on the number of nodes and random walk sequences based on the meta path is shown in Formula (15)(15) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }\mathit{l}\mathbf{\ast }\mathit{h}\mathbf{\ast }\mathit{k})\end{array}$(15) . (15) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }\mathit{l}\mathbf{\ast }\mathit{h}\mathbf{\ast }\mathit{k})\end{array}$(15) where the number of nodes is $\mathit{n}$, the length of walk sequences is $\mathit{l}$, the number of walk sequences is $\mathit{h}$ and the types of meta-path is $\mathit{k}$.

The complexity of MGC training is shown in Formula (16)(16) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }\mathit{l}\mathbf{\ast }\mathit{h}\mathbf{\ast }\mathit{k}\mathbf{\ast }\mathit{b}\mathbf{\ast }\mathit{e})\end{array}$(16) . (16) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }\mathit{l}\mathbf{\ast }\mathit{h}\mathbf{\ast }\mathit{k}\mathbf{\ast }\mathit{b}\mathbf{\ast }\mathit{e})\end{array}$(16) where the number of negative samples is $\mathit{b}$ and the number of model iterations is $\mathit{e}$.

The complexity of node propagation ability calculation based on the k-shell and $IE$ value of neighbours is shown in Formula (17)(17) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }\mathit{a})\end{array}$(17) . (17) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }\mathit{a})\end{array}$(17) where the mean number of neighbours is $\mathit{a}$.

The complexity of node influence calculation based on the third-order neighbour node is shown in Formula (18)(18) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }{\mathit{a}}^3)\end{array}$(18) . (18) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }{\mathit{a}}^3)\end{array}$(18)

The complexity of weighted summation and ranking is shown in Formula (19)(19) $\begin{array}{r}\mathit{O}(\mathit{n})+\mathit{O}(\mathit{n}\mathit{l}\mathit{o}{\mathit{g}}^{\mathit{n}})\end{array}$(19) . (19) $\begin{array}{r}\mathit{O}(\mathit{n})+\mathit{O}(\mathit{n}\mathit{l}\mathit{o}{\mathit{g}}^{\mathit{n}})\end{array}$(19)

The total time complexity is shown in Formula (20)(20) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }\mathit{l}\mathbf{\ast }\mathit{h}\mathbf{\ast }\mathit{k}+\mathit{n}\mathbf{\ast }\mathit{l}\mathbf{\ast }\mathit{h}\mathbf{\ast }\mathit{k}\mathbf{\ast }\mathit{b}\mathbf{\ast }\mathit{e}+\mathit{n}\mathbf{\ast }\mathit{a}+\mathit{n}\mathbf{\ast }{\mathit{a}}^3+\mathit{n}+\mathit{n}\mathit{l}\mathit{o}{\mathit{g}}^{\mathit{n}})\end{array}$(20) . (20) $\begin{array}{r}\mathit{O}(\mathit{n}\mathbf{\ast }\mathit{l}\mathbf{\ast }\mathit{h}\mathbf{\ast }\mathit{k}+\mathit{n}\mathbf{\ast }\mathit{l}\mathbf{\ast }\mathit{h}\mathbf{\ast }\mathit{k}\mathbf{\ast }\mathit{b}\mathbf{\ast }\mathit{e}+\mathit{n}\mathbf{\ast }\mathit{a}+\mathit{n}\mathbf{\ast }{\mathit{a}}^3+\mathit{n}+\mathit{n}\mathit{l}\mathit{o}{\mathit{g}}^{\mathit{n}})\end{array}$(20)

Since $\mathit{l}$, $\mathit{k}$, $\mathit{h}$, $\mathit{b}$, $\mathit{e}$ and $\mathit{a}$ are usually small constants, the time complexity can be simplified, as shown in Formula (21)(21) $\begin{array}{r}\mathit{O}(\mathit{n}+\mathit{n}\mathit{l}\mathit{o}{\mathit{g}}^{\mathit{n}})\end{array}$(21) . (21) $\begin{array}{r}\mathit{O}(\mathit{n}+\mathit{n}\mathit{l}\mathit{o}{\mathit{g}}^{\mathit{n}})\end{array}$(21)

5. Experiment

To verify the effectiveness of the evaluation model, experiments are conducted on two real MLN datasets. The comparison method includes the K-shell algorithm (Kitsak et al., 2010), the Page Ranking algorithm in MLN (PR) (Tu et al., 2018), the entropy ranking algorithm (ERM) (Molaei et al., 2020), the K-shell-based gravity model ranking algorithm (KSDG) (Yang & Xiao, 2021) and influence maximisation based on network embedding (IMNE) (Yang, Zhou, et al., 2021). The basic information of each experimental dataset is shown in Table 1, in which the meta path type is referenced from the literature (Yang, Guan, et al., 2021).

1. DBLP (Yang, Guan, et al., 2021). It is a paper network in the computer field which contains four types of nodes: Author (A), Paper (P), Conferences (C) and Term (T). The types of edges include the following: the author writes the paper or the paper is written by the authors $\text{(}\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{A}\text{)}$; the paper is published in a conference or included in a conference $\text{(}\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{C}\text{)}$; the paper contains terms or terms are included in the paper $\text{(}\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{T}\text{)}$.

2. ACM (Yang, Guan, et al., 2021). The dataset from ACM Digital Library in 2010 includes data from 14 representative computer science conferences. Data contain three types of nodes: Papers (P), Authors (A) and Conferences (C). The types of edges include the following : the authors write the paper or the paper is written by the authors $\text{(}\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{A}\text{)}$; the paper is published in a conference or included in a conference $\text{(}\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{C}\text{)}$.

Table 1. Datasets.

Dataset	Nodes	Nodes Number	Edge Number	Relations	Meta paths
DBLP	A	14475	611542	$\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{A}$	APA
	P	14376		$\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{C}$	APCPA
	C	20		$\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{T}$	APTPA
	T	8898
ACM	P	12499	49554	$\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{A}$	APA
	A	17430		$\mathit{P}\stackrel{\leftharpoonup }{\rightharpoondown }\mathit{C}$	APCPA
	C	14

5.1. Evaluation method

The method based on the propagation model and the method based on node deletion are employed to evaluate the proposed method MNIE.

5.1.1. Method based on propagation

The evaluation method based on the propagation model mainly considers the ability of infecting other nodes. In the paper, the susceptible influenced model (SIR) (Avram et al., 2022) is used to evaluate the propagation information ability of nodes from the view of dynamics. The nodes in the SIR model fall into three states: susceptible state, infectious state and immune state. In the SIR model, the settings of the infection rate $\mathit{\delta }$ and recovery rate $\mathit{\gamma }$ depend on the topology of the network. Different semantic graphs of MLN have different topological structures, so $\mathit{\delta }$ and $\mathit{\gamma }$ should be set for different semantic graphs. In the experiment, $\mathit{\delta }$ is set as the threshold of infectious disease progressive propagation of each semantic graph. $\mathit{\gamma }$ is the reciprocal of the average degree on each semantic graph. The Top-100 nodes calculated by different methods are used as infection sources. After $\mathit{t}$ times of infection, the propagation coverage $\mathit{f}(\mathit{t})$ is the ratio of the infected nodes’ number in all semantic graphs and the total node numbers in all semantic graphs. In the experiment, we take the average of 10 independent experiments as the experimental results. The calculation of $\mathit{f}(\mathit{t})$ is shown in Formula (22)(22) $\begin{array}{r}\mathit{f}(\mathit{t})=\sum _{\mathit{l}=1}^{\mathit{k}}\frac{\mathit{i}\mathit{n}\mathit{f}\mathrm{\_}\mathit{n}\mathit{o}\mathit{d}\mathit{e}\mathit{s}({\mathit{M}}_{\mathit{l}})}{\mathit{a}\mathit{l}\mathit{l}\mathrm{\_}\mathit{N}\mathit{u}\mathit{m}(\mathit{M})}\end{array}$(22) . (22) $\begin{array}{r}\mathit{f}(\mathit{t})=\sum _{\mathit{l}=1}^{\mathit{k}}\frac{\mathit{i}\mathit{n}\mathit{f}\mathrm{\_}\mathit{n}\mathit{o}\mathit{d}\mathit{e}\mathit{s}({\mathit{M}}_{\mathit{l}})}{\mathit{a}\mathit{l}\mathit{l}\mathrm{\_}\mathit{N}\mathit{u}\mathit{m}(\mathit{M})}\end{array}$(22) where $\mathit{i}\mathit{n}\mathit{f}\mathrm{\_}\mathit{n}\mathit{o}\mathit{d}\mathit{e}\mathit{s}({\mathit{M}}_{\mathit{l}})$ is the total number of infected nodes on the semantic graph ${\mathit{M}}_{\mathit{l}}$ after the $\mathit{t}$ iteration, $\mathit{a}\mathit{l}\mathit{l}\mathrm{\_}\mathit{N}\mathit{u}\mathit{m}(\mathit{M})$ is the total number of nodes on all semantic graphs and $\mathit{k}$ is the number of semantic graphs.

5.1.2. Method based on deletion

Connected node pair is an index of network robustness (Fan et al., 2020), which describes the connectivity between nodes in the network. By observing the changes in the number of nodes in the maximum connected graph, we can judge the influence of nodes on the network topology. After the nodes are removed, the greater change of the number of nodes in the maximum connected graph, the greater the structure change of the overall network, meaning that the nodes are more important. The network connectivity is computed by formula (23)(23) $\begin{array}{r}\mathit{C}\mathit{o}\mathit{n}=\sum _{\begin{array}{c}l=1\\ {\mathit{G}}^{\mathbf{\prime }}\in {\mathit{M}}_{\mathit{l}}\end{array}}^{\mathit{k}}\frac{\mathit{M}\mathit{a}\mathit{x}(\mathit{N}\mathit{u}\mathit{m}({\mathit{G}}^{\mathbf{\prime }}))}{\mathit{a}\mathit{l}\mathit{l}\mathrm{\_}\mathit{N}\mathit{u}\mathit{m}(\mathit{M})}\end{array}$(23) : (23) $\begin{array}{r}\mathit{C}\mathit{o}\mathit{n}=\sum _{\begin{array}{c}l=1\\ {\mathit{G}}^{\mathbf{\prime }}\in {\mathit{M}}_{\mathit{l}}\end{array}}^{\mathit{k}}\frac{\mathit{M}\mathit{a}\mathit{x}(\mathit{N}\mathit{u}\mathit{m}({\mathit{G}}^{\mathbf{\prime }}))}{\mathit{a}\mathit{l}\mathit{l}\mathrm{\_}\mathit{N}\mathit{u}\mathit{m}(\mathit{M})}\end{array}$(23) where ${\mathit{G}}^{\mathbf{\prime }}$ is a connected subgraph on the semantic graph ${\mathit{M}}_{\mathit{l}}$, $\mathit{M}\mathit{a}\mathit{x}(\mathit{N}\mathit{u}\mathit{m}({\mathit{G}}^{\mathbf{\prime }}))$ is the nodes number in the maximum connected subgraph, $\mathit{a}\mathit{l}\mathit{l}\mathrm{\_}\mathit{N}\mathit{u}\mathit{m}(\mathit{M})$ is the total node number of all semantic graphs.

5.2. Experimental results and analysis

5.2.1. Determination of $\mathit{r}$

Different $\mathit{r}$ has different effects on the ranking quality of nodes’ importance. The top 200 nodes obtained by the MNIE method are divided into 10 groups, let$\text{'}$s say $g{p}_1$ to $g{p}_{10}$, which are used as infection sources in SIR and SI models. The nodes of $g{p}_i$ will be more important than the nodes of $g{p}_{i+1}$, so that the infection range of $g{p}_i$ is larger than that of the node of $g{p}_{i+1}$. For the SI model, when $t=\frac{T}{2}$, the propagation coverage $f(t)$ of each method has obvious discrimination. Therefore, the value of $f(t)$ is taken as MAX-SI. $T$ is the iteration step when the number of infected nodes is stable. For the SIR model, the maximum value of propagation coverage $f(t)$ is taken as MAX-SIR.

In the experiment, we selected the $\mathit{r}$ value, which can make MAX-SI and MAX-SIR approximately descent from $g{p}_1$ to $g{p}_{10}$, so that the ranking quality of nodes’ importance is better. Considering that the propagation of infection is accidental, the average value of 10 independent experiments is taken.

As can be seen from Figure 7, there are 11 different colour curves with a range of $\mathit{r}$ from 0 to 1 and an interval of 0.1, which describes MAX-SI and MAX-SIR values when $\mathit{r}$ takes different values. Specifically, as shown in Figure 7(a), when the $\mathit{r}$ is 0.6 in the ACM dataset, the MAX-SI approximately descent from $g{p}_1$ to $g{p}_{10}$. It is worth noting that the change curve of the MAX-SI value of r = 0.7 also has a similar effect as r = 0.6. However, it can be seen in Figure 7(b) that the MAX-SIR is not an obvious downward trend when r = 0.7. Thus, on the ACM dataset, it indicates when $r=0.6$ can obtain better node ranking quality. As shown in Figure 7(c,d), when the $\mathit{r}$ value is 0.3 in the DBLP dataset, the MAX-SI and MAX-SIR approximately descend from $g{p}_1$ to $g{p}_{10}$. It indicates that $r=0.3$ can obtain better node ranking quality.

Figure 7. Comparison diagram of max-SIR and max-SI. (a) The impact of $r$ value on max-SI in ACM, (b) The impact of $r$ value on max-SIR in ACM, (c) The impact of $r$ value on max-SI in DBLP, (d) The impact of $r$ value on max-SIR in DBLP.

In summary, on the ACM dataset, the $r$ is 0.6. Similarly, on the DBLP dataset, the $r$ is 0.3.

5.2.2. Accuracy and ranking quality

We use the SI model and SIR model to evaluate the accuracy and ranking quality of critical nodes obtained by each method. We select the top 100 nodes obtained by different methods (K-shell, PR, ERM, KSDG and MNIE) as the infection source of the SI model. The experimental results of propagation coverage $f(t)$ are shown in Figure 8.

Figure 8. Comparison diagram of SI. (a) ACM dataset. (b) DBLP dataset.

As shown in Figure 8, compared with other methods, $f(t)$ of MNIE is higher when $\mathit{t}$ between 3 and 20. On the other hand, $f(t)$ of MNIE reaches a steady state when the iteration step is 20, while steady state other methods are later. It confirms the high efficiency of MNIE.

In addition, these methods have little difference in infected nodes at the beginning of the iteration, but only an obvious difference at the late iteration. Because at the beginning of the iteration, there are few infected nodes, the infection range is not much different. With the increase in iteration steps, the number of infected nodes increases exponentially, showing obvious differences. Moreover, the maximum infection range of each method is not much different after iterative stability. The reason is that the network has strong connectivity and the infection source can infect most nodes after enough iteration.

As shown in Figure 8, compared with ERM, MNIE is leading in infection coverage on two datasets in the middle of an iteration. The main reason is that ERM is a single evaluation metric of information entropy based on the meta path, which will lead to excessive dependence on the type of the meta path. While MNIE not only mines topological structure and semantic information based on the meta path but also considers the influence of node features on node importance. The infection coverages of K-shell on DBLP and ACM datasets are the worst. The reason is that the K-shell cannot further distinguish the nodes’ importance on the same shell and ignores the semantic information of nodes in heterogeneous networks.

As shown in Figure 9, the top 100 nodes of methods (K-shell, PR, ERM, IMNE, KSDG and MNIE) are divided into 10 groups, such as $GP=\{g{p}_1,g{p}_2,\dots ..,g{p}_{10}\}$, which are used as infection sources to spread infection in the SIR model. Considering that the spread of infection is accidental, the average value is taken after 10 independent experiments.

Figure 9. Comparison diagram of MAX-SIR. (a) ACM dataset. (b) DBLP dataset.

Intuitively, if $\text{MAX}-\text{SIR }$ approximately descend from $g{p}_1$ to $g{p}_{10}$, the ranking quality of nodes’ importance is better. On the ACM dataset, the MAX-SIR values of $g{p}_1,g{p}_2,g{p}_3,g{p}_4$ obtained by MNIE were higher than those of other methods. It indicates that the critical nodes of $g{p}_1,g{p}_2,g{p}_3,g{p}_4$ evaluated by MNIE have better ranking quality. On the DBLP dataset, the critical nodes of $g{p}_1,g{p}_2,g{p}_3,g{p}_4,g{p}_5,g{p}_6$ evaluated by MNIE have better ranking quality. The reason is that MNIE pays attention to not only node features on the nodes’ importance but also local structure information.

In the ACM dataset, the experimental results of MNIE show that except for the $g{p}_4$ group, nodes have smaller MAX-SIR values than $g{p}_5$ group nodes. The reason is that there are nodes, which should have been sorted in $g{p}_i$, sorted in $g{p}_{i-k}$. There are many such situations in the nodes obtained by other methods.

In summary, the critical nodes evaluated by MNIE have better accuracy and ranking quality.

5.2.3. Network connectivity impact analysis

To further verify the accuracy of the critical nodes obtained by each method, we compute the network connectivity after deleting critical nodes in sequence.

As can be seen from Figure 10, $Con$ of the top 100 nodes obtained by deleting MNIE on two datasets drops faster. It means that MNIE has advantages over other methods. When the nodes obtained by the K-shell algorithm are deleted, the decrease in network connectivity is less obvious than in K-shell, PR, ERM, IMNE and KSDG. Because the K-shell algorithm ignores the influence of semantic information on HIN connectivity. Besides, when the nodes obtained by IMNE are deleted, the decrease in network connectivity is less than MNIE. Although the IMNE method pays attention to node features, it ignores local structure information on the nodes’ importance. When the nodes obtained by ERM are deleted, the decrease in network connectivity is less than MNIE. Although the ERM method pays attention to the information of first-order neighbours and high-order neighbours, it ignores node features on the nodes’ importance.

Figure 10. Comparison chart of network connectivity. (a) ACM dataset. (b) DBLP dataset.

6. Conclusion

Aiming at the existence of various types of nodes and edges in MLN, we proposed a critical node evaluation method for MLN. We used the meta path to mine semantic information and structural information between nodes, to effectively evaluate critical nodes in MLN. Experimental results show that compared with K-shell, PR, ERM and KSDG methods, our method can more accurately evaluate the critical nodes in MLN. In the paper, the inter-graph semantic aggregation needs to be further optimised, which ignores the differences in the importance of node features on different semantic graphs. In addition, because the paper constructs the heterogeneous network as a static heterogeneous network, it ignores the dynamic nature of the network. In future, the dynamic impact of MLN on critical node evaluation will be further considered to improve the evaluation accuracy of critical nodes in MLN.

Acknowledgements

The authors would like to thank the anonymous reviewers for their constructive and insightful comments on the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant number 62062050], the Natural Science Foundation of Jiangxi Province [grant number 20202B ABL2020 39] and the Innovation Foundation for Postgraduate Student of Jiangxi Province [grant number YC2021-S709].