IEEE Systems, Man and Cybernetics Magazine - October 2022 - 46

social networks: Custpost and Custforward. But, in fact, a part
of all Custpost (original publishing behaviors) obtained
should belong to Custmention (reporting behaviors), which is
different from the communication network. Therefore,
related and need to be distinguished.
Method Steps
The primary process of building a dissemination network
is to associate the equivalent information and derivative
information released by other users after information N is
released. For example, for the forwarding behavior list Kf,
the information in the list contains the relationship of its
entire forwarding sequence, so it is easy to add to the propagation
network. For the publishing behavior list Kp,
according to definition 4, part of the information is derived
information from information N, corresponding to the
behavior type Custmention, which needs to be added to the
propagation network HN. The other part is the original
information of other users, corresponding to the behavior
type Custpost, and has nothing to do with the communication
network HN. The basic idea of building a propagation
network is to establish a relationship between the information
in the current action and the existing nodes in the
propagation network in sequence according to time. The
basic steps are as follows:
1) establish the initial node of the propagation network HN,
< y, Equaled >
2) merge the list Kf and the list Kp and sort to obtain the
list K
3) traverse the list K, assuming that the current traversed
behavior is < uid, custtype, t,Nll >, denote modeold as
the node that publishes information N' in the propagation
network
4) if custtype = Custmention, create a new node modenew for
the information N', and update the information dissemination
network HN = CustNode(HN, modeold, modenew, forwarded)
5)
If custtype = Custpost, create a new node modenew for
the information N', and update the information
dissemination network HN = CustNode(HN, modeold,
modenew, Mentioned).
Experiment and Result Evaluation
Experimental Data
To build a dissemination network, accurate social network
data are needed. Here, we choose to use a crawler to crawl
users' public information in Sina Weibo as the experimental
data. The crawled data can be divided into microblog
data, personal information data, and social relationship
data. In the micro blog data finally crawled, the number of
users is 2,903,403, and the total number of micro blogs is
23,068,115, of which 7,006,235 are forwarded. The crawled
Weibo content is all content posted by users during the
2018 National Day.
Result Analysis
The existing influence maximization methods are
mainly divided into three types: heuristic algorithm,
Monte Carlo method, and community-based algorithm.
Since the community-based algorithm is difficult to
extend to user privacy protection requirements, the
Monte Carlo-based method has certain theoretical guarantees.
The node degree and the node's distance in the
network are the basis of standard heuristic algorithms.
Therefore, three representative Monte Carlo methods
are selected for the comparative experiments in this
paper: simulate greedy algorithm, degree algorithm, and
distance algorithm. The degree algorithm and the distance
algorithm are both heuristic algorithms. The
Monte Carlo simulation part of the algorithm is only
used to judge whether the seed set satisfies the privacy
protection constraint.
1) Incremental greedy algorithm: Construct the seed set
incrementally according to the greedy rule and use
Monte Carlo to estimate the size of the influence and
whether the privacy protection constraints are met.
2) Degree-based algorithm: a degree heuristic algorithm
based on the degree of the node. In the beginning, all
nodes are sorted according to the degree of the node
from large to small, and then try to join the seed set in
sequence, which requires Monte Carlo simulation.
1,000
1,200
1,400
1,600
200
400
600
800
10
20
40
60
80
Figure 2. A comparison of algorithms running time based on
influence index.
46 IEEE SYSTEMS, MAN, & CYBERNETICS MAGAZINE October 2022
Proposed Greedy Algorithm
Incremental Greedy Algorithm
Distance-Based Algorithm
Degree-Based Algorithm
3) Distance-based algorithm: a heuristic algorithm based
on the average distance to all other nodes. In the beginning,
all nodes are sorted from small to
large, and then they are added to the seed
set in sequence, and Monte Carlo simulation
is required.
4) Influence-based greedy algorithm (proposed):
The algorithm Calculate Bound is
used to calculate the vq (y) of each node
initially and the algorithm Local Influence
is used to estimate the influence of
the seed set. The algorithm also constructs
the seed set incrementally but
requires Monte Carlo simulations.
The simulate greedy algorithm uses the
Monte Carlo method to calculate the
IEEE Systems, Man and Cybernetics Magazine - October 2022

Table of Contents for the Digital Edition of IEEE Systems, Man and Cybernetics Magazine - October 2022
