Journal of Frontiers of Computer Science and Technology ›› 2012, Vol. 6 ›› Issue (9): 769-778.DOI: 10.3778/j.issn.1673-9418.2012.09.001

Previous Articles     Next Articles

Sentiment Influence Maximization Model for Microblogging System

OU Gaoyan1,2, CHEN Wei1,2+, WANG Tengjiao1,2, LEI Kai3, YANG Dongqing1,2   

  1. 1. Key Laboratory of High Confidence Software Technologies, Ministry of Education, Beijing 100871, China
    2. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
    3. The Shenzhen Key Lab for Cloud Computing Technology and Applications, Shenzhen Graduate School, Peking University, Shenzhen, Guangdong 518055, China
  • Online:2012-09-01 Published:2012-09-03

面向微博的情感影响最大化模型

欧高炎1,2,陈  薇1,2+,王腾蛟1,2,雷  凯3,杨冬青1,2   

  1. 1. 高可信软件技术教育部重点实验室,北京 100871
    2. 北京大学 信息科学技术学院,北京 100871
    3. 北京大学 深圳研究生院 深圳市云计算关键技术与应用重点实验室,广东 深圳 518055

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模型能够有效地找出情感影响最大化的节点集,同时具有很高的扩展性。

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