Influence Maximization based on a Non-dominated Sorting Genetic Algorithm

摘要

Influence Maximization (IM) is a problem represented by a set of users who are specified in advance and are usually called the seed. The latter can influence their friends, who can in turn influence others and so on until it reaches the largest number of users within the network. This issue is of ultimate importance in a variety of fields. In the current study, a Non-dominated Sorting Genetic Algorithm II (NSGA-II) has been adopted in influence maximization to produce the so-called NSGAII based IM algorithm (NSGAII-IM). Principally, the population should be represented with individuals of variable lengths as the seed group, and the diffusion model should be designed so as to formulate its multi-objective function. In the context of individual representation, the nodes have been pseudo-randomly chosen using the centrality measures (based on high centrality nodes as degree, closeness, and eigenvector). As for the multi-objective function, increasing the coverage size of influence and decreasing the number of seed nodes as far as possible have been set as the conflicting objectives. Weighted Integration Cascade (WIC) has been suggested as an improved version of the Independent Cascade (IC) diffusion model. It has proven to be effective in the performance of the NSGAII-IM algorithm. In evaluating the proposed optimization model, two real-world social network datasets have been used: Facebook wall posts, and Digg networks. The algorithm showed promising results as it could relatively improve the solutions as compared with other methods, with an increased average of influential spread. Additionally, the WIC model has proven to be effective through the evaluation of the performance of the NSGAII-IM algorithm with other diffusion models.