Abstract: Influence maximization is a problem of finding a subset of nodes in a social network, which can maximize the influence spread. Most existing influence maximization algorithms merely rely on the social graph. This paper proposes a new sentiment influence model, named sentiment influence distribution (SID) model. SID model simultaneously utilizes the social graph, user interaction data and sentiment of microblog posts. The paper demonstrates
that the sentiment influence maximization problem is an NP-hard problem under the SID model and the sentiment influence function is monotone and submodular. It also develops an approximate algorithm which can provide high performance guarantee. Experimental results from real data show the effectiveness of the proposed SID model compared to the traditional IC model and LT model.

Key words: sentiment analysis, social networks, influence maximization

摘要： 社交网络中影响最大化问题是寻找具有最大影响范围的节点。影响最大化的大部分求解算法仅仅依赖社交网络图。基于微博的转发关系树和微博内容的情感倾向性，以及用户的社交网络图，提出了一个能够刻画用户情感影响的情感影响最大化模型——情感影响分配模型（sentiment influence distribution，SID），证明了SID模型下的情感影响最大化问题是一个NP难问题，给出了一个具有精度保证的贪心算法。在真实的微博数据上的实验结果表明，SID模型能够有效地找出情感影响最大化的节点集，同时具有很高的扩展性。

关键词: 情感分析, 社交网络, 影响最大化