第一章  緒論

1.1  研究的背景和意義
隨著電子商務(wù)的快速發(fā)展，物流在電子商務(wù)中所起的作用越來(lái)越大，人們的日常生活更離不開物流。隨著信息技術(shù)的日新月異，物流企業(yè)借助信息技術(shù)使得物流能夠更加快捷、方便的服務(wù)大眾。 隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展和廣泛應(yīng)用，虛擬社會(huì)越來(lái)越多的出現(xiàn)在我們眼前，比如通過微博所形成的的人際關(guān)系網(wǎng)絡(luò)以及各式各樣的社交網(wǎng)絡(luò)。通過這些社交網(wǎng)絡(luò)所表現(xiàn)出來(lái)的社會(huì)以及人際關(guān)系互動(dòng)是許多領(lǐng)域的研究重點(diǎn)，在社會(huì)影響力傳播中，社交網(wǎng)絡(luò)作為傳播的媒介，在個(gè)體之間相互影響、個(gè)體之間傳播觀點(diǎn)與信息等方面發(fā)揮著巨大的作用。一種信息可以在人群中巨大的蔓延，也有可能在很短時(shí)間內(nèi)就消失。了解信息被人們所接受的程度是很有必要的，這就需要了解信息是如何在社會(huì)網(wǎng)絡(luò)中動(dòng)態(tài)的傳播的：人們?cè)诤畏N程度上能夠受到他的親友的影響而且從事某種行為，“口碑效應(yīng)”在什么程度下會(huì)發(fā)生。同樣，在物流中也存在著物流網(wǎng)絡(luò)，物流網(wǎng)絡(luò)由物流企業(yè)的中轉(zhuǎn)點(diǎn)和物品的流動(dòng)所組成。物流網(wǎng)絡(luò)表現(xiàn)了物流網(wǎng)點(diǎn)之間的關(guān)系。 影響力最大化模型模型研究是近來(lái)社會(huì)影響力領(lǐng)域的一個(gè)熱點(diǎn)問題�！安《臼綘I(yíng)銷”開始只是針對(duì)為數(shù)不多的幾個(gè)相對(duì)于其他個(gè)體具有“影響力”的個(gè)體。將一種商品首先推薦給這樣的群體，然后在人群中進(jìn)行擴(kuò)散，大多數(shù)個(gè)體將會(huì)把此商品推薦給朋友，通過口口相傳使這種商品得到推廣。這種首先找到一定個(gè)數(shù)的具有“影響力”的節(jié)點(diǎn)，然后通過這些具有“影響力”的節(jié)點(diǎn)去影響別的節(jié)點(diǎn)的問題我們稱之為影響力最大化問題。最早提出最大化問題的是作者 Richardson 和 Domingos 等人[1]，在文獻(xiàn)[1]中給出了影響力最大化問題的詳細(xì)定義并且給出了關(guān)于影響力最大化的評(píng)價(jià)指標(biāo)，在社會(huì)網(wǎng)絡(luò)和影響力領(lǐng)域引起了極大的關(guān)注。Kempe 等[2]作者第一次系統(tǒng)的研究了影響力最大化模型。文獻(xiàn)[2]系統(tǒng)地總結(jié)了影響力最大化問題，并且詳細(xì)總結(jié)了影響力最大化模型：獨(dú)立級(jí)聯(lián)模型（Independent Cascade 簡(jiǎn)稱 IC）和線性閾值模型(Linear Thresholds 簡(jiǎn)稱 LT)。
.........

1.2  國(guó)內(nèi)外的發(fā)展及現(xiàn)狀
隨著電子商務(wù)以及信息技術(shù)在我國(guó)的快速發(fā)展，物流網(wǎng)絡(luò)的研究對(duì)于我國(guó)物流產(chǎn)業(yè)的進(jìn)步有著至關(guān)重要的作用，物流發(fā)展對(duì)經(jīng)濟(jì)具有很好的促進(jìn)作用，，能夠在很大程度上影響經(jīng)濟(jì)的發(fā)展。M. Christopher 在關(guān)于物流戰(zhàn)略方案一書中指出了對(duì)物流網(wǎng)點(diǎn)規(guī)劃和物流網(wǎng)絡(luò)進(jìn)行研究的重要意義。Bowerso 系統(tǒng)地研究了供應(yīng)鏈管理中的物流網(wǎng)絡(luò)設(shè)計(jì)與規(guī)劃。Fisher 探討了物流的規(guī)劃問題，并從網(wǎng)絡(luò)規(guī)劃與節(jié)點(diǎn)規(guī)劃兩方面進(jìn)行研究。Gandiur 將物流網(wǎng)絡(luò)中的物流節(jié)點(diǎn)分成不同的類型，探討不同類型的節(jié)點(diǎn)對(duì)物流流通的匹配性的影響，以及對(duì)物流流通運(yùn)行效率的作用。相比于一些發(fā)達(dá)國(guó)家，中國(guó)的物流產(chǎn)業(yè)發(fā)展的比較落后，在借鑒國(guó)外先進(jìn)技術(shù)和發(fā)展經(jīng)驗(yàn)的同時(shí)，國(guó)內(nèi)有越來(lái)越多的研究者投身到物流領(lǐng)域的研究中。物流網(wǎng)絡(luò)在本質(zhì)上屬于社會(huì)網(wǎng)絡(luò)，因?yàn)槲锪骶W(wǎng)絡(luò)所涉及的是物流領(lǐng)域中個(gè)體與個(gè)體之間的相互關(guān)系，與社會(huì)網(wǎng)絡(luò)相比只是個(gè)體身份存在著不同。 社會(huì)網(wǎng)絡(luò)是反映社會(huì)群體中的個(gè)人之間的相互關(guān)系以及相互活動(dòng)的圖。社會(huì)網(wǎng)絡(luò)在信息的傳播以及影響力的傳播方面起到了十分重要的作用。舉例來(lái)說，一個(gè)新的產(chǎn)品或者創(chuàng)新的出現(xiàn)，會(huì)在短時(shí)間內(nèi)沒有得到廣泛的應(yīng)用而消失蹤跡，或者是得到人們廣泛的應(yīng)用。如果我們想要了解在多大程度上類似的產(chǎn)品或者創(chuàng)新會(huì)得到人們的認(rèn)可，那么了解這個(gè)想法或者創(chuàng)新如何動(dòng)態(tài)的在社會(huì)網(wǎng)絡(luò)中進(jìn)行傳播的就顯得十分重要，也就是說，了解一個(gè)人在何種程度上會(huì)受到他的朋友或者同事的影響從而來(lái)接受類似的產(chǎn)品或者創(chuàng)新，即“口口相傳”或者說“口碑效應(yīng)”。關(guān)于諸如此類的網(wǎng)絡(luò)擴(kuò)散過程的研究很早就已經(jīng)在社會(huì)學(xué)中展開。一些早期研究在發(fā)達(dá)國(guó)家或者發(fā)展中國(guó)家展開，研究的重點(diǎn)是通過分析相關(guān)數(shù)據(jù)帶動(dòng)醫(yī)療和農(nóng)業(yè)的創(chuàng)新。另一方面，一些學(xué)者也在研究如何應(yīng)用“口碑相傳”和“病毒式營(yíng)銷”等擴(kuò)散過程來(lái)進(jìn)行新產(chǎn)品推廣。 
.......

第二章  社會(huì)網(wǎng)絡(luò)中的影響力概述

2.1  社會(huì)影響力與社會(huì)相關(guān)性
社會(huì)影響力是指一個(gè)人的情感、觀點(diǎn)或者行為受到其他人影響而發(fā)生改變。James 等人在文獻(xiàn)[3]中提出“three degrees of separation”來(lái)說明幸福感能夠由一個(gè)人傳遞給他朋友的朋友，這正體現(xiàn)出了社會(huì)影響力的傳播過程。R. Dunbar 等人[4]提到在這個(gè)世界上一個(gè)人能夠影響超過 1000000 個(gè)人。 社會(huì)影響力反應(yīng)了用戶行為與用戶社會(huì)聯(lián)系之間的關(guān)系。Backstrom 等人[5]觀察了網(wǎng)絡(luò)社區(qū)的從屬問題。他們主要研究一個(gè)用戶加入網(wǎng)絡(luò)社區(qū)這個(gè)行為和他的已經(jīng)在這個(gè)網(wǎng)絡(luò)社區(qū)中的朋友的數(shù)量之間的關(guān)系。Marlow 等人[6]研究觀察了 Flickr 上標(biāo)簽的使用并且觀察了用戶設(shè)置標(biāo)簽的位置與和他朋友設(shè)置標(biāo)簽的位置的關(guān)系。這些研究驗(yàn)證了用戶行為和社會(huì)聯(lián)系之間的關(guān)聯(lián)性的存在，但它們沒有找到這種關(guān)聯(lián)性的根源。 在社會(huì)網(wǎng)絡(luò)中引起社會(huì)之間的相關(guān)性的因素可以分為三種：影響力（influence）；同質(zhì)性（homophily）；環(huán)境因素（environment）。 Anagnostopoulos 等人在文獻(xiàn)[7]中，證明了社會(huì)影響力是社會(huì)相關(guān)性的一種，以及社會(huì)影響力在社會(huì)中發(fā)揮著作用。Anagnostopoulos 等人的貢獻(xiàn)：給出了社會(huì)影響力的含義，這對(duì)于社會(huì)網(wǎng)絡(luò)中的社會(huì)影響力的定性研究有著很大幫助；提出兩種能夠證明社會(huì)影響力確實(shí)在社會(huì)網(wǎng)絡(luò)中發(fā)揮作用的方法 shuffle 和 edge-reversal。 這兩種方法首先對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)觀察，每隔 T 時(shí)間單位取一個(gè)時(shí)間片。 shuffle：按照時(shí)間片的先后順序?qū)φ麄�(gè)網(wǎng)絡(luò)求一個(gè)社會(huì)相關(guān)性系數(shù) ，然后打亂時(shí)間片的順序再求一次社會(huì)相關(guān)系數(shù) 。如果兩次 是相同的，那么社會(huì)影響力是不起作用的；如果兩次 是不同的，社會(huì)影響力確實(shí)存在。 
.........

2.2  影響力研究趨勢(shì)
2002 年，Richardson 和 Domingos 等人[1]將影響力最大化問題引入到社會(huì)網(wǎng)絡(luò)領(lǐng)域后引起了很多學(xué)者的關(guān)注，作者給出了影響力最大化問題的詳細(xì)定義并且給出了關(guān)于影響力最大化的評(píng)價(jià)指標(biāo)，為后來(lái)的學(xué)者的研究提供了借鑒。隨后在 2003 年，Kempe 等人[2]第一次比較系統(tǒng)的研究了影響力最大化模型。該篇文章系統(tǒng)地總結(jié)了影響力最大化問題，并且詳細(xì)總結(jié)了影響力最大化模型：獨(dú)立級(jí)聯(lián)模型（Independent  Cascade 簡(jiǎn)稱 IC）和線性閾值模型(Linear Thresholds 簡(jiǎn)稱 LT)，并且證明了獨(dú)立級(jí)聯(lián)模型、線性閾值模型是 NP 難題，同時(shí)證明了兩個(gè)模型的結(jié)果函數(shù)σ是一個(gè)子模函數(shù)，滿足收益遞減原則。Kempe 等人還提出了尋找影響力最大化模型中的種子節(jié)點(diǎn)集的算法--貪心算法[2]。貪心算法結(jié)構(gòu)簡(jiǎn)單，易于理解，得到的種子節(jié)點(diǎn)很穩(wěn)定，但貪心算法同時(shí)時(shí)間復(fù)雜度非常高，這使得貪心算法并不適合在大型網(wǎng)絡(luò)中使用。 目前，社會(huì)網(wǎng)絡(luò)中的影響力主要研究方向：(1)  尋找以及確定具有影響力的個(gè)體；(2)  影響力最大化問題。其中，第二個(gè)研究方向包含第一個(gè)研究方向，因?yàn)橛绊懥ψ畲蠡瘑栴}首先要解決的問題是找到種子節(jié)點(diǎn)，即具有影響力的節(jié)點(diǎn)。 
...........

第三章 影響力最大化問題 ......... 14 
3.1 影響力最大化問題描述 ........... 14
3.2 影響力最大化問題的模型 ......... 14 
3.2.1 獨(dú)立級(jí)聯(lián)模型 ..... 14 
3.2.2 線性閾值模型 ..... 15 
3.3 影響力最大化問題的算法 ......... 16 
3.3.1 貪心算法 ......... 16 
3.3.2 探索式算法 ....... 17 
3.4 本章小節(jié) ....... 18 
第四章 基于親和傳播的影響力分析 ......... 19 
4.1 問題描述 ....... 19 
4.2 親和傳播聚類算法簡(jiǎn)介 ........... 19 
4.3 基于親和傳播的影響力 ........... 21 
4.3.1 算法思想 ......... 21 
4.3.2 算法描述 ......... 23 
4.4 實(shí)驗(yàn)仿真 ....... 23
4.5 本章小節(jié) ........ 25 
第五章 基于時(shí)間片網(wǎng)絡(luò)的獨(dú)立級(jí)聯(lián)模型 ..... 26 
5.1 獨(dú)立級(jí)聯(lián)模型 .... 26 
5.1.1 靜態(tài)物流網(wǎng)絡(luò)中的獨(dú)立級(jí)聯(lián)模型 ..... 26 
5.1.2 模型分析以及存在問題 ..... 27 
5.2 基于時(shí)間片的獨(dú)立級(jí)聯(lián)模型 ....... 28 
5.3 實(shí)驗(yàn)仿真 ....... 32
5.4 本章小節(jié) ........ 41 

第五章  基于時(shí)間片網(wǎng)絡(luò)的獨(dú)立級(jí)聯(lián)模型

Richardson 和 Domingos 等人將影響力最大化問題引入到社會(huì)網(wǎng)絡(luò)領(lǐng)域后引起了很多學(xué)者的關(guān)注。Kempe 等人提出的獨(dú)立級(jí)聯(lián)模型是在一個(gè)靜態(tài)的社會(huì)網(wǎng)絡(luò)中來(lái)進(jìn)行擴(kuò)散的，顯然，社會(huì)網(wǎng)絡(luò)是隨著時(shí)間不斷的變化的，靜態(tài)網(wǎng)絡(luò)不能反映網(wǎng)絡(luò)的變化。本章將時(shí)間片網(wǎng)絡(luò)引入到獨(dú)立級(jí)聯(lián)模型中，并結(jié)合第三章中的基于親和傳播的影響力以及物流網(wǎng)絡(luò)，對(duì)基于時(shí)間片網(wǎng)絡(luò)的獨(dú)立模型進(jìn)行分析。 

5.1 獨(dú)立級(jí)聯(lián)模型

5.1.1  靜態(tài)物流網(wǎng)絡(luò)中的獨(dú)立級(jí)聯(lián)模型

在一個(gè)有向邊組成的物流網(wǎng)絡(luò)中規(guī)定網(wǎng)絡(luò)中的節(jié)點(diǎn)有且只有兩種狀態(tài)：激活態(tài)（active，或稱感染態(tài)，表明此節(jié)點(diǎn)已經(jīng)受到它的鄰居節(jié)點(diǎn)的影響而去做了某項(xiàng)事情）和未激活態(tài)（inactive，或稱未感染態(tài)，表明此節(jié)點(diǎn)暫時(shí)沒有收到它的鄰居節(jié)點(diǎn)的影響去做某項(xiàng)事情）。每個(gè)節(jié)點(diǎn)只能由未激活態(tài)轉(zhuǎn)變?yōu)榧せ顟B(tài)，而不能由激活態(tài)轉(zhuǎn)變?yōu)槲醇せ顟B(tài)。物流網(wǎng)絡(luò)中的有向邊代表了網(wǎng)絡(luò)中的節(jié)點(diǎn)以往的聯(lián)系：如果兩個(gè)節(jié)點(diǎn)之間有一條有向邊說明這兩個(gè)節(jié)點(diǎn)之前發(fā)生過某種聯(lián)系。這種以往的聯(lián)系可以來(lái)表示一個(gè)節(jié)點(diǎn)能夠在多大程度上影響有向邊所指向節(jié)點(diǎn)。在獨(dú)立級(jí)聯(lián)模型中，這種影響的程度用概率值來(lái)表示。 在獨(dú)立級(jí)聯(lián)模型中，節(jié)點(diǎn) u 在某一輪擴(kuò)散 t（t 并不代表時(shí)間而是代表節(jié)點(diǎn) v 在第 t 輪擴(kuò)散中被激活）中被激活，那么節(jié)點(diǎn) u 就有一次機(jī)會(huì)去激活它的鄰居節(jié)點(diǎn) v。在 t+1 輪擴(kuò)散中，u 能否成功激活 v 依賴于概率   （   是模型的一個(gè)參數(shù)，即上述所述影響力概率值）。如果，v 有多個(gè)鄰居節(jié)點(diǎn)處于激活狀態(tài)，那么這些節(jié)點(diǎn)對(duì) v 的影響是隨機(jī)的、獨(dú)立的。但是不管 v 能否成功激活，它都不能對(duì) v 以后的狀態(tài)造成影響。在獨(dú)立級(jí)聯(lián)模型中，實(shí)際情況下每個(gè)節(jié)點(diǎn)受到它的鄰居節(jié)點(diǎn)的影響的難易程度是不同的，即   的值應(yīng)該是不同的，但為了簡(jiǎn)化模型，把每個(gè)節(jié)點(diǎn)的   設(shè)置成統(tǒng)一值。圖 5.1 畫出了經(jīng)過兩輪擴(kuò)散的獨(dú)立級(jí)聯(lián)模型。首先，A 被選為種子節(jié)點(diǎn)進(jìn)行第一輪的擴(kuò)散，A 成功激活了它的鄰居節(jié)點(diǎn) B 和 D，而 C 和 E 并沒有被激活。

.....

總結(jié)

本文開始細(xì)致的總結(jié)了近幾年社會(huì)影響力研究方向的主要研究?jī)?nèi)容以及物流網(wǎng)絡(luò)主要研究?jī)?nèi)容，對(duì)影響力最大化問題的模型和確定種子節(jié)點(diǎn)的算法進(jìn)行了細(xì)致的調(diào)研，通過越多大量文獻(xiàn)總結(jié)出來(lái)近幾年社會(huì)影響力的研究趨勢(shì)。 在本文的第三章中分析了現(xiàn)有的獨(dú)立級(jí)聯(lián)模型中存在的一個(gè)問題：將每?jī)蓚�(gè)節(jié)點(diǎn)之間的激活概率設(shè)定為統(tǒng)一的值，而現(xiàn)實(shí)情況中物流網(wǎng)絡(luò)中的每對(duì)節(jié)點(diǎn)之間的激活概率不可能都是完全相同的。針對(duì)這一問題在第三章本文提出使用親和傳播方法來(lái)進(jìn)行節(jié)點(diǎn)之間的影響力概率值的量化。 在本文的第四章中分析了現(xiàn)有的獨(dú)立級(jí)聯(lián)模型中的一個(gè)問題：現(xiàn)有的獨(dú)立級(jí)聯(lián)模型都是在靜態(tài)網(wǎng)絡(luò)中擴(kuò)展的，而現(xiàn)實(shí)中的物流網(wǎng)絡(luò)是隨時(shí)間不斷的變化的，靜態(tài)網(wǎng)絡(luò)不能反映出網(wǎng)絡(luò)隨時(shí)間變化的情況。時(shí)間片網(wǎng)絡(luò)是由多個(gè)按時(shí)間序列排序的網(wǎng)絡(luò)構(gòu)成的社會(huì)網(wǎng)絡(luò)可以反映出網(wǎng)絡(luò)中的節(jié)點(diǎn)隨著時(shí)間的變化而變化�；诖吮疚奶岢鲈诨跁r(shí)間片網(wǎng)絡(luò)中進(jìn)行獨(dú)立級(jí)聯(lián)模型的擴(kuò)散，并通過實(shí)驗(yàn)對(duì)兩種網(wǎng)絡(luò)中的獨(dú)立級(jí)聯(lián)模型擴(kuò)散進(jìn)行了對(duì)比，此外還將一些在靜態(tài)網(wǎng)絡(luò)中比較經(jīng)典的算法引入到基于時(shí)間片的網(wǎng)絡(luò)中。
.........
參考文獻(xiàn)(略) 

本文編號(hào)：42487