隨著互聯(lián)網(wǎng)技術(shù)和Web2.0應(yīng)用的飛速發(fā)展,大量形態(tài)各異的在線社交網(wǎng)絡(luò)風(fēng)靡世界,成為人們分享和傳遞信息的重要平臺,也幫助人們在網(wǎng)絡(luò)中維系著自己的社會關(guān)系。因此,研究社交網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)有著非常現(xiàn)實的意義,也成為近些年的研究熱點。研究人員曾提出過很多社區(qū)發(fā)現(xiàn)算法,然而很多算法都有時間復(fù)雜度較高的問題�；跇撕瀭鞑サ纳鐓^(qū)發(fā)現(xiàn)算法具有接近線性的時間復(fù)雜度,它對圖中每個頂點分配一個代表其所在社區(qū)的標簽,按照隨機順序?qū)γ總�頂點進行標簽更新。一個頂點若具有多個滿足條件的候選標簽,則隨機選擇標簽。然而該算法的結(jié)果包含很多小而碎的社區(qū),且結(jié)果很不穩(wěn)定。因此我們提出了基于標簽影響值的社區(qū)發(fā)現(xiàn)算法（LIB）。LIB算法選取一個種子集,為其中的頂點分配標簽并按頂點度排序進行傳播,在傳播過程中為每一種標簽計算標簽影響值來選擇標簽。我們在不同類型的數(shù)據(jù)集上進行了對比實驗,實驗結(jié)果表明LIB算法在復(fù)雜度相近的情況下明顯提高了所發(fā)現(xiàn)社區(qū)的質(zhì)量,并有很好的穩(wěn)定性。為了能更多的考慮社交網(wǎng)絡(luò)中的動態(tài)行為,并且更多的從社會學(xué)意義上提高社區(qū)發(fā)現(xiàn)的質(zhì)量,我們提出了基于標簽影響向量的社區(qū)發(fā)現(xiàn)算法（LIVB）。LIVB算法將在線社... 

【文章來源】：復(fù)旦大學(xué)上海市 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：53 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 引言
    1.1 背景介紹
    1.2 相關(guān)概念
        1.2.1 社交網(wǎng)絡(luò)中的社區(qū)
        1.2.2 社交網(wǎng)絡(luò)的數(shù)學(xué)表達
        1.2.3 社區(qū)發(fā)現(xiàn)算法
    1.3 本文組織架構(gòu)
第二章 相關(guān)工作與背景知識
    2.1 社區(qū)發(fā)現(xiàn)相關(guān)算法
    2.2 基于標簽傳播的社區(qū)發(fā)現(xiàn)算法
    2.3 社區(qū)質(zhì)量評價指標
第三章 基于標簽影響值的社區(qū)發(fā)現(xiàn)算法
    3.1 算法思想
    3.2 LIB社區(qū)發(fā)現(xiàn)算法
        3.2.1 種子集合的選取
        3.2.2 標簽傳播過程
        3.2.3 社區(qū)生成算法LIB
    3.3 LIB算法時間復(fù)雜度
第四章 LIB算法實驗驗證
    4.1 實驗數(shù)據(jù)
        4.1.1 基準數(shù)據(jù)集
        4.1.2 抓取數(shù)據(jù)集
    4.2 實驗環(huán)境
    4.3 實驗評估方法
    4.4 實驗結(jié)果與分析
        4.4.1 實驗一 基于基準數(shù)據(jù)集的實驗
        4.4.2 實驗二 基于抓取數(shù)據(jù)集的實驗
第五章 基于標簽影響向量的社區(qū)發(fā)現(xiàn)算法
    5.1 算法提出背景
    5.2 Label-Influence-Vector-Based社區(qū)發(fā)現(xiàn)算法
        5.2.1 算法思想
        5.2.2 標簽影響向量的計算
        5.2.3 標簽影響向量的比較方式
        5.2.4 社區(qū)生成算法LIVB
    5.3 LIVB算法時間復(fù)雜度
    5.4 標簽影響向量比較公式的傳遞性證明
        5.4.1 問題定義
        5.4.2 問題分析
        5.4.3 分類詳細證明
第六章 LIVB算法實驗驗證
    6.1 實驗數(shù)據(jù)
    6.2 實驗環(huán)境
    6.3 實驗評估方法
    6.4 實驗結(jié)果與分析
        6.4.1 實驗三 LIVB算法和LPA算法對比實驗
        6.4.2 實驗四 LPA算法在不同類型圖上的對比實驗
第七章 總結(jié)與展望
    7.1 論文總結(jié)
    7.2 未來工作展望
參考文獻
附錄一 碩士期間所發(fā)表的論文
致謝



本文編號：3326589