基于时间片的物流网络影响力最大化研究

发布时间：2016-05-06 07:41

第一章  绪论

1.1  研究的背景和意义
随着电子商务的快速发展，物流在电子商务中所起的作用越来越大，人们的日常生活更离不开物流。随着信息技术的日新月异，物流企业借助信息技术使得物流能够更加快捷、方便的服务大众。 随着互联网技术的快速发展和广泛应用，虚拟社会越来越多的出现在我们眼前，比如通过微博所形成的的人际关系网络以及各式各样的社交网络。通过这些社交网络所表现出来的社会以及人际关系互动是许多领域的研究重点，在社会影响力传播中，社交网络作为传播的媒介，在个体之间相互影响、个体之间传播观点与信息等方面发挥着巨大的作用。一种信息可以在人群中巨大的蔓延，也有可能在很短时间内就消失。了解信息被人们所接受的程度是很有必要的，这就需要了解信息是如何在社会网络中动态的传播的：人们在何种程度上能够受到他的亲友的影响而且从事某种行为，“口碑效应”在什么程度下会发生。同样，在物流中也存在着物流网络，物流网络由物流企业的中转点和物品的流动所组成。物流网络表现了物流网点之间的关系。 影响力最大化模型模型研究是近来社会影响力领域的一个热点问题。“病毒式营销”开始只是针对为数不多的几个相对于其他个体具有“影响力”的个体。将一种商品首先推荐给这样的群体，然后在人群中进行扩散，大多数个体将会把此商品推荐给朋友，通过口口相传使这种商品得到推广。这种首先找到一定个数的具有“影响力”的节点，然后通过这些具有“影响力”的节点去影响别的节点的问题我们称之为影响力最大化问题。最早提出最大化问题的是作者 Richardson 和 Domingos 等人[1]，在文献[1]中给出了影响力最大化问题的详细定义并且给出了关于影响力最大化的评价指标，在社会网络和影响力领域引起了极大的关注。Kempe 等[2]作者第一次系统的研究了影响力最大化模型。文献[2]系统地总结了影响力最大化问题，并且详细总结了影响力最大化模型：独立级联模型（Independent Cascade 简称 IC）和线性阈值模型(Linear Thresholds 简称 LT)。
.........

1.2  国内外的发展及现状
随着电子商务以及信息技术在我国的快速发展，物流网络的研究对于我国物流产业的进步有着至关重要的作用，物流发展对经济具有很好的促进作用，，能够在很大程度上影响经济的发展。M. Christopher 在关于物流战略方案一书中指出了对物流网点规划和物流网络进行研究的重要意义。Bowerso 系统地研究了供应链管理中的物流网络设计与规划。Fisher 探讨了物流的规划问题，并从网络规划与节点规划两方面进行研究。Gandiur 将物流网络中的物流节点分成不同的类型，探讨不同类型的节点对物流流通的匹配性的影响，以及对物流流通运行效率的作用。相比于一些发达国家，中国的物流产业发展的比较落后，在借鉴国外先进技术和发展经验的同时，国内有越来越多的研究者投身到物流领域的研究中。物流网络在本质上属于社会网络，因为物流网络所涉及的是物流领域中个体与个体之间的相互关系，与社会网络相比只是个体身份存在着不同。 社会网络是反映社会群体中的个人之间的相互关系以及相互活动的图。社会网络在信息的传播以及影响力的传播方面起到了十分重要的作用。举例来说，一个新的产品或者创新的出现，会在短时间内没有得到广泛的应用而消失踪迹，或者是得到人们广泛的应用。如果我们想要了解在多大程度上类似的产品或者创新会得到人们的认可，那么了解这个想法或者创新如何动态的在社会网络中进行传播的就显得十分重要，也就是说，了解一个人在何种程度上会受到他的朋友或者同事的影响从而来接受类似的产品或者创新，即“口口相传”或者说“口碑效应”。关于诸如此类的网络扩散过程的研究很早就已经在社会学中展开。一些早期研究在发达国家或者发展中国家展开，研究的重点是通过分析相关数据带动医疗和农业的创新。另一方面，一些学者也在研究如何应用“口碑相传”和“病毒式营销”等扩散过程来进行新产品推广。 
.......

第二章  社会网络中的影响力概述

2.1  社会影响力与社会相关性
社会影响力是指一个人的情感、观点或者行为受到其他人影响而发生改变。James 等人在文献[3]中提出“three degrees of separation”来说明幸福感能够由一个人传递给他朋友的朋友，这正体现出了社会影响力的传播过程。R. Dunbar 等人[4]提到在这个世界上一个人能够影响超过 1000000 个人。 社会影响力反应了用户行为与用户社会联系之间的关系。Backstrom 等人[5]观察了网络社区的从属问题。他们主要研究一个用户加入网络社区这个行为和他的已经在这个网络社区中的朋友的数量之间的关系。Marlow 等人[6]研究观察了 Flickr 上标签的使用并且观察了用户设置标签的位置与和他朋友设置标签的位置的关系。这些研究验证了用户行为和社会联系之间的关联性的存在，但它们没有找到这种关联性的根源。 在社会网络中引起社会之间的相关性的因素可以分为三种：影响力（influence）；同质性（homophily）；环境因素（environment）。 Anagnostopoulos 等人在文献[7]中，证明了社会影响力是社会相关性的一种，以及社会影响力在社会中发挥着作用。Anagnostopoulos 等人的贡献：给出了社会影响力的含义，这对于社会网络中的社会影响力的定性研究有着很大帮助；提出两种能够证明社会影响力确实在社会网络中发挥作用的方法 shuffle 和 edge-reversal。 这两种方法首先对社会网络进行动态观察，每隔 T 时间单位取一个时间片。 shuffle：按照时间片的先后顺序对整个网络求一个社会相关性系数 ，然后打乱时间片的顺序再求一次社会相关系数 。如果两次 是相同的，那么社会影响力是不起作用的；如果两次 是不同的，社会影响力确实存在。 
.........

2.2  影响力研究趋势
2002 年，Richardson 和 Domingos 等人[1]将影响力最大化问题引入到社会网络领域后引起了很多学者的关注，作者给出了影响力最大化问题的详细定义并且给出了关于影响力最大化的评价指标，为后来的学者的研究提供了借鉴。随后在 2003 年，Kempe 等人[2]第一次比较系统的研究了影响力最大化模型。该篇文章系统地总结了影响力最大化问题，并且详细总结了影响力最大化模型：独立级联模型（Independent  Cascade 简称 IC）和线性阈值模型(Linear Thresholds 简称 LT)，并且证明了独立级联模型、线性阈值模型是 NP 难题，同时证明了两个模型的结果函数σ是一个子模函数，满足收益递减原则。Kempe 等人还提出了寻找影响力最大化模型中的种子节点集的算法--贪心算法[2]。贪心算法结构简单，易于理解，得到的种子节点很稳定，但贪心算法同时时间复杂度非常高，这使得贪心算法并不适合在大型网络中使用。 目前，社会网络中的影响力主要研究方向：(1)  寻找以及确定具有影响力的个体；(2)  影响力最大化问题。其中，第二个研究方向包含第一个研究方向，因为影响力最大化问题首先要解决的问题是找到种子节点，即具有影响力的节点。 
...........

第三章 影响力最大化问题 ......... 14 
3.1 影响力最大化问题描述 ........... 14
3.2 影响力最大化问题的模型 ......... 14 
3.2.1 独立级联模型 ..... 14 
3.2.2 线性阈值模型 ..... 15 
3.3 影响力最大化问题的算法 ......... 16 
3.3.1 贪心算法 ......... 16 
3.3.2 探索式算法 ....... 17 
3.4 本章小节 ....... 18 
第四章 基于亲和传播的影响力分析 ......... 19 
4.1 问题描述 ....... 19 
4.2 亲和传播聚类算法简介 ........... 19 
4.3 基于亲和传播的影响力 ........... 21 
4.3.1 算法思想 ......... 21 
4.3.2 算法描述 ......... 23 
4.4 实验仿真 ....... 23
4.5 本章小节 ........ 25 
第五章 基于时间片网络的独立级联模型 ..... 26 
5.1 独立级联模型 .... 26 
5.1.1 静态物流网络中的独立级联模型 ..... 26 
5.1.2 模型分析以及存在问题 ..... 27 
5.2 基于时间片的独立级联模型 ....... 28 
5.3 实验仿真 ....... 32
5.4 本章小节 ........ 41 

第五章  基于时间片网络的独立级联模型

Richardson 和 Domingos 等人将影响力最大化问题引入到社会网络领域后引起了很多学者的关注。Kempe 等人提出的独立级联模型是在一个静态的社会网络中来进行扩散的，显然，社会网络是随着时间不断的变化的，静态网络不能反映网络的变化。本章将时间片网络引入到独立级联模型中，并结合第三章中的基于亲和传播的影响力以及物流网络，对基于时间片网络的独立模型进行分析。 

5.1 独立级联模型

5.1.1  静态物流网络中的独立级联模型

在一个有向边组成的物流网络中规定网络中的节点有且只有两种状态：激活态（active，或称感染态，表明此节点已经受到它的邻居节点的影响而去做了某项事情）和未激活态（inactive，或称未感染态，表明此节点暂时没有收到它的邻居节点的影响去做某项事情）。每个节点只能由未激活态转变为激活态，而不能由激活态转变为未激活态。物流网络中的有向边代表了网络中的节点以往的联系：如果两个节点之间有一条有向边说明这两个节点之前发生过某种联系。这种以往的联系可以来表示一个节点能够在多大程度上影响有向边所指向节点。在独立级联模型中，这种影响的程度用概率值来表示。 在独立级联模型中，节点 u 在某一轮扩散 t（t 并不代表时间而是代表节点 v 在第 t 轮扩散中被激活）中被激活，那么节点 u 就有一次机会去激活它的邻居节点 v。在 t+1 轮扩散中，u 能否成功激活 v 依赖于概率   （   是模型的一个参数，即上述所述影响力概率值）。如果，v 有多个邻居节点处于激活状态，那么这些节点对 v 的影响是随机的、独立的。但是不管 v 能否成功激活，它都不能对 v 以后的状态造成影响。在独立级联模型中，实际情况下每个节点受到它的邻居节点的影响的难易程度是不同的，即   的值应该是不同的，但为了简化模型，把每个节点的   设置成统一值。图 5.1 画出了经过两轮扩散的独立级联模型。首先，A 被选为种子节点进行第一轮的扩散，A 成功激活了它的邻居节点 B 和 D，而 C 和 E 并没有被激活。

.....

总结

本文开始细致的总结了近几年社会影响力研究方向的主要研究内容以及物流网络主要研究内容，对影响力最大化问题的模型和确定种子节点的算法进行了细致的调研，通过越多大量文献总结出来近几年社会影响力的研究趋势。 在本文的第三章中分析了现有的独立级联模型中存在的一个问题：将每两个节点之间的激活概率设定为统一的值，而现实情况中物流网络中的每对节点之间的激活概率不可能都是完全相同的。针对这一问题在第三章本文提出使用亲和传播方法来进行节点之间的影响力概率值的量化。 在本文的第四章中分析了现有的独立级联模型中的一个问题：现有的独立级联模型都是在静态网络中扩展的，而现实中的物流网络是随时间不断的变化的，静态网络不能反映出网络随时间变化的情况。时间片网络是由多个按时间序列排序的网络构成的社会网络可以反映出网络中的节点随着时间的变化而变化。基于此本文提出在基于时间片网络中进行独立级联模型的扩散，并通过实验对两种网络中的独立级联模型扩散进行了对比，此外还将一些在静态网络中比较经典的算法引入到基于时间片的网络中。
.........
参考文献(略) 

本文编号：42487