社會網(wǎng)絡社區(qū)發(fā)現(xiàn)方法研究.pdf

1、客觀世界可以被抽象成不同的復雜網(wǎng)絡，其中個體及個體之間的關聯(lián)關系可以依據(jù)設定的規(guī)則抽象為圖中的節(jié)點和節(jié)點間的邊。社區(qū)結構是復雜網(wǎng)絡的一個重要屬性，社區(qū)內部節(jié)點連接稠密而社區(qū)間節(jié)點連接稀疏。通過尋找復雜網(wǎng)絡中的社區(qū)結構可以發(fā)現(xiàn)網(wǎng)絡蘊含的規(guī)律，并可以預測網(wǎng)絡演化趨勢，所以復雜網(wǎng)絡社區(qū)發(fā)現(xiàn)一直是研究的熱點之一。
　　近年來，社區(qū)發(fā)現(xiàn)研究已經(jīng)取得了長足的進步，國內外學者們提出了各類不同的理論和方法。但是，這些算法一般需要先驗知識或者時間復

2、雜度過高。標簽傳播算法(LPA)作為近年來新興的一種快速劃分方法，不需要知道網(wǎng)絡的整體信息或者先驗社區(qū)結構，運行速度快，僅具有線性的時間復雜度，且準確率高。但是，傳統(tǒng)標簽傳播算法在標簽傳播過程平等對待每一個標簽，隨機更新標簽，所以該算法的穩(wěn)定性有待進一步提高。
　　為抑制標簽傳播算法中標簽傳播的隨意性，本文提出了一種基于隨機游走的標簽傳播社區(qū)發(fā)現(xiàn)算法，研究工作主要包括以下三個方面:
　　(1)隨機游走算法改進。原始的隨機游走

3、算法中只有一個游走的種子，文中稱之為walker，但是，由于隨機游走算法本身存在的隨機性，產生的結果有很大的不確定性。為提高結果的準確性和魯棒性，本文提出可以連續(xù)不斷釋放多個walker的隨機游走算法，即在給定的時間內，每間隔一個單位時間釋放一個walker。通過walker運動路徑在兩點間可達的概率，得出兩個節(jié)點間的相似度，進而求得網(wǎng)絡中所有節(jié)點間的相似度矩陣。
　　(2)提出了基于隨機游走相似度矩陣的標簽傳播社區(qū)發(fā)現(xiàn)算法。原始

4、標簽傳播過程中，當鄰居節(jié)點中標簽出現(xiàn)頻率存在多個最高時，將會隨機選擇一個最高標簽，由于標簽傳播的隨意性導致算法結果的不穩(wěn)定。為此本文提出一個基于隨機游走相似度矩陣的標簽傳播社區(qū)發(fā)現(xiàn)算法，即在標簽傳播過程中引入相似度矩陣，當遇有相同的最大鄰居標簽數(shù)時，不再隨機選擇標簽，而是通過查找相似度矩陣，找到相似度最高的鄰居節(jié)點，將自身更新為與該節(jié)點相同的標簽，避免了標簽在社區(qū)之間的任意傳播。
　　(3)確定隨機游走過程中步數(shù)t的取值。計算相似