Computational Intelligence - August 2016 - 29

The Eval() function is to compute the fitness
of a solution based on (1). The FindBestNeighbor() function is to find the best neighbor chromosome with the largest fitness value.

The similarity-based local search procedure attempts
to find a better individual from the neighborhoods of
the individual.

V. Experimental Study

In this section, we evaluate the effectiveness and the efficiency
of our proposed algorithm CMA-IM and compare the influence spread and the running time with other six algorithms on
three real-world social networks.
A. Experiment Setting

1) Datasets
Dolphin network [35]. The small size Dolphin social network
describes the associations between 62 bottlenose dolphins living in Doubtful Sound, New Zealand [35]. Lusseau observed
the behavior of the dolphins in a period of seven years. The
nodes of the network represent dolphins and edges represent a
statistically frequent associations between these dolphins.
NetGRQC network [36]. The medium size NetGRQC
network is a collaboration network whose nodes represent
authors and edges represent co-authors relationships between
them. If two authors coauthor a paper, an edge establishes
between them. The data contains papers collected from the
"General Relativity and Quantum Cosmology" section of the
e-print arXiv (http://www.arXiv.org) in a period from January
1993 to April 2003.
NetHEPT network [10]. The large size NetHEPT network
is also a collaboration network of paper co-authors and is frequently used in previous works such as [10]. The papers in this
dataset are obtained from the "High Energy Physics-Theory"
section of the e-print arXiv from year 1991 to year 2003. This
network contains multiedges if the two co-authors have collaborated multiple papers.
The basic characteristics of the real-world networks
described above are given in Table 2.
2) Comparing Algorithms
CGA-IM and MA-IM. CGA-IM is the variant version of
CMA-IM by removing the local search procedure and MA-IM
is the variant of CMA-IM by removing the network clustering
step. We compare CMA-IM with CGA-IM and MA-IM on
two real-world networks to demonstrate the effectiveness of
the network clustering and the local search procedure in
CMA-IM.
CELF. The CELF algorithm [9] is an improvement on the
greedy algorithm which has the same result as the greedy algorithm and as much as 700 times speedup. Here, we take the
number of Monte-Carlo simulations as 10,000 to obtain an
accurate estimate.
CMA-HClustering and CMA-SLPA. CMA-HClustering
and CMA-SLPA are two comparing algorithms combining
our memetic algorithm and the network clustering algorithms
in [1] and [12], respectively.

Degree centrality. The Degree centrality [15] is a classical
heuristic for mining influential nodes, which believes the more
neighbor nodes connected, the more important the node is. It
sorts nodes in the descending order according to their degrees
and simply selects the top k nodes as the seeds.
PageRank. PageRank is the popular algorithm for ranking
webpages based on their importance proposed by Brin and
Page [37]. Here, the restart parameter is set as 0.15 and the stop
criterion is set as 0.001. PageRank sorts the nodes according to
their importance and return their ranks. We select the top k
nodes as seed nodes.
Random. Random is a baseline method used in [15]. The
random method randomly selects k nodes as the seeds.
Other famous heuristics are not taken into consideration
such as the distance centrality and the betweeness centrality
because of their high computational cost [10].
All experiments are implemented under the IC model. In
order to compare the accuracy of different algorithms, we
compute the influence spread of the ultimate k-node set of
each algorithm by running Monte-Carlo simulation for 10,000
times and take the average influence spread. All algorithms are
independently run 30 times on each network. All the experiments are conducted on a PC with 1.70 GHz Inter Core i5
and 8.00 GB Memory. The experimental parameters of our
algorithm are listed in Table 3.

Table 2 Statistics of the three real-world networks.
Network

Nodes

Edges

Average degree

Dolphin

159

5.129

NetGRQC

5242

14496

5.5261

NetHEPT

15233

58891

3.8635

Table 3 The parameters in our algorithm.
Parameter

Meaning

Value

The constant term in (2)

The amplification term in (2)

maxgen

The maximum generation

pop

Population size

200

pool

Size of the mating pool

100

tour

Tournament size

Crossover probability

0.8

Mutation probability

0.2

AUGUST 2016 | IEEE Computational intelligence magazine

http://www.arXiv.org

Table of Contents for the Digital Edition of Computational Intelligence - August 2016