Affiliations: [a] Department of Software Engineering, Faculty of Computer Engineering, University of Isfahan, Isfahan, Iran | [b] Department of Artificial Intelligence, Faculty of Computer Engineering, University of Isfahan, Isfahan, Iran | [c] Department of Computer Science, Aalborg University, Aalborg, Denmark
Correspondence:
[*]
Corresponding author: Maryam Hosseini-Pozveh, Department of Software Engineering, Faculty of Computer Engineering, University of Isfahan, Isfahan, Iran. Tel.: +98 3137934070; Fax: +98 3137934038; E-mail:ma.hosseini@eng.ui.ac.ir
Abstract: Influence maximization in a social network
involves identifying an initial subset of nodes with a pre-defined size in
order to begin the information diffusion with the objective of maximizing
the influenced nodes. In this study, a sign-aware cascade (SC) model is
proposed for modeling the effect of both trust and distrust relationships on
activation of nodes with positive or negative opinions towards a product in
the signed social networks. It is proved that positive influence
maximization is NP-hard in the SC model and influence function is neither
monotone nor submodular. For solving this NP-hard problem, a particle swarm
optimization (PSO) method is presented which applies the random keys
representation technique to convert the continuous search space of the PSO
to the discrete search space of this problem. To improve the performance of
this PSO method against premature convergence, a re-initialization mechanism
for portion of particles with poorer fitness values and a heuristic mutation
operator for global best particle are proposed. Experiments establish the
effectiveness of the SC in modeling the real-world cascades. In addition,
PSO method is compared with the well-known algorithms in the literature on
two real-world data sets. The evaluation results demonstrate that the
proposed method outperforms the compared algorithms significantly in the SC
model.
Keywords: Influence maximization, Signed social networks, particle swarm optimization
