Analysis Of Group-based Influence Maximization Methods

With the popularity of microblog,Facebook and other social media,social network has become a platform on which people follow others,transmit information and share contents to interact and influence with each other.Users in the same group have similar characteristic,including the compactness in structure and similarity in attribute.Influence propagation between users is another important research content in social network analysis.To solve the influence maximization problem,researchers proved the problem is NP-hard and put forward an greedy algorithm to solve this problem.However,the greedy algorithm needs a large amount of Monte Carlo simulations which leads to high time complexity.To improve the algorithm efficiency,researchers proposed the community-based influence maximization algorithms.However,when dividing communities,community-based influence maximization algorithms only consider the density of connection while neglect the influence property of nodes.As a result,they cannot make good approximation when computing influence spread and need a large amount of Monte Carlo simulations.To improve the accuracy and efficiency of community-based influence maximization algorithms,a group-based influemce maximization algorithm is proposed to calculate influence spread with group structure.This alogorithm firstly defines a measurement to evaluate the similarity of two nodes.Then,this algorithm clusters nodes with similar inflence into the same group.Finally,influence spread is estimated based on the group structure and most influencial nodes are selected.The main work of this paper includes the following points:1.The first step of group-based influence maximization is group detection.Community only considers the density of connection while group considers more about the similarity between nodes' characteristics.In this paper,groups are divided according to the similarity of influence property.To improve the neighborhood vector propagation algorithm,a local influence-based group detection method is proposed to get groups with similar influence property.2.In this paper,influence maximization problem is used to evaluate the group detection algorithms.Results show that the local influence-based group detection method has low time efficiency,so the global influence-based group detection method is adopted.Based on the group structure,a two-stage propagation model is used to model the propagation process and select the seeds with the most influence spread.3.Community-based influence maximization algorithm,greedy algorithm and two heuristic alogorithms are introduced to compare with group-based influence maximization algorithm.Five real-world datasets and a series of synthetic datasets are used to evaluate the accuracy and scalability of these algorithms.Experiments show that the improved group-based influence maximization algorithm is more accurate and scalable.