ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (2): 382-393.doi: 10.7544/issn1000-1239.2017.20151118

• 信息处理 • 上一篇    下一篇



  1. 1(中南大学信息科学与工程学院 长沙 410083); 2(中南大学软件学院 长沙 410075) (
  • 出版日期: 2017-02-01
  • 基金资助: 

An Optimized Credit Distribution Model in Social Networks with Time-Delay Constraint

Deng Xiaoheng1, Cao Dejuan1, Pan Yan1, Shen Hailan1, Chen Zhigang2   

  1. 1(School of Information Science and Engineering, Central South University, Changsha 410083);2(School of Software, Central South University, Changsha 410075)
  • Online: 2017-02-01

摘要: 基于时延约束的影响力最大化问题(influence maximization with time-delay constraint, IMTC)定义为在时延约束条件下,选取网络中一部分初始用户,使得影响力传播过程结束后网络中被成功影响的用户数量最多.现有研究工作主要依据网络结构优化影响力传播模型,或改进启发式算法提高初始节点的选取质量,影响力传播过程中的时间延迟特性及时延约束条件往往被忽略.针对这点不足,基于时延约束的信用分布模型(credit distribution with time-delay constraint model, CDTC)综合考虑见面概率和条件激活概率对信用分配进行优化定义,同时将相邻节点之间不断见面并激活对信用分配的阻碍作用映射到传播增量路径中,最后根据信用分布函数,使用基于时延约束的贪心算法GA-TC,递归选取边际收益最大的节点组成初始节点集合.实验结果表明:在CDTC模型上使用GA-TC算法不仅能够保证初始节点的选取质量,而且具有更高的执行效率及更好的行为执行预测能力.

关键词: 社会网络, 影响力最大化, 时延约束, 信用分布, 贪心算法

Abstract: The research of influence maximization in social networks is emerging as a promising opportunity for successful viral marketing. Influence maximization with time-delay constraint (IMTC) is to identify a set of initial individuals who will influence others and lead to a maximum value of influence spread consequence under time-delay constraint. Most of the existing models focus on optimizing the simulation consequence of influence spread, and time-delay factors and time-delay constraint are always ignored. The credit distribution with time-delay constraint model (CDTC) incorporates the meeting and activation probabilities to optimize the distribution of credit considering time-delay constraint, and utilizes the optimized relationships of meeting and activation probabilities to evaluate the ability to influence on adjacent individuals. Furthermore, the obstructive effect due to repeated attempts of meeting and activation is reflected by the length of increased propagation paths. After assigning the credit along with the increased propagation paths learned from users action-logs, the nodes which obtain maximal marginal gain are selected to form the seed set by the greedy algorithm with time-delay constraint (GA-TC). The experimental results based on real datasets show that the proposed approach is more accurate and efficient compared with other related methods.

Key words: social networks, influence maximization, time-delay constraint, credit distribution, greedy algorithm