基于模塊度最大化的社區(qū)發(fā)現(xiàn)算法的研究.pdf

1、隨著網(wǎng)絡(luò)的迅速發(fā)展，對(duì)復(fù)雜網(wǎng)絡(luò)的研究在許多領(lǐng)域都備受關(guān)注。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的一個(gè)普遍特征，對(duì)社區(qū)結(jié)構(gòu)的挖掘成為了網(wǎng)絡(luò)分析中的研究熱點(diǎn)。復(fù)雜網(wǎng)絡(luò)由許許多多個(gè)社區(qū)構(gòu)成，社區(qū)發(fā)現(xiàn)對(duì)于了解復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)有著重要的意義。從計(jì)算角度而言，社區(qū)劃分相當(dāng)于將任務(wù)分解，可以降低計(jì)算復(fù)雜度；從實(shí)際應(yīng)用而言，社區(qū)發(fā)現(xiàn)“產(chǎn)生”了推薦，方便了人們的生活。本文針對(duì)社區(qū)發(fā)現(xiàn)問(wèn)題，結(jié)合社區(qū)結(jié)構(gòu)這個(gè)重要屬性，利用模塊度最大化方法對(duì)社區(qū)發(fā)現(xiàn)算法中的時(shí)間復(fù)雜度以及社

2、區(qū)結(jié)構(gòu)的強(qiáng)弱展開(kāi)了深入研究。
　　首先，針對(duì)基于模塊度最大化這類(lèi)標(biāo)簽傳播算法中時(shí)間復(fù)雜度高的問(wèn)題，本文依據(jù)“先傳播，后合并”的原則，降低了社區(qū)合并導(dǎo)致整個(gè)網(wǎng)絡(luò)需要更新帶來(lái)的較高時(shí)間復(fù)雜度；結(jié)合社區(qū)結(jié)構(gòu)的概念提出了基于模塊度最大化的標(biāo)簽傳播算法CDMM-LPA?；谏鐓^(qū)結(jié)構(gòu)的重要性，本文將社區(qū)結(jié)構(gòu)作為一個(gè)重要的考慮因素融入CDMM-LPA算法中，使得最終獲得的社區(qū)屬于強(qiáng)結(jié)構(gòu)社區(qū)。
　　其次，提出了基于模塊度最大化的雙向合并的社