面向大规模社交网络的信息传播模型及其应用研究

近年来,社交网络得到了极大的发展,成为人们消磨休闲时光、获取最新信息、了解朋友动态的重要工具,构成了人们网络在线生活的重要一部分。社交网络的出现带来了各种可能性,如美国总统奥巴马利用社交网络成功赢得两次竞选,韩国音乐人PSY利用社交网络传播其舞曲视频《江南style》突破了10亿次点击的吉尼斯记录。社交网络如何进行信息传播,以及如何利用社交网络推动信息的快速有效传播,成为目前学术界研究的热点。本文系统研究了社交网络上的信息传播模型,其研究成果对于改进社交网络上的信息服务具有重要的应用价值。 首先,本文提出一种信息传播的快速计算模型：线性影响力传播模型。信息传播模型是描述社交网络上信息传播过程和进行信息传播计算的基础。尽管近年来对信息传播模型的研究较多,如独立级联模型和线性阈值模型,但这些模型都存在许多缺点,如不可解析,没有闭形式解,效率太低等。这些缺点导致它们只能应用在小规模网络中,然而实际环境中的社交网络(如Facebook、 Twitter等)常常拥有数以亿计的用户规模!为此,本文提出了一种线性影响力模型。该模型能够在线性时间内完成信息传播计算,同时该模型具有可调节性,通过调节模型参数可以使得该模型的信息传播结果非常逼近传统模型。在一个规模达到千万的实际社交网络上的测试表明,线性影响力模型能够严格逼近传统模型的传播效果,而且仅需要付出比传统模型低得多的计算代价。 其次,本文基于线性影响力模型提出PageRank的改进算法。PageRank算法是用于计算网络中节点权威值的经典算法。自Larry Page和Seige Brin提出以来,已成为网络研究中最重要的算法之一,也是互联网巨擎Google的立身之本。本文从影响力传播的角度重新分析了这一算法,并得出“网络中节点权威值就是该节点对网络中所有节点的影响力之和”这一本质结论。同时还论证了PageRank算法只是对网络中节点权威值的一种快速近似计算,并给出了多种针对节点权威值计算的精确算法,如规范PageRank算法和先验Pagerank算法等。本文在科学家合作网络上对各种PageRank算法进行了对比,结果表明规范PageRank算法和先验PageRank算法均能取得比传统PageRank更好的结果。 然后,本文基于线性影响力传播模型和PageRank算法的本质联系,提出一种用于快速计算任意群体影响力(权威值)的群体PageRank算法。群体PageRank算法是对PageRank算法一种维度上的推广。众所周知,Pagerank算法是计算节点权威值的经典算法,然而如何计算一个群体的权威值呢?如美国民主党和共和党在竞选之时,如何计算两党在民众中的权威值从而预测谁将赢得最终大选?因此,群体权威值计算具有重要的应用价值。本文从影响力传播的角度分析了群体的权威值的计算方法,同时基于影响力传播模型和PageRank算法的关系提出了群体PageRank算法,用于快速计算大规模社交网络上群体权威值。在真实数据上进行的大量测试表明,群体PageRank算法能在常数时间内计算任意群体的群体权威值,同时计算结果能够一致逼近真实结果。 最后,本文将线性影响力传播模型和群体PageRank算法用于病毒营销设计,为社交网络上的信息传播提供最佳策略。病毒营销,亦称“口碑效应”,致力于寻找一组社交网络用户为某种产品代言,希望这组用户能在网络上造成多米诺骨牌效应,使得该产品的好口碑能口口相传到到最大规模的网络群体中,从而为产品销售带来最佳效果。本文基于线性影响力传播模型和群体PageRank算法提出了两种病毒营销算法,Linear算法和Bound算法。同时,在多个真实数据上进行的实验测试结果表明,Linear算法和Bound算法均能在时间和效果上胜过当前最新算法。其中,Bound算法甚至只需要常数时间代价就能为病毒营销设计出最佳策略,尤其适合应用在超大规模的社交网络上。