IEEE Computational Intelligence Magazine - February 2023 - 55

A. IM in Social Networks
A social network is modeled as a graph G¼ (V, E), where V¼
{1, 2, .. ., v}and E¼ {eij j i,j2V} are accordingly the node-set
and edge set ofthe network [42]. Given a seed set A2Vwith k
seed nodes, a probabilistic influence spread model returns the
expected number of nodes influenced by the seeds, which is
denoted as s(A). Many models are proposed to describe the
influence spread process under different scenarios, such as the IC,
WC, and LT models. The IC model is one ofthe most widely
studied diffusion models, and many proxy models are developed
to approximate this model [43], [44]. Therefore, this article
chooses the ICmodel to describe the influence spread process.
In the IC model [9], all the nodes are either active or inactive.
Activated nodes influence inactive nodes through connections
between nodes with a propagation probability p.
Considering a seed set A2Vwith k nodes, the influence spread
process can be expressed as follows. In the first step, k seeds in A
are active and saved in set A1. At step t, given the propagation
probabilityp (u, v) ofthe edge euv, a node u2At-1 may activate an
inactive neighbor v with the probability p. Note that u only has
one chance to activate its neighbors. Those successfully activated
nodes are saved in the set At. The above influence spread process
stops when At ¼. Then, the number of active nodes in the
influence spread process is defined as the influence spread s (A)
ofseed set A under the IC model.
IM can be considered as the following discrete problem
[45]: Given a social network G ¼ (V, E) and the size of seed
set k, the goal ofthe IM problem is to select a seed set A under
an influence spread model such that,
arg max s AðÞ s:t: Ajj ¼ k
AV
(1)
where j A j is the size of set A. To solve the above IM problem,
tens of thousands ofMonte Carlo simulations are used to
estimate the influence spread process of any given seed set,
which is very time-consuming [43]. In the next section, two
popular proxy models, EDV and TIS, are introduced to
approximate influence spread s to replace the expensive
Monte Carlo simulation process.
B. Proxy Models for Meta-Heuristic Methods
EDV [18]. For a small propagation probability p in the IC
model, EDV estimates the expected number of nodes influenced
by seed set A with k seeds through,
EDV AðÞ ¼ k þ
b2NB AðÞnA
X
1 1pðÞd bðÞ
;
(2)
where NBðAÞ¼ A [fbj9a 2 A; eab 2 Eg represents one-hop
neighbors of the seed set A, and dðbÞ¼jfaja 2 A; eab 2 Egj
represents the influence from A to b. j j is the number ofelements
in the set. This formula essentially extracts the edge
and node information ofN(A) to form a subgraph to quickly
evaluate the influence spread. A series of existing efforts use
meta-heuristic algorithms to optimize EDV or its variants,
The fitness landscapes of these two
optimization tasks are indeed highly
similar because these proxy models all
consider the neighbor information of
the seed set, leading to a large amount
of available knowledge between the
optimization processes of the different
proxy models.
such as the SA [18], the particle swarm optimization (PSO)
[23], [46], and the ant colony optimization [24]. Compared
with heuristic-based methods, these methods can quickly find
more accurate solutions in real-world networks.
TIS [20]. For the IC model, TIS estimates the influence
spread ofthe seed set A by the 2-hop neighborhood through,
TIS AðÞ ¼
X
a2A
b ¼
TIS afg
@
X
a2A
X
a2A
X
b2NaðÞ\A
X
X
b2NaðÞ=A c2NbðÞ\A= afg
where N () denotes the 1-hop nodes cover of seed, p (a, b)
represents the propagation probability between the active
node a and the inactive node b, and a(b) represents the 1-hop
influence spread of the node b. In (3), the first term evaluates
the sum of the 2-hop influence spread of seeds in A. The second
and third terms consider the potential redundant influences
between the seeds. TIS considers the information of the
seed neighbors and the neighbors' neighbors to quickly
approximate the influence spread of the seed set, which has
been widely extended to solve IM problems on different types
of networks [25], [47]. Based on TIS, some proxy models are
proposed, such as LIE [21], [48], and IEEV [22].
Since different proxy models consider different neighbor
information on the seed set, the use ofEDV and TIS may lead
to different search behaviors with similar characteristics, thus
resulting in different performance on specific problems. The
EDV and the TIS have been emphasized in previous studies,
so this article chooses them as alternative transformations of
IM problems. Furthermore, in Section V. E, more comparative
experiments are provided to illustrate the rationale for
choosing EDV and TIS.
C.MTFO
Given S alternate formulations {f1,f2, ...,fS} ofa target minimization
taskf, the MTFO problem can be formalized as [32],
min
x
fi xðÞ; i ¼ 1; 2; ... ; S
s:t: x ¼ x1; x2; ... ; xm 0
2 D
(4)
FEBRUARY 2023 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 55
pa; bðÞpb; cðÞ
pa; bðÞ a bðÞpb; aðÞ
ðÞ
1
A b;
(3)
IEEE Computational Intelligence Magazine - February 2023

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - February 2023
