社會(huì)信息網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法研究.pdf

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

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

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