Research On Mining Top-k Influential Nodes Based On Community Structure

A social network is composed of nodes representing individuals and edges corresponding to various relation types. It is an issue to find a K-node seed set of influential nodes that can maximize the spread of influence in a social network according to a chosen diffusion model. Normally, this problem is called as influence maximization, or target set selection. It has great practical significance in the marketing, the ad publishing, the virus spreading, and the public opinions pre-warning.Because individuals within a community are more likely to influence each other, first, we investigate the problem of community detection. It is found that most existing algorithms detect communities with misclassified nodes and peripheries, so a community detection algorithm based on the similarity sequence is proposed, names as ACSS. ACSS is tested on some computer-generated networks and some real networks. Compared with other algorithms, the experimental results confirm the validity of this approach.Based on the detected community structure, we propose an influence maximization algorithm named as IMBC under the linear threshold model. First, we use a k-shell decomposition method to evaluate nodes' potential influence. Then we improve the greedy algorithm by discarding some unnecessary calculations. Finally, the influential nodes are selected in communities based on the idea of dynamic programming. IMBC is tested on some real network datasets. The experimental results show that IMBC can achieve both high efficiency and high accuracy compared with the existing representative algorithms.To confirm the scientificity and validity of IMBC, IMBC is tested on the Sina Weibo dataset. ACSS is firstly applied to detect the communities in the weibo network. Then on the basis of the detected community structure, IMBC is used to find the Top-K influential nodes. Finally, the largest scale community is selected to simulate the information diffusion in the form of “word-of-mouth”, reflecting the social reality.