A super adjacency matrix-time-network modeling method was constructed to sort the
nodes of the time network. The model includes the attenuation factor to describe the
interlayer coupling strength more accurately. An algorithm combining heuristic and
greedy strategy was proposed to determine the impact of the nodes of a temporal network.
3.1 Construction of Superadjacency Matrix Temporal Network Modeling Method based on
Interlayer Coupling Intensity Attenuation
Finding critical nodes in a network has long been a popular area of study. A technique
for modeling temporal networks that uses interlayer coupling intensity attenuation,
the super-based adjacency matrix (ASAM), was proposed to represent the changing process
of the actual network more appropriately, taking the multilayer graph temporal network
model as the foundation. In the specific application of temporal networks, individual
users are usually regarded as nodes in the network and generally defined as $G=\left(V,F\right)\,.$
Where $V=\left\{v_{1},v_{2},\ldots ,v_{N}\right\}$ represents the node set that contains
all nodes. $\left[0,m\right]$ is the time period; The triplet $f_{t}=\left(i,j,t\right)$
is the set of edges of the temporal network on $\left[0,m\right]$; $i$ and $j$ denote
the nodes in the network; $t$ is the time to establish the connections for nodes.
$F=\left\{f_{1},f_{2},\ldots ,f_{t}\right\}$ is the network edge set of all triples.
The temporal network may be split into $T$ time windows using time intervals $w$,
and the temporal network becomes a discrete slice network $G_{1},G_{2},\ldots ,G_{T}$.
Sequential network modeling is the basis of sequential network node ranking and influence
maximization algorithms. Temporal network modeling is divided mainly into three types:
time aggregation graph, snapshot-based temporal network model, and temporal network
model based on obvious path flow [18]. The time aggregate graph model can show the dynamic evolution of the actual network
more realistically, but it is not easy to store and calculate the matrix. Snapshot-based
temporal network models are divided into a multilayer graph temporal network model
and a time window model [19]. Fig. 1 illustrates the time window model.
Fig. 1. Time window graph model with a time window size of 2.
Fig. 2. Multilayer graph temporal network model with a time window size of 2.
Fig. 3. Time series network model based on obvious runoff.
The time interval of the time window model at this time was 2, which affects the time
window size (Fig. 1). A, B, C, and D are the nodes of a temporal network, and the interactions among
nodes are represented by the lines connecting them. Snapshots at different times are
displayed as a time aggregation graph in chronological order. The model can show the
evolution process of the event. Fig. 2 presents the multilayer diagram sequential network model.
Fig. 2 denotes the relationship between layers. The model also includes four network nodes,
A, B, C, and D, and lines represent the interaction among nodes. The multilayer graph
temporal network model generally comprises intra-layer and inter-layer relationships.
The interactions among nodes are represented mainly by intra-layer relationships,
and there are corresponding snapshots. In adjacent snapshots, the connection relationship
between the corresponding nodes is expressed mainly through the inter-layer relationship.
Fig. 3 shows the sequential network model based on obvious channel runoff.
The time-series network model based on obvious path runoff contains more nodes and
more connections among nodes (Fig. 3). The horizontal axis below the model represents the time scale, which results from
further refinement of the model in the time dimension. In addition, the interaction
between nodes occurs only between two adjacent time layers, and the nodes only connect
themselves in the preceding and following time layers. Overall, the evaluation methods
of node importance can be split into three categories: evaluation based on network
effectiveness changes, evaluation based on the propagation model, and evaluation based
on the correlation [20]. The evaluation calculation based on network performance changes is expressed in
Eq. (1):
where $E\left(G\right)$ is the network timing performance before important nodes are
deleted; $E\left(G\right)$ is the deletion ratio of the nodes; $E\left(G\right)$ is
the network timing performance after the cumulative deletion of $E\left(G\right)$
proportional nodes. The network timing performance is usually evaluated using the
network timing efficiency and the maximum connectivity component of network timing.
The network timing efficiency was calculated using Eq. (2):
where $d_{t}\left(u,v\right)$ denotes the temporal distance between nodes opposite
sides $\left(u,v\right)$ of time $t$; $N$ denotes the total quantity of nodes. Eq.
(3) shows the calculation of the maximum connected component of network timing.
where $\left| \left.C_{\partial }^{\psi }\right| \right.\left(1\leq \partial \leq
k\right)$ denotes the quantity of nodes in $\partial $ connected graph in the $\psi
$ snapshot, and$k$ is the number of connected components in each snapshot. The evaluation
based on the correlation mainly involves the Kendall correlation coefficient and accuracy.
The Kendall correlation coefficient was calculated using Eq. (4):
where$\xi $ is the logarithm of the sequence; $n_{c}$ is a sequence consistent quantity;
$n_{d}$ is the number of sequence inconsistencies. The value interval of $\tau $ is
$\left[-1,1\right]$, and the greater the link, the higher the value. The accuracy
rate was calculated using Eq. (5):
where $P_{\upsilon }$ and $R_{\upsilon }$ represent the sorting results of the first$\upsilon
$ point in real sorting and predicted sorting respectively. The multilayer coupling-network-analysis
technique was used in the development process of the Supra-adjacency Matrix (SAM).
The SAM matrix is expressed in Eq. (6).
where $A^{\left(1\right)},A^{\left(2\right)},\ldots ,A^{\left(T\right)}$ denotes intra-layer
connection; $\omega I$ is interlayer connectivity; $\omega $ is an adjustable parameter;
$I$ is the identity matrix. The enhanced similarity index (ESI) is a new suggested
local similarity index for measuring inter-layer coupling, which was proposed after
integrating fixed parameters and local similarity index. The ESI was calculated using
Eq. (7).
When $\sum _{j}a_{ij}^{t}=1$, nodes $i$ and $j$ in time layer $G_{T}$ have connected
edges. $CN_{i}^{\left(t,t+1\right)}$ denotes the number of common neighbors of node
$i$ on both $G_{T}$ networks. Eq. (8) was used to calculate $CN_{i}^{\left(t,t+1\right)}$.
where the First-order neighbor set was denoted by $\Gamma _{i}^{t}$. An ASAM model
was proposed to measure the interlayer coupling strength of the adjacent-layer and
cross-layer network nodes. In addition, the attenuation coefficient was incorporated
into the ASAM model to describe the interlayer coupling intensity more accurately.
The attenuation factor was calculated using Eq. (9).
where $\mu $ is the adjustable parameter; $\Delta t$ is the space of time between
successive epochs.
where the time values $t_{1}$ and $t_{2}$ are associated with the time-layer network,
and $1\leq t_{2}-t_{1}\leq 4$. The research used the centrality of eigenvectors for
the calculation to express the importance of nodes, as expressed in Eq. (11).
where $\eta $ is the feature vector; $\theta _{\alpha \beta }$ is the element in the
column $\alpha $ of row $\beta $ of the matrix, displaying the eigenvector centrality
of node $i$ on the temporal layer $\beta $.
3.2 Design of Influence Maximization Algorithms and Visualization Tools for Temporal
Networks
The information dissemination model can predict the future dissemination trend of
information and can visualize the process of information dissemination. The Independent
Cascade (IC) model and the Linear Threshold (LT) model are influence models, both
of which may replicate the process of information dissemination. Fig. 4 shows the propagation mechanism of the IC model.
where $V_{1}$ to $V_{7}$ are nodes, and the value between nodes is the propagation
probability $p_{u,v}\in \left[0.1\right]$. Green indicates that the node is currently
active, and red indicates that the node is currently inactive. First, decide the parent
node of the active state. The second step is to determine whether to activate other
nodes according to the size of the propagation probability. The LT model mainly completes
the propagation process through the influence weight and influence threshold. There
are four kinds of infectious disease models, and the network nodes in these four models
have four states. Different models have different node state transitions. Fig. 5 shows the node state transitions of each of the four models.
Fig. 4. Propagation process of the IC model.
Fig. 5. Node state transitions for each of the four models.
S, I, R, and E represent the susceptible, infected, recovered, and exposed states
of the node, respectively (Fig. 5). $\delta $ is the probability of infection; $\gamma $is the probability of cure;
$\varepsilon $ is the probability of infection. The susceptible infected (SI) nodes
in the SI model have a $\delta $ probability of becoming infected. The SI nodes in
the susceptible (SIS) model are likely to $\delta $ transform into infected nodes;
A node in an infected state has a $\gamma $ probability of transforming into a susceptible
state. The susceptible infected recovered (SIR) nodes have a $\delta $ probability
of transforming into susceptible. A node in a susceptible state has a $\gamma $ probability
of transforming into a recovered state. The susceptible exposure infected recovered
(SEIR) nodes in the SEIR model have a $\delta $ probability of being exposed. A node
in the exposed state has an $\varepsilon $ probability of transforming into an infected
state. A node in an infected state has a $\gamma $ probability of transitioning to
a recovered state. A discrete combinatorial optimization problem in mathematics is
the impact maximization issue. The initial seed set selected in the temporal network
is expressed as Eq. (12).
where $\phi $ is a set of nodes found in the temporal network; $\phi $ is also known
as seed collections; $\sigma \left(\phi \right)$ denotes the range of influence of
the seed collection. $\left| \left.\phi \right| \right.$ is the quantity of nodes
in $\phi $, and $\mathrm{\hslash }$ denotes the value of $\left| \left.\phi \right|
\right.$. The marginal gain of the seed set $\phi $ is expressed as Eq. (13).
where $\sigma _{v}\left(\phi \right)$ is the size of the marginal benefit of the node.
The main metrics of influence maximization algorithms are the time complexity and
the influence range of the seed set. The propagation probability was calculated using
Eq. (14).
where $d_{v}$ denotes the degree of the node; $CN\left(u,v\right)$ indicates the number
of common neighbors among nodes. Eq. (15) expresses the likelihood that node $u$ will affect node $v$.
where the eigenvector centrality of network node $u$ is shown by $E_{u}$. The eigenvector
centrality of network node $E_{v}$ is shown by $v$. Because the IC model is proposed
based on a static network and cannot be applied directly, it was improved in this
research. Fig. 6 presents the propagation process of the improved IC model in the G3 slicing website.
The circles in Fig. 6 represent the nodes. The green, yellow, blue, and red circles are the seed nodes,
active nodes, nodes to be activated, and inactive nodes, respectively. The propagation
probability is mostly dependent on the activity of the node. The temporal-network
combined heuristic greedy (TCHG) algorithm was adopted. The algorithm combines the
benefits of greedy and heuristic algorithms. The selection of seed nodes can be split
into the heuristic and greedy stages. In the previous stage, nodes with greater influence
values are chosen for the candidate seed set. In the later stage, the algorithm selects
the nodes with more sway in the candidate seed set and takes them as the final seed
set. The timing network visualization tool is implemented mainly using Python language
and a Python-based graphical user interface. The visualization tool has six main functional
modules: data reading and writing module, network parameter calculation module, network
topology mapping module, ASAM method module, TCHG algorithm module, and seed node
information-propagation process module.
Fig. 6. Propagation process of the IC model in slicing network G3.