关键词: 在线社交网络, 影响力抑制最大化, 启发式算法, 多信息, 竞争独立级联模型

Abstract: While online social networks provide people with convenient information interaction， they also widely spread negative information thus cause panic in the society. Therefore， it is urgent to take reasonable and effective strategies to block the spread of negative information in the network to the greatest extent. In COICM model， this paper studies the problem of negative information blocking maximization and designs a method to compute the positive（negative） activation probabilities of nodes based on maximum influence in-arborescence， and then proposes a heuristic algorithm to solve this problem. The core idea is that， firstly， distinguishing the state of nodes in the local impact in-tree， that is， the node is positive（negative） activated at the current time， has been positive or negative activated before the current time and remains inactive until the current time， and the five states constitute the sample space of the events occurring at the node up to the current time. Then use the compound event probability operation method to work out the probability expression of positive （negative） activation of the node at the current time as well as calculate the negative activation probability of the root node through recursive calculation. Finally， take the sum of the negative activation probabilities of all nodes in the network as the influence of the negative seed set. The algorithm uses the greedy framework to iteratively select the node with the largest negative information blocking as the node to propagate positive information. Compared with existing algorithms on four real social network datasets of different sizes， the results show that the proposed algorithm has better negative information blocking effect， and can be applied to large-scale networks.

Key words:  , online social networks； influence blocking maximization； heuristic algorithm； multi-information； competitive independent cascade model