社會信息網絡社區(qū)發(fā)現(xiàn)算法研究.pdf

1、社會信息網絡普遍存在于現(xiàn)實世界中的許多領域，比如微博網絡、電子郵件網絡、科學合作網絡等等。在現(xiàn)實生活中，這些網絡通常以社區(qū)的形式組合在一起，社區(qū)結構具體表現(xiàn)為一組頂點的集合，在這個頂點集內部連接緊密而頂點集彼此之間連接比較稀疏。作為復雜社會信息網絡的一個顯著特征，社區(qū)結構一方面反映了目標網絡個體之間聯(lián)系的局部性；另一方面，社區(qū)結構影響甚至決定著發(fā)生在復雜網絡上的動態(tài)過程。因此，社區(qū)結構的研究對闡明復雜信息網絡的組織結構及功能具有非常重要

2、的理論和實際意義。
　　本文針對如何度量社區(qū)、如何發(fā)現(xiàn)社會信息網絡中的社區(qū)結構的問題，研究了社會網絡中許多高效的靜態(tài)和動態(tài)社區(qū)發(fā)現(xiàn)算法。主要研究成果和創(chuàng)新之處包括：
　?。?）基于對k均值思想以及其他相關算法的研究分析，本文提出了一種針對靜態(tài)社會信息網絡的社區(qū)發(fā)現(xiàn)算法（命名為 KRRW）從社會網絡中發(fā)現(xiàn)社區(qū)結構。KRRW采用一個簡單的隨機游走模型來減少 k均值模型中算法對初始中心節(jié)點選擇的強烈依賴程度。另外，文中還提出了一種

3、改進的社區(qū)好壞評估方式DCD，DCD是基于社區(qū)的聚集性（clustering）這一衡量方式進行的改進，這一度量方式綜合考慮了社區(qū)內及社區(qū)之間的連接密度。在一些經典的現(xiàn)實網絡數(shù)據集上的實驗結果證實了KRRW算法能夠較其他一些算法獲得更高的社區(qū)模塊度Q， DCD以及準確率AR等衡量指標。
　　（2）本文還針對動態(tài)社會信息網絡中如何準確地挖掘社區(qū)核心頂點、如何定義和量化社區(qū)的增量變化等問題展開研究。在這些調查研究的基礎上，本論文提出了一