社交网络与社会计算课程内容梳理总结
目錄
- 1 引言
- 2 復(fù)雜網(wǎng)絡(luò)的圖要素
- 3 復(fù)雜網(wǎng)絡(luò)度量
- 4 復(fù)雜網(wǎng)絡(luò)模型
- 5 網(wǎng)絡(luò)表示學(xué)習(xí)
- 6 主題模型
1 引言
社會計算是指社會科學(xué)和計算技術(shù)交叉融合而成的一個研究領(lǐng)域，研究如何利用計算系統(tǒng)幫助人們進(jìn)行溝通與協(xié)作，研究如何利用計算技術(shù)分析社會運行的規(guī)律與發(fā)展趨勢，即以社交網(wǎng)絡(luò)和社會媒體為研究對象，從中發(fā)現(xiàn)社會關(guān)系、社會行為的規(guī)律。
社會計算的研究內(nèi)容包括：
社會計算的研究理論工具：
社會媒體是指互聯(lián)網(wǎng)上基于用戶關(guān)系的內(nèi)容生產(chǎn)與交換平臺，其特點有：1）多對多；2）豐富的用戶交互特性。
社會媒體數(shù)據(jù)通常用圖或者矩陣的形式進(jìn)行表示。現(xiàn)實世界中的大規(guī)模網(wǎng)絡(luò)往往具有一些共同的性質(zhì)：無標(biāo)度分布、小世界效應(yīng)、強社區(qū)結(jié)構(gòu)。
社會媒體挖掘的意義：
社會媒體挖掘的挑戰(zhàn)：
本課程關(guān)注的社會計算任務(wù)：
2 復(fù)雜網(wǎng)絡(luò)的圖要素
復(fù)雜網(wǎng)絡(luò)是指那些結(jié)構(gòu)復(fù)雜、無規(guī)則、隨時間動態(tài)變化的網(wǎng)絡(luò)。
哥尼斯堡七橋問題：只有當(dāng)圖中度為奇數(shù)的頂點不超過兩個，這樣的路徑才存在。
圖的基礎(chǔ)知識：
圖的表示：
圖的類型：
通路是指依次遍歷相鄰邊產(chǎn)生的邊序列，分為開通路和閉通路。通路可以用邊序列或者節(jié)點序列表示。通路的長度是指經(jīng)過的邊的數(shù)量。邊不重復(fù)的通路稱為簡單通路，閉合的簡單通路稱為環(huán)路。節(jié)點和邊都不重復(fù)的通路稱為路徑，閉合的路徑稱為回路。歐拉環(huán)路是指圖中所有邊均只被遍歷一次的環(huán)路，哈密爾頓回路是指遍歷了圖中所有節(jié)點的回路。如下圖所示：
圖的連通性：如果節(jié)點viv_ivi?和節(jié)點vjv_jvj?之間有路徑連接，那么稱節(jié)點viv_ivi?可連接到節(jié)點vjv_jvj?，即可達(dá)。無向圖的可達(dá)性對稱，有向圖的可達(dá)性不一定對稱。任意節(jié)點相互可達(dá)的有向圖稱為強聯(lián)通有向圖，不考慮相互約束，稱為弱連通有向圖。同理可以基于子圖和連通性定義連通分支、強連通分支和弱連通分支。
最短路徑可以使用Dijstra算法和Prim算法進(jìn)行求解。
圖的直徑是指任意兩個節(jié)點之間距離中的最大值。圖的平均距離是指圖中所有節(jié)點對的距離的平均值。
特殊圖包括：樹、森林、生成樹、完全圖、平面圖、二分圖、正則圖
圖算法：最大流算法、Prim算法、Dijstra算法。
3 復(fù)雜網(wǎng)絡(luò)度量
度中心性認(rèn)為具有更多鏈接關(guān)系的節(jié)點具有更高的中心性，我們可以使用最大可能度數(shù)(n-1)、最大度數(shù)、度數(shù)和對度中心性進(jìn)行歸一化。
特征向量中心性是度中心性的一種擴(kuò)展，其試圖通過結(jié)合無向圖中的鄰居節(jié)點的重要性來修正度中心性，計算如下：ce(vi)=1λ∑j=1nAj,ice(vj)c_{e}\left(v_{i}\right)=\frac{1}{\lambda} \sum_{j=1}^{n} A_{j, i} c_{e}\left(v_{j}\right)ce?(vi?)=λ1?∑j=1n?Aj,i?ce?(vj?)。
Katz中心性修正了特征向量中心性的一個缺點：沒有入邊的特征向量中心性為0，計算如下：CKatz(vi)=α∑j=1nAj,iCKatz(vj)+βC_{\mathrm{Katz}}\left(v_{i}\right)=\alpha \sum_{j=1}^{\mathrm{n}} A_{j, i} C_{\mathrm{Katz}}\left(v_{j}\right)+\betaCKatz?(vi?)=α∑j=1n?Aj,i?CKatz?(vj?)+β。
PageRank中心性認(rèn)為并不是中心性用戶所關(guān)注的每一個人都是中心性用戶，解決方案是讓中心性除以節(jié)點的出度，這樣每個鄰居節(jié)點獲取源節(jié)點中心性的一部分。Cp(vi)=α∑j=1nAj,iCp(vj)djout+βC_{p}\left(v_{i}\right)=\alpha \sum_{j=1}^{n} A_{j, i} \frac{C_{p}\left(v_{j}\right)}{d_{j}^{\mathrm{out}}}+\betaCp?(vi?)=α∑j=1n?Aj,i?djout?Cp?(vj?)?+β。
介數(shù)中心性度量方法是考慮節(jié)點在連接其他節(jié)點時所表現(xiàn)出來的重要性，計算其他節(jié)點間最短路徑中有多少條要通過節(jié)點??，這個比重是多少，公式如下：Cb(vi)=∑s≠t≠viσst(vi)σstC_{b}\left(v_{i}\right)=\sum_{s \neq t \neq v_{i}} \frac{\sigma_{s t}\left(v_{i}\right)}{\sigma_{s t}}Cb?(vi?)=∑s??=t??=vi??σst?σst?(vi?)?，歸一化的介數(shù)中心性：Cbnorm?(vi)=Cb(vi)2(n?12)C_{b}^{\operatorname{norm}}\left(v_{i}\right)=\frac{C_{b}\left(v_{i}\right)}{2 \left( \begin{array}{c}{n-1} \\ {2}\end{array}\right)}Cbnorm?(vi?)=2(n?12?)Cb?(vi?)?。
緊密度中心性，在一個連通圖中，節(jié)點越接近中心，它越能快速地到達(dá)其他節(jié)點，這些節(jié)點與其他節(jié)點之間平均路徑長度應(yīng)該較小，因此定義緊密度中心性，Cc(vi)=1l￣viC_{c}\left(v_{i}\right)=\frac{1}{\overline{l}_{v_{i}}}Cc?(vi?)=lvi??1?，其中l￣vi=1n?1∑vj≠vili,j\overline{l}_{v_{i}}=\frac{1}{n-1} \sum_{v_{j} \neq v_{i}} l_{i, j}lvi??=n?11?∑vj???=vi??li,j?。
群體中心性，上述所有的中心性度量方法都是針對單個節(jié)點而定義的，這里討論如何將度中心性、緊密度中心性、介數(shù)中心性的定義擴(kuò)展到一組節(jié)點組成的集合上。
傳遞性，在社交網(wǎng)絡(luò)中，傳遞性就是我朋友的朋友就是我的朋友，傳遞性可以通過聚類系數(shù)或局部聚類系數(shù)進(jìn)行度量。C=(Number?of?Triangles?)×3Number?of?Connected?Triples?of?Nodes?C=\frac{(\text { Number of Triangles }) \times 3}{\text { Number of Connected Triples of Nodes }}C=?Number?of?Connected?Triples?of?Nodes?(?Number?of?Triangles?)×3?。
相互性：相互性是簡化的傳遞性，它只考慮有向圖中長度為2的閉合循環(huán)。
相似性分為結(jié)構(gòu)相似性和規(guī)則相似性，結(jié)構(gòu)相似性的度量方法有Jaccard 相似度:σJaccard(vi,vj)=∣N(vi)∩N(vj)∣∣N(vi)∪N(vj)∣\sigma_{J a c c a r d}\left(v_{i}, v_{j}\right)=\frac{\left|N\left(v_{i}\right) \cap N\left(v_{j}\right)\right|}{\left|N\left(v_{i}\right) \cup N\left(v_{j}\right)\right|}σJaccard?(vi?,vj?)=∣N(vi?)∪N(vj?)∣∣N(vi?)∩N(vj?)∣?和Cosine相似度σcosine?(vi,vj)=∣N(vi)∩N(vj)∣∣N(vi)∣∣N(vj)∣\sigma_{\text { cosine }}\left(v_{i}, v_{j}\right)=\frac{\left|N\left(v_{i}\right) \cap N\left(v_{j}\right)\right|}{\sqrt{\left|N\left(v_{i}\right)\right|\left|N\left(v_{j}\right)\right|}}σ?cosine??(vi?,vj?)=∣N(vi?)∣∣N(vj?)∣?∣N(vi?)∩N(vj?)∣?。在規(guī)則相似性里，我們并不注重個體間共有的鄰居節(jié)點，而是關(guān)注鄰居節(jié)點自身的相似程度，通過比較鄰居節(jié)點的相似度來確定節(jié)點間的相似度，而不是通過共有的鄰居節(jié)點來確定。
4 復(fù)雜網(wǎng)絡(luò)模型
真實網(wǎng)絡(luò)的常見屬性包括：1）度分布——冪律分布2）聚類系數(shù)——普遍較高3）平均路徑長度——普遍較短。
社會媒體中節(jié)點度通常是指一個人的朋友數(shù)量（無向圖中的度）或粉絲數(shù)量（關(guān)注網(wǎng)絡(luò)中的入度），這個度分布通常滿足冪律分布：ln?pk=?bln?k+ln?a\ln p_{k}=-b \ln k+\ln alnpk?=?blnk+lna，pkp_kpk?表示節(jié)點度為?的節(jié)點在整個網(wǎng)絡(luò)節(jié)點中所占的比例。
符合冪律分布的網(wǎng)絡(luò)通常叫做無標(biāo)度網(wǎng)絡(luò)（Scale-Free networks）。
圖論中，聚類系數(shù)是表示節(jié)點聚集程度的系數(shù)。
全局集聚系數(shù)基于節(jié)點三元組，是所有三元組（包括開三元組和閉三元組）中閉三元組所占比例，圖中一個節(jié)點的局部集聚系數(shù)表示它的相鄰節(jié)點形成一個團(tuán)（完全圖）的緊密程度，Ci={kidi×(di?1)/2di>10di=0or?1C_{i}=\left\{\begin{array}{cc}{\frac{k_{i}}{d_{i} \times\left(d_{i}-1\right) / 2}} & {d_{i}>1} \\ {0} & {d_{i}=0 \text { or } 1}\end{array}\right.Ci?={di?×(di??1)/2ki??0?di?>1di?=0?or?1?，其中kik_iki?表示鄰居間的邊數(shù)，did_idi?是鄰居數(shù)。整個網(wǎng)絡(luò)的平均聚類系數(shù)定義如下：C=∑i∈VCi∣V∣C=\frac{\sum_{i \in V} C_{i}}{|V|}C=∣V∣∑i∈V?Ci??。
在真實網(wǎng)絡(luò)中，網(wǎng)絡(luò)中任意兩個用戶都可以經(jīng)過一條比較短的朋友關(guān)系鏈進(jìn)行關(guān)聯(lián)，評論路徑長度定義為：lG=1n?(n?1)?∑i,jd(vi,vj)l_{G}=\frac{1}{n \cdot(n-1)} \cdot \sum_{i, j} d\left(v_{i}, v_{j}\right)lG?=n?(n?1)1??∑i,j?d(vi?,vj?)。
隨機圖模型，節(jié)點之間的邊是隨機生成的，我們討討論兩種隨機圖模型，G(n,p)G(n, p)G(n,p)，節(jié)點之間存在連邊的概率；G(n,m)G(n, m)G(n,m)，m是生成邊的數(shù)量。
小世界網(wǎng)絡(luò)模型是Watts和Strogatz在1998年提出的基于人類社會網(wǎng)絡(luò)的網(wǎng)絡(luò)生成模型，它通過調(diào)節(jié)一個重鏈參數(shù)?可以從正則網(wǎng)絡(luò)向隨機網(wǎng)絡(luò)過渡，該模型稱為WS小世界模型。正則網(wǎng)絡(luò)是指任何一個節(jié)點的近鄰數(shù)目都相同的網(wǎng)絡(luò)。
優(yōu)先鏈接模型由Albert-László Barabási and Réka Albert在1999年提出，當(dāng)新的節(jié)點加入到網(wǎng)絡(luò)時，它們更傾向于連接那些與網(wǎng)絡(luò)中較多節(jié)點相連的節(jié)點。
5 網(wǎng)絡(luò)表示學(xué)習(xí)
6 主題模型
貝葉斯概率是貝葉斯網(wǎng)絡(luò)運行的理論基礎(chǔ)，其原理和應(yīng)用相對比較簡單。
先驗概率是指根據(jù)歷史的資料或主觀判斷所確定的各種事件發(fā)生的概率，該概率沒有經(jīng)過實驗證實，屬于檢驗前的概率。
后驗概率一般是指通過貝葉斯公式，結(jié)合調(diào)查等方式獲取了新的附加信息，對先驗概率修正后得到的更符合實際的概率。
似然條件概率：當(dāng)條件確定時，某事件發(fā)生的概率就是該事件的條件概率。
貝葉斯公式：P(Bi∣A)=P(Bi)P(A∣Bi)∑i=1nP(Bi)P(A∣Bi)P\left(B_{i} | A\right)=\frac{P\left(B_{i}\right) P\left(A | B_{i}\right)}{\sum_{i=1}^{n} P\left(B_{i}\right) P\left(A | B_{i}\right)}P(Bi?∣A)=∑i=1n?P(Bi?)P(A∣Bi?)P(Bi?)P(A∣Bi?)?。
有向概率圖模型：貝葉斯網(wǎng)絡(luò)（BN）、隱馬爾科夫模型（HMM）；
無向概率圖模型：馬爾科夫隨機場（MRF）、條件隨機場（CRF）；
混合概率圖模型：鏈圖（CG）。
貝葉斯網(wǎng)絡(luò)：聯(lián)合分布：P(X1,…,Xn)=∏iP(Xi∣Pa?(Xi))P\left(X_{1}, \ldots, X_{n}\right)=\prod_{i} P\left(X_{i} | \operatorname{Pa}\left(X_{i}\right)\right)P(X1?,…,Xn?)=∏i?P(Xi?∣Pa(Xi?))。
極大似然估計的步驟：
極大似然估計存在以下問題：對于許多具體問題不能構(gòu)造似然函數(shù)解析表達(dá)式?(?|?);似然函數(shù)表達(dá)式過于復(fù)雜而導(dǎo)致難以求解最值。正是在這種情況下，人們提出了基于數(shù)值迭代的EM算法。
EM算法主要用于非完全數(shù)據(jù)參數(shù)估計，它通過假設(shè)隱變量的存在，可以大大簡化似然函數(shù)方程，以迭代的方式尋找使似然函數(shù)?(?|?)達(dá)到最大的參數(shù)。
Markov Chain Mento Carlo采樣方法（簡稱MCMC方法）主要用于統(tǒng)計推理中的模擬抽樣，尤其在貝葉斯推理中有著非常廣泛的應(yīng)用。
直觀上，主題就是一個概念、一個方面，它表現(xiàn)為一系列相關(guān)的詞語，數(shù)學(xué)上，主題就是詞匯表上詞語的條件概率分布。在自然語言處理中，主題（topic）可以看成是詞項空間（或詞典、詞匯表）上的概率分布。
主題模型起源于隱性語義索引（Latent Semantic Indexing, LSI），隱性語義索引并不是概率模型，因此也算不上一個主題模型，但是其基本思想為主題模型的發(fā)展奠定了基礎(chǔ)。
在LSI的基礎(chǔ)上，Hofmann提出了概率隱性語義索引（probabilistic Latent Semantic Indexing, pLSI）,該模型被看成是一個真正意義上的主題模型。
Blei等人提出的LDA（Latent Dirichlet Allocation）又在pLSI的基礎(chǔ)上進(jìn)行了擴(kuò)展得到一個更為完全的概率生成模型。
主題模型的主要內(nèi)容包括：
主題模型的主要輸入是文檔集合，由于交換性的假設(shè)，文檔集合等價于詞項-文檔矩陣。主題模型的另一個輸入是主題個數(shù)?，通常，?的大小需要在模型訓(xùn)練前指定，而且存在一定的經(jīng)驗性。
主題模型中的一個重要假設(shè)是詞袋（bag of words）假設(shè)，即一篇文檔內(nèi)的詞項可以交換次序而不影響模型的訓(xùn)練結(jié)果。
主題模型的表示有兩種，分別是使用圖模型和生成過程。以LDA模型為例，下圖是使用圖模型的方法對LDA模型進(jìn)行表示：
圖中方框表示其中的內(nèi)容進(jìn)行重復(fù)，右下角是重復(fù)的次數(shù)，灰色節(jié)點表示觀測值，空心節(jié)點表示隱含隨機變量或者參數(shù)，箭頭代表依賴關(guān)系，?是?的超參數(shù)，?是?×?的參數(shù)集合，每行代表某個主題中的詞項概率分布，?是主題個數(shù)，?是詞項個數(shù)；?表示每篇文檔的主題概率分布，共?個，?為文檔個數(shù)．?為單詞，?為?的主題標(biāo)號。我們也可以通過生成過程來對主題模型進(jìn)行描述，LDA模型是按照如下圖所示的方式生成一篇文檔，重復(fù)?次則生成整個語料：
主題模型中，最重要的兩組參數(shù)分別是各文檔的主題概率分布和各主題下的詞項概率分布,參數(shù)估計可以看成是生成過程的逆過程：即在已知文檔集（即生成的結(jié)果）的情況下，通過參數(shù)估計，得到參數(shù)值。針對參數(shù)估計，我們需要選擇最優(yōu)化的目標(biāo)函數(shù)，在主題模型中通常是整個語料的概率似然。
以LDA模型為例，根據(jù)其概率模型很容易得到語料概率似然值p(D∣α,β)p(D|\alpha, \beta)p(D∣α,β)為：
∏d=1M∫p(θd∣α)(∏n=1Nd∑zdnp(zdn∣θd)p(wdn∣zdn,β))dθd\prod_{d=1}^{M} \int p\left(\theta_ze8trgl8bvbq | \alpha\right)\left(\prod_{n=1}^{N_ze8trgl8bvbq}\sum_{z_{d n}} p\left(z_{d n} | \theta_ze8trgl8bvbq\right) p\left(w_{d n} | z_{d n}, \beta\right) \right) \mathrmze8trgl8bvbq \theta_ze8trgl8bvbq d=1∏M?∫p(θd?∣α)(n=1∏Nd??zdn?∑?p(zdn?∣θd?)p(wdn?∣zdn?,β))dθd?
其中，D代表整個語料，也就是所有文檔的集合，NdN_dNd?表示第d篇文檔的長度，θd\theta _dθd?表示第d篇文檔的主題概率分布，wdnw_{dn}wdn?表示第d篇文檔的第n個單詞，zdnz_{dn}zdn?表示wdnw_{dn}wdn?的主題，該函數(shù)以α\alphaα和β\betaβ為參數(shù)，通過對目標(biāo)函數(shù)進(jìn)行最大化來估計α\alphaα 和β\betaβ的值。
主題模型訓(xùn)練完成后，我們便可以使用訓(xùn)練好的主題模型對新的樣本進(jìn)行推斷，通過主題模型將以詞項空間表達(dá)的文檔變換到新的主題空間，得到一個以主題為坐標(biāo)的低維表達(dá)，該表達(dá)也就是文檔的主題概率分布。
概率隱性語義索引（probabilistic Latent Semantic Indexing, pLSI）是Hofmann在1999年提出的一個主題模型，旨在尋找一個從詞項空間到隱性語義（即主題）空間的變換。
pLSI生成數(shù)據(jù)集的步驟如下：
觀察上述過程，容易得到模型的兩組主要參數(shù)$p(w | z) 和和和 p(z | d)$，即個主題下的詞項分布和各文檔的主題概率分布，由于沒有概率分布的類型，這兩組參數(shù)其實就是兩張二維的參數(shù)表，需要通過參數(shù)估計來確定二維表的每個參數(shù)的值。
共軛先驗分布，如果后驗概率和先驗概率滿足同樣的分布，那么先驗分布和后驗分布被叫做共軛分布，同時先驗分布叫做似然函數(shù)的共軛先驗分布：
P(θ∣x)=P(x∣θ)?P(θ)P(x)∝P(x∣θ)?P(θ)P(\theta | x)=\frac{P(x | \theta) \cdot P(\theta)}{P(x)} \propto P(x | \theta) \cdot P(\theta) P(θ∣x)=P(x)P(x∣θ)?P(θ)?∝P(x∣θ)?P(θ)
采用共軛先驗分布的原因是：一方面可以使得先驗分布和后驗分布的形式相同，符合人的直覺；另一方面，可以形成一個先驗鏈，即現(xiàn)在的后驗部分可以作為下一次計算的先驗分布。
舉個例子，二項分布的似然函數(shù)是:P(x∣θ)=θx?(1?θ)1?xP(x | \theta)=\theta^{x} \cdot(1-\theta)^{1-x}P(x∣θ)=θx?(1?θ)1?x,其共軛分布是Beta分布，P(θ∣α,β)=θα?1(1?θ)β?1∫01θα?1(1?θ)β?1dθP(\theta | \alpha, \beta)=\frac{\theta^{\alpha-1}(1-\theta)^{\beta-1}}{\int_{0}^{1} \theta^{\alpha-1}(1-\theta)^{\beta-1} d \theta}P(θ∣α,β)=∫01?θα?1(1?θ)β?1dθθα?1(1?θ)β?1?，根據(jù)貝葉斯公式計算后驗概率如下：
P(θ∣x)∝P(x∣θ)?P(θ)∝(θx(1?θ)x)(θα?1(1?θ)β?1)=θx+α?1(1?θ)1?x?α?1\begin{array}{l} {P(\theta | x)} \\ {\propto P(x | \theta) \cdot P(\theta)} \\ {\propto\left(\theta^{x}(1-\theta)^{x}\right)\left(\theta^{\alpha-1}(1-\theta)^{\beta-1}\right)}\\ {=\theta ^{x+\alpha-1}(1-\theta)^{1-x-\alpha-1}} \end{array} P(θ∣x)∝P(x∣θ)?P(θ)∝(θx(1?θ)x)(θα?1(1?θ)β?1)=θx+α?1(1?θ)1?x?α?1?
歸一化這個后驗概率可以得到另一個Beta分布。
總結(jié)
以上是生活随笔為你收集整理的社交网络与社会计算课程内容梳理总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 软件设计师教程（第5版）- 前言和目录
- 下一篇： java对话框进度条_java进度条