基于圖著色的社區(qū)發(fā)現(xiàn)算法研究.pdf

1、隨著信息時代的高速發(fā)展，人們的生活、工作和社會網(wǎng)絡(luò)之間的聯(lián)系越來越緊密，社會網(wǎng)絡(luò)體現(xiàn)是一種密集的社會結(jié)構(gòu)，這種社會結(jié)構(gòu)已經(jīng)形成了相對比較穩(wěn)定的關(guān)系體系。社會網(wǎng)絡(luò)就是將各社會個體成員(或者組織)之間通過互動的方式相連接，它所關(guān)注的是每個社會個體成員或者組織之間的互動和聯(lián)系。社會網(wǎng)絡(luò)一般都呈現(xiàn)出高度的社區(qū)性，這也是社會網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)之間的區(qū)別。社區(qū)發(fā)現(xiàn)就是根據(jù)給定的社會網(wǎng)絡(luò)，來抽取社區(qū)。國外已經(jīng)針對這個問題的研究很多，并且廣泛地應(yīng)用于科學(xué)家

2、的合作、疾病的傳播等方面。該那么如何在社會網(wǎng)絡(luò)中高效地發(fā)現(xiàn)社區(qū)，就稱為了近年來社會網(wǎng)絡(luò)的研究熱點。
　　本文主要研究工作如下：第一，分析目前社會網(wǎng)絡(luò)的社區(qū)劃分算法。通過對各種算法進行詳細的闡述和性能比較，結(jié)果表明：一方面這些算法進行合理社區(qū)劃分的時間復(fù)雜度較高而且效率較低，另一方面這些算法進行合理社區(qū)劃分時需要設(shè)置先驗條件。
　　第二，針對這些算法存在的主要問題，本文準(zhǔn)備首先通過圖著色算法首先求出極大團，給出就求解極大團算法