基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究.pdf

1、由于21世紀(jì)的第二個(gè)十年將是實(shí)現(xiàn)人、機(jī)、物和信息等要素和諧共生的物聯(lián)網(wǎng)和社會(huì)網(wǎng)絡(luò)時(shí)代,許多國家都將面向網(wǎng)絡(luò)化社會(huì)的研究提升到了國家戰(zhàn)略層次,而在各種網(wǎng)絡(luò)的實(shí)際應(yīng)用中社區(qū)發(fā)現(xiàn)是一個(gè)不可逾越的步驟,所以深入展開網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)研究具有十分重要的意義。拓?fù)鋭堇碚撌且环N新的社區(qū)發(fā)現(xiàn)理論。較之傳統(tǒng)社區(qū)發(fā)現(xiàn)方法,基于該理論的社區(qū)發(fā)現(xiàn)方法具有多方面的優(yōu)勢。針對傳統(tǒng)社區(qū)發(fā)現(xiàn)方法和拓?fù)鋭萆鐓^(qū)發(fā)現(xiàn)方法存在的不足,并以對拓?fù)鋭堇碚摷捌渖鐓^(qū)發(fā)現(xiàn)方法進(jìn)行改進(jìn)、完善和

2、發(fā)展為主線,本文主要從四個(gè)方面展開研究。
　　首先,證明了拓?fù)鋭蒽刈钚≈迭c(diǎn)存在性定理。網(wǎng)絡(luò)中拓?fù)鋭蒽刈钚≈迭c(diǎn)的存在性是拓?fù)鋭堇碚摷捌浞椒ㄟM(jìn)行社區(qū)發(fā)現(xiàn)的前提和基礎(chǔ),然而目前對其只限于有限的實(shí)證研究。該定理表明了拓?fù)鋭蒽刈钚≈迭c(diǎn)在千差萬別的網(wǎng)絡(luò)中存在的一般性,明確了基于拓?fù)鋭莸木W(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法的應(yīng)用范圍。
　　其次,提出了基于拓?fù)鋭莸闹丿B節(jié)點(diǎn)社區(qū)歸屬不確定性測度。目前許多社區(qū)發(fā)現(xiàn)方法為只允許一個(gè)節(jié)點(diǎn)只能屬于一個(gè)社區(qū)的硬方法,缺乏

3、現(xiàn)實(shí)合理性。事實(shí)上,眾多網(wǎng)絡(luò)中的節(jié)點(diǎn)的社區(qū)歸屬具有亦此亦彼性。重疊社區(qū)發(fā)現(xiàn)方法雖然允許一個(gè)節(jié)點(diǎn)可以同時(shí)屬于多個(gè)社區(qū),但目前尚缺乏刻畫重疊節(jié)點(diǎn)歸屬不同社區(qū)的程度指標(biāo)。該指標(biāo)的缺乏嚴(yán)重阻礙了對社區(qū)的挖掘和分析。為了驗(yàn)證該測度的有效性和合理性,提出了基于貪婪策略的重疊社區(qū)發(fā)現(xiàn)方法、基于歸屬不確定性的社區(qū)節(jié)點(diǎn)重要度排序算法和基于Pareto原理的重疊社區(qū)發(fā)現(xiàn)方法?；谪澙凡呗缘闹丿B社區(qū)發(fā)現(xiàn)方法克服了處于社區(qū)邊緣的節(jié)點(diǎn)與其他社區(qū)的聯(lián)系被人為割裂的

4、問題,基于歸屬不確定性的社區(qū)節(jié)點(diǎn)重要度排序算法針對社區(qū)發(fā)現(xiàn)結(jié)果難以理解的問題提出解決方案,基于Pareto原理的重疊社區(qū)發(fā)現(xiàn)方法彌補(bǔ)了基于貪婪策略的重疊社區(qū)發(fā)現(xiàn)方法中存在的重疊節(jié)點(diǎn)數(shù)量相對較多的不足。
　　第三,提出了基于重疊節(jié)點(diǎn)歸屬不確定性的變規(guī)模重疊社區(qū)發(fā)現(xiàn)方法。在該方法中,根據(jù)力學(xué)中的力的分解原理對前面提出的重疊節(jié)點(diǎn)歸屬不確定性測度進(jìn)行了改進(jìn)。該方法不但可以達(dá)到與目前拓?fù)鋭莘椒ㄏ喈?dāng)?shù)陌l(fā)現(xiàn)效果,還能提供較之相對宏觀或微觀的社區(qū)

5、,實(shí)現(xiàn)了對社區(qū)規(guī)模的控制和定制。
　　第四,提出了基于拓?fù)鋭萆鐓^(qū)發(fā)現(xiàn)的無損網(wǎng)絡(luò)壓縮方法。為滿足不同的需求,此項(xiàng)研究提出了兩個(gè)網(wǎng)絡(luò)無損網(wǎng)絡(luò)壓縮方法。一個(gè)方法以節(jié)點(diǎn)與社區(qū)代表點(diǎn)的相對距離為依據(jù)進(jìn)行節(jié)點(diǎn)重要性的判斷,區(qū)分不同距離節(jié)點(diǎn)的重要性,進(jìn)而實(shí)現(xiàn)按層次的網(wǎng)絡(luò)無損壓縮;另一個(gè)方法以節(jié)點(diǎn)在社區(qū)構(gòu)成中所起的作用為依據(jù)以判斷節(jié)點(diǎn)的重要性,并對節(jié)點(diǎn)的重要性進(jìn)行了量化,實(shí)現(xiàn)了按壓縮比率的網(wǎng)絡(luò)無損壓縮。對比實(shí)驗(yàn)表明,兩種方法不但可以獲得理想的壓縮