本文試圖對社交網絡上的事件傳播效果進行理論建模，并研究如何最大化傳播效果這一算法問題。

1、概述介紹

首先，我們來看社交網絡的基本模型定義。所謂社交網絡，在數學上是這么定義的：

1) N個頂點，{1，2，……N}

2) 它們構成一個有向圖，邊上有權重，權重矩陣為R，其中表示頂點 i 被頂點 j 影響的程度。如果，那么就意味這頂點 i 不受j影響（比如 i 和 j 之間沒有連邊、i 沒有關注 j 等）。

社交網絡的一個例子：下面的圖來自[Adamic-Adar 2003]，表示436個HP Lab研究員之間的社交網絡，兩個人之間連邊當且僅當他們有過至少6封email交流。

接下來，我們來描述在社交網絡上事件營銷的”波紋效應“是如何進行的。一般來說，這個過程可以按下面的方式來理解：

1) 初始化：會有一些頂點被選定，在一定觸發（激勵）條件下，做了某種行為。比如事件營銷時，會選擇一些大號發帖，這好比向湖里投幾顆石頭。

2) 網絡傳播：網絡中的某個頂點，一旦發現他的鄰居們觸發了這個"行為"，達到一定程度，這個人也會觸發一定"行為"。這現象叫做這個頂點被鄰居的行為轉播影響到了。

那么我們研究的問題是什么呢？顯而易見的，在不同的頂點上做這樣的初始化觸發行為，最終在網絡上達到的傳播效果是不同的。所以，我們的目標是在一定的資源限制下（找大號發軟文都是要給很大一筆費用的），找到傳播效果最好的初始化頂點集合（也叫種子集）。

對這個問題，當然是已經有一些經典的模型和研究成果了。在這些研究里，所謂的”行為“一般是一個0/1變量？比如：感染傳染病、轉發軟文、購買新產品、相信謠言等。對網絡傳播的模型，他們也重點放在某個頂點采取這個行為的概率。直觀上說，一個人是否采取行為，和鄰居有很大關系。這個關系定量的趨勢有大概下面兩種：邊際遞減和突變式。

相應的，找到種子集最大化傳播效果這個問題也有截然不同的結果。對于被影響概率隨被影響鄰居數量邊際遞減的情況，存在常數近似比的算法。（http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf 這篇論文給出了模型和達到最優解63%的一個貪心算法）；對第二種情況，卻很難計算近似解。

2、我們的模型

ok，說了那么多，回到這篇文章要解決的問題。我們希望每個頂點的行為不局限于0/1變量，而是一個可充分量化的變量。我們的新傳播模型有下面幾個特點：

1) 采取的行為是可充分量化的：不再非0即1，可以是一個實數。我們用表示頂點 i 采取的行為量。

2) 各個鄰居的影響是獨立的：頂點 i 會受到鄰居 j 的影響而采取一定行為量，假設這個量用表示，其中是描述 i 受 j 影響程度的邊(j,i)的權重。這個影響是獨立的，不受其他鄰居 j' 的干擾。

3) 影響可簡單線性疊加：

必須說明的是，種子集合中的頂點，我們一般認為不再受鄰居的影響而改變行為了。

對這個新的模型，我們首先來看一下給定一個種子集合S，如何定義和計算它的傳播影響力。給定S后，S中這些頂點觸發一定的初始行為量，不斷刺激著鄰居，并通過網絡不斷迭代傳播。最終這個過程會收斂到一個穩定狀態。所謂穩定狀態，就是對非S內的頂點集合，存在一個行為量向量，將和拼接起來的行為量向量用B表示。那么在穩定狀態下，使得對所有內的頂點都滿足：

集合S的傳播影響力用F(S)表示，那么：

（待續）

總結

以上是生活随笔為你收集整理的社交网络上的影响传播模型的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。