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

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

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