基于拓撲勢的網絡社區(qū)發(fā)現方法研究.pdf

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

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

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

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

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