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
62
159
5.129
NetGRQC
5242
14496
5.5261
NetHEPT
15233
58891
3.8635
Table 3 The parameters in our algorithm.
Parameter
Meaning
Value
a
The constant term in (2)
4
b
The amplification term in (2)
10
maxgen
The maximum generation
50
pop
Population size
200
pool
Size of the mating pool
100
tour
Tournament size
2
pc
Crossover probability
0.8
pm
Mutation probability
0.2
AUGUST 2016 | IEEE Computational intelligence magazine
29
http://www.arXiv.org
Table of Contents for the Digital Edition of Computational Intelligence - August 2016
Computational Intelligence - August 2016 - Cover1
Computational Intelligence - August 2016 - Cover2
Computational Intelligence - August 2016 - 1
Computational Intelligence - August 2016 - 2
Computational Intelligence - August 2016 - 3
Computational Intelligence - August 2016 - 4
Computational Intelligence - August 2016 - 5
Computational Intelligence - August 2016 - 6
Computational Intelligence - August 2016 - 7
Computational Intelligence - August 2016 - 8
Computational Intelligence - August 2016 - 9
Computational Intelligence - August 2016 - 10
Computational Intelligence - August 2016 - 11
Computational Intelligence - August 2016 - 12
Computational Intelligence - August 2016 - 13
Computational Intelligence - August 2016 - 14
Computational Intelligence - August 2016 - 15
Computational Intelligence - August 2016 - 16
Computational Intelligence - August 2016 - 17
Computational Intelligence - August 2016 - 18
Computational Intelligence - August 2016 - 19
Computational Intelligence - August 2016 - 20
Computational Intelligence - August 2016 - 21
Computational Intelligence - August 2016 - 22
Computational Intelligence - August 2016 - 23
Computational Intelligence - August 2016 - 24
Computational Intelligence - August 2016 - 25
Computational Intelligence - August 2016 - 26
Computational Intelligence - August 2016 - 27
Computational Intelligence - August 2016 - 28
Computational Intelligence - August 2016 - 29
Computational Intelligence - August 2016 - 30
Computational Intelligence - August 2016 - 31
Computational Intelligence - August 2016 - 32
Computational Intelligence - August 2016 - 33
Computational Intelligence - August 2016 - 34
Computational Intelligence - August 2016 - 35
Computational Intelligence - August 2016 - 36
Computational Intelligence - August 2016 - 37
Computational Intelligence - August 2016 - 38
Computational Intelligence - August 2016 - 39
Computational Intelligence - August 2016 - 40
Computational Intelligence - August 2016 - 41
Computational Intelligence - August 2016 - 42
Computational Intelligence - August 2016 - 43
Computational Intelligence - August 2016 - 44
Computational Intelligence - August 2016 - 45
Computational Intelligence - August 2016 - 46
Computational Intelligence - August 2016 - 47
Computational Intelligence - August 2016 - 48
Computational Intelligence - August 2016 - 49
Computational Intelligence - August 2016 - 50
Computational Intelligence - August 2016 - 51
Computational Intelligence - August 2016 - 52
Computational Intelligence - August 2016 - 53
Computational Intelligence - August 2016 - 54
Computational Intelligence - August 2016 - 55
Computational Intelligence - August 2016 - 56
Computational Intelligence - August 2016 - 57
Computational Intelligence - August 2016 - 58
Computational Intelligence - August 2016 - 59
Computational Intelligence - August 2016 - 60
Computational Intelligence - August 2016 - 61
Computational Intelligence - August 2016 - 62
Computational Intelligence - August 2016 - 63
Computational Intelligence - August 2016 - 64
Computational Intelligence - August 2016 - 65
Computational Intelligence - August 2016 - 66
Computational Intelligence - August 2016 - 67
Computational Intelligence - August 2016 - 68
Computational Intelligence - August 2016 - 69
Computational Intelligence - August 2016 - 70
Computational Intelligence - August 2016 - 71
Computational Intelligence - August 2016 - 72
Computational Intelligence - August 2016 - 73
Computational Intelligence - August 2016 - 74
Computational Intelligence - August 2016 - 75
Computational Intelligence - August 2016 - 76
Computational Intelligence - August 2016 - Cover3
Computational Intelligence - August 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202311
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202308
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202305
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202302
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202211
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202208
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202205
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202202
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202111
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202108
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202105
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202102
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202011
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202008
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202005
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_202002
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201911
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201908
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201905
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201902
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201811
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201808
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201805
https://www.nxtbook.com/nxtbooks/ieee/computationalintelligence_201802
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring17
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring16
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring15
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring14
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_summer13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_spring13
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_winter12
https://www.nxtbook.com/nxtbooks/ieee/computational_intelligence_fall12
https://www.nxtbookmedia.com