復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)與網(wǎng)絡(luò)圖壓縮算法研究.pdf

1、進入科技高速發(fā)展的21世紀，網(wǎng)絡(luò)潛移默化影響著人們的生活，復(fù)雜網(wǎng)絡(luò)已經(jīng)滲透到生活中的各個領(lǐng)域。真實世界中系統(tǒng)抽象出的復(fù)雜網(wǎng)絡(luò)大多具有社區(qū)結(jié)構(gòu)，社區(qū)內(nèi)節(jié)點聯(lián)系緊密，社區(qū)間節(jié)點聯(lián)系稀疏。發(fā)現(xiàn)這些社區(qū)結(jié)構(gòu)有助于人們掌握網(wǎng)絡(luò)中潛在的規(guī)律和預(yù)測網(wǎng)絡(luò)的行為，具有重要的實際應(yīng)用價值。數(shù)據(jù)規(guī)模巨大是當(dāng)今數(shù)據(jù)的顯著特點，網(wǎng)絡(luò)圖數(shù)據(jù)也不例外。大型的 WWW網(wǎng)絡(luò)往往包含上千萬甚至上億個節(jié)點，如果使用傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)存儲網(wǎng)絡(luò)，所需空間遠遠超過了計算機內(nèi)存的大小，更

2、別說運行算法了。因此，對網(wǎng)絡(luò)圖進行有效的壓縮越來越受到人們的重視。本文針對復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)與網(wǎng)絡(luò)圖壓縮進行研究，貢獻如下：
　　(1)提出一種改進的基于相干鄰居親近度的標簽傳播算法。傳統(tǒng)社區(qū)發(fā)現(xiàn)算法存在時間復(fù)雜度高，需要事先指定社區(qū)數(shù)目等缺陷。標簽傳播算法（LPA）擁有接近線性的時間復(fù)雜度，且不需要先驗參數(shù)。但樸素 LPA算法更新策略只考慮到了鄰節(jié)點中標簽的個數(shù)，完全忽視了節(jié)點間的相互關(guān)系。本文重視挖掘節(jié)點間的親密程度，節(jié)點與節(jié)

3、點的依賴關(guān)系，提出節(jié)點間依賴度的定義，結(jié)合相干鄰居親近度（CNP），使節(jié)點的相互關(guān)系充分影響到標簽的更新策略。算法對復(fù)雜網(wǎng)絡(luò)進行預(yù)處理，將網(wǎng)絡(luò)轉(zhuǎn)化為簡單CNP網(wǎng)絡(luò)，接著根據(jù)節(jié)點間依賴度將依賴度高的節(jié)點并入本區(qū)域內(nèi)的核心節(jié)點，得到核心CNP網(wǎng)絡(luò)。最后在核心網(wǎng)絡(luò)上傳播標簽。與樸素LPA,CNP-LPA算法相比，本文算法顯著提高了社區(qū)發(fā)現(xiàn)的質(zhì)量，明顯減少了標簽傳播所需的時間。算法仍保持接近線性的時間復(fù)雜度，適用于真實的大規(guī)模復(fù)雜網(wǎng)絡(luò)。

4、　　(2)提出了一種基于社區(qū)發(fā)現(xiàn)的網(wǎng)絡(luò)圖壓縮算法。Web網(wǎng)絡(luò)按照URL字典序排列后自然地就可以體現(xiàn)出按域分類的特征，節(jié)點序列表現(xiàn)出相似性與本地性，研究者根據(jù)這兩種特性設(shè)計了許多高效的壓縮算法。大多數(shù)真實復(fù)雜網(wǎng)絡(luò)也包含類似于 Web網(wǎng)絡(luò)圖體現(xiàn)出的特性，但卻并不存在一種天然的節(jié)點排列方式，使得排列后的節(jié)點序列表現(xiàn)出相似性與本地性。本文將社區(qū)發(fā)現(xiàn)算法應(yīng)用到網(wǎng)絡(luò)圖壓縮領(lǐng)域中，對網(wǎng)絡(luò)進行預(yù)處理，將網(wǎng)絡(luò)劃分為多個社區(qū)，同一社區(qū)內(nèi)的節(jié)點連續(xù)排序，節(jié)點