基于拓撲勢的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法研究.pdf

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

2、發(fā)展為主線,本文主要從四個方面展開研究。
　　首先,證明了拓撲勢熵最小值點存在性定理。網(wǎng)絡(luò)中拓撲勢熵最小值點的存在性是拓撲勢理論及其方法進行社區(qū)發(fā)現(xiàn)的前提和基礎(chǔ),然而目前對其只限于有限的實證研究。該定理表明了拓撲勢熵最小值點在千差萬別的網(wǎng)絡(luò)中存在的一般性,明確了基于拓撲勢的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法的應(yīng)用范圍。
　　其次,提出了基于拓撲勢的重疊節(jié)點社區(qū)歸屬不確定性測度。目前許多社區(qū)發(fā)現(xiàn)方法為只允許一個節(jié)點只能屬于一個社區(qū)的硬方法,缺乏

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

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

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