Community Structure Based Research On Influence Maximization Problem

Information diffusion is an important part of social network analysis, it is closely related to our life. As people recommend products to their friends, and the spread of thoughts, these are all "word of mouth" effects in information diffusion. The influence maximization problem is an important part of information propagation, the target of influence maximization is to find a small fixed set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The influence maximization problem has been proven to be NP-Hard, the current greedy algorithms work very slowly and can’t be applied to large scale social networks. Most of the seeds algorithms don’t take community structure into consideration, but the connections inside the community are tighter than connections outside the community. This paper proposes two new activating strategies under the independ cascade model and show their efficiency in both non-overlapping and overlapping community structures. Based on the inside activating strategy and community structure, this paper proposes a new influence maximization algorithm. The influence spread of the algorithm is approximate to the greedy algorithm, and it largely improves time efficiency, and it’s suitable for large networks.The main work in this paper is as follows:1. For the issue of nodes activating strategy during the propagation period, this paper proposes two new node activating strategies:inner activating strategy and probability activating strategy.2. For the issue of overlapping community detection, this paper improves the classic overlapping community detection algorithm based on label propagation. This paper redefines the relation strength between nodes, and define closeness between node and community, and use them to choose label in the process.3. For the issue of influence maximization with community structure problem, this paper proposes a new algorithm based on community structure. This algorithm includes two main procedures. First, detect all the communities in the network. Second, calculate the influence of each community.4. For the issue of ignoring time restriction when dealing with influence maximization problem, this paper proposes the problem of influence maximization with time restriction. This paper also proposes the greedy algorithm and compare with the community based algorithm.