论文部分内容阅读
近几年来,随着互联网的发展,在线社交网络(如Facebook、Twitter等)的成功应用,网络上存在大规模的真实社会数据,催生了社交网络在计算机领域的蓬勃发展。在信息传播研究领域,病毒式营销(viral marketing)是一个广为研究的问题。在社交网络中病毒式营销的一个具体方案是找出最有影响力的用户,将这些用户作为信息的源头,通过口头传播方式使得信息最终能够到达网络的大部分,这也就是影响最大化问题的原型。 然而,这种病毒式营销使用的是“广而告之”的广告模式,这种广告模式在近几年的实践中,取得的效果不甚理想。为此一种与“广而告之”对应的新型网络广告模式-----“窄告”被提出。窄告会根据浏览者的偏好、使用习性、地理位置、访问历史等信息,有针对性地将广告投放到真正感兴趣的用户面前。基于以上考虑,本文将病毒式营销手段和窄告这种个性化的广告模式结合起来,提出了带属性的影响最大化问题。 针对这个问题,本文提出了一种概率和覆盖算法(Sum of Probability CoveredAlgorithm,简称SoPCA)和两种基于局部社区的算法,社区识别算法分别是Community-Based Algorithm(CBA)和Improved Community-Based Algorithm(ICBA)。其中ICBA是对CBA在时间复杂度上的改进算法。基于以上算法的研究成果,本文设计并实现了社交网络影响力节点挖掘原型系统。 本文在六个数据集和拓展独立级联传播模型上进行了实验,结果表明:(a)为避免影响范围重叠问题,在算法中引入覆盖距离是有效的,最佳覆盖距离的选取受边上影响概率影响;(b)本文提出的算法的影响范围优于其他启发式算法,且网络中目标节点(与商品目标受众属性相似度不为0的节点)数目越少,算法的优势越明显;(c)在本文提出的三个算法中,ICBA的影响范围最佳,其次是CBA,SoPCA最差;在时间性能方面,SoPCA最快,其次是ICBA,CBA运行时间最长。