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

1、隨著復(fù)雜系統(tǒng)科學(xué)的不斷發(fā)展，同時(shí)受到移動(dòng)通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等現(xiàn)實(shí)網(wǎng)絡(luò)的推動(dòng)作用，人們針對(duì)復(fù)雜網(wǎng)絡(luò)的研究逐漸深入。由于復(fù)雜網(wǎng)絡(luò)能夠很好地描述許多復(fù)雜系統(tǒng)，人們期望通過(guò)對(duì)復(fù)雜網(wǎng)絡(luò)的研究和分析，揭示并掌握其統(tǒng)計(jì)特征、功能特性、演化規(guī)律等等，從而能夠更深刻地理解復(fù)雜系統(tǒng)，指導(dǎo)解決實(shí)際問(wèn)題。在研究中人們發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)存在社區(qū)結(jié)構(gòu)，并且社區(qū)結(jié)構(gòu)對(duì)于理解復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)和功能非常重要，許多研究者因此投入到對(duì)社區(qū)發(fā)現(xiàn)的研究，社區(qū)發(fā)現(xiàn)問(wèn)題也因此成為近年復(fù)雜網(wǎng)

2、絡(luò)領(lǐng)域中的熱門(mén)問(wèn)題。但是該問(wèn)題迄今并未被完美解決。
　　 本文通過(guò)研究近年該領(lǐng)域具有代表性的文獻(xiàn)，總結(jié)目前典型的一些社區(qū)發(fā)現(xiàn)算法，并分析它們的優(yōu)點(diǎn)和不足之處，在此基礎(chǔ)上提出一種可以并行化的重疊社區(qū)發(fā)現(xiàn)算法，以解決當(dāng)前重疊社區(qū)發(fā)現(xiàn)算法普遍效率偏低，無(wú)法處理超大規(guī)模網(wǎng)絡(luò)的問(wèn)題。
　　 首先，借鑒將clique作為初始社區(qū)核心的思想，本文提出了將clique作為標(biāo)簽傳播過(guò)程中擁有標(biāo)簽的基本單位這一新思路，并以此為基礎(chǔ)提出了一種

3、用于發(fā)現(xiàn)網(wǎng)絡(luò)中重疊社區(qū)結(jié)構(gòu)的CLPA算法。在人工網(wǎng)絡(luò)以及真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果都證明了基于此思想的重疊社區(qū)發(fā)現(xiàn)算法的有效性，并且在很多網(wǎng)絡(luò)上該算法比其他一些算法具有更佳的社區(qū)發(fā)現(xiàn)結(jié)果，同時(shí)其時(shí)間效率也令人滿意。
　　 其次，本文創(chuàng)新性的將MapReduce分布計(jì)算模型與重疊社區(qū)發(fā)現(xiàn)結(jié)合。由于本文提出的算法具備并行化的條件，借助于MapReduce分布計(jì)算模型，使得對(duì)現(xiàn)實(shí)中普遍存在的超大規(guī)模網(wǎng)絡(luò)進(jìn)行重疊社區(qū)發(fā)現(xiàn)成為可能，因而具有一定