Computational Intelligence - August 2016 - 27

term that guarantees the least selection in each community.
After selecting the Candidate, the last step of our algorithm is to
generate the ultimate seeds.
C. Seed Generation

algorithm 1 Framework of meme-im.

input: Maximum generation: maxgen, population size: pop,
mating pool size: pool, tournament size: tour, crossover
probability: pc, mutation probability: pm, spread probability:
p, seed size: k, the candidate nodes pool: Candidate and the
connection matrix: A.
output: The most influential k-node set.
1: step 1) initialization
2: step 1.1) Population initialization:

P = " x 1, x 2, ..., x pop ,T ;

step 1.2) Best individual initialization: Pbest = x i ;

step 2) Set t = 0; // the number of generations
step 3) repeat
step 3.1) Select parental chromosomes for mating;
Pparent ! Selection(P, pool, tour);
7: step 3.2) Perform genetic operators:
Pchild ! Geneticoperation( Pparent , pc, pm);
8: step 3.3) Perform local search:
Pnew ! LocalSearch( Pchild );
9: step 3.4) Update population:
P ! UpdatePopulation(P, Pnew );
10: step 3.5) Update the best individual Pbest ;
11: step 4) stopping criterion: If t < maxgen, then
t = t + 1 and go to step 3), otherwise, stop the
algorithm and output.
4:
5:
6:

5
4

After the two aforementioned steps, the search space has been
reduced. In the next step, we will employ the proposed problemspecific memetic algorithm, named as Meme-IM, to generate
the ultimate seeds by optimizing the 2-hop influence spread
shown as (1). The whole framework of Meme-IM is shown as
Algorithm 1.
In Step 1), Meme-IM mainly completes the population
initialization task. Firstly, it creates the initial population of
solutions P = " x 1, x 2, ..., x pop ,T according to a problem-specific strategy. And then it selects the individual with the maximum fitness as Pbest . Step 3) is the evolution procedure. In
Step 3.1), Meme-IM first uses the deterministic tournament
selection method to select parental individuals Pparent for mating in genetic algorithm. Then in Step 3.2), Meme-IM
reproduces the chosen parental individuals Pparent , i.e., performs crossover and mutation operation on Pparent . Step 3.3)
is an individual reinforcement procedure. Step 3.4) is to
refresh the current population by taking the best pop individuals from P , Pnew . And in Step 4), when the algorithm terminates on convergence, Meme-IM stops and outputs the
ultimate k-node set.

Position
Integer
String

123456789
123456789

Figure 4 Illustration of the representation. Left: a 9-node set selected from Candidate. Right: the individual encoding of the 9-node set.

In the following, we will give a more detail description of
several important procedures including the population initialization, genetic operation and local search procedure.
1) Representation and Initialization
In Meme-IM, each chromosome (individual) x a (1 # a # pop )
in the population represents a k-node set, which is encoded as
an integer string
x a = " x 1a , x 2a , ..., x ka ,,
where k is the number of seeds, each gene x ia of the chromosome corresponds to a node selected from Candidate. An illustration of this representation is shown as Fig. 4. It is noticed
that there is no repeated node in x a . Considering that the
solution produced by selecting k nodes randomly from Candidate is of low quality and may result in a long time to converge,
we attempt to initialize a higher quality population to speed
up the convergence. Here, we propose a similarity-based high
degree method called SHD. The SHD and the random mechanism can guarantee the convergence and diversity of the individuals. The population initialization procedure is shown as
Algorithm 2.
High degree centrality is a standard method for influence
maximization on social and other networks [34]. But high

algorithm 2 population initialization.

input: Population size: pop
output: Population P
1: Generate a half of population based on ShD, see
algorithm 3 for more information;
2: for i from 1 to ^ pop/2 h do
3:
for j from 1 to k do
4:
if rand ^1 h 2 0.5 then
5:
select a random node different from each node in x i
j
from the Candidate to replace x i ;
6:
end if
7:
end for
8: end for
9: for i from ^ pop/2 + 1 h to pop do
10:
select k different nodes from the Candidate to
initialize x i based on ShD;
11: end for

auguSt 2016 | IEEE ComputatIonal IntEllIgEnCE magazInE

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