網(wǎng)絡(luò)中極大k-plex發(fā)現(xiàn)算法和網(wǎng)絡(luò)社群簡歷挖掘研究.pdf

1、針對網(wǎng)絡(luò)的挖掘已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域中的熱點(diǎn)。由于需要用圖結(jié)構(gòu)來描述的數(shù)據(jù)廣泛存在于生物、化學(xué)、通信和社會學(xué)等眾多領(lǐng)域，因此針對網(wǎng)絡(luò)的挖掘有著廣泛的應(yīng)用。社群是網(wǎng)絡(luò)中的相對密集的區(qū)域，其內(nèi)部實(shí)體間存在著緊密的連接，而區(qū)域之間相互隔離或只有少許聯(lián)系橋接其間。網(wǎng)絡(luò)社群是我們了解網(wǎng)絡(luò)的結(jié)構(gòu)、功能和增長機(jī)制的一個重要工具。本文的工作圍繞著對網(wǎng)絡(luò)社群的分析展開，大體分為下面兩部分。 第一部分是對一種具體的社群結(jié)構(gòu)——極大k-plex(k叢)

2、的挖掘算法的研究。k-plex是眾多網(wǎng)絡(luò)社群定義中的一種，近年來一些使用k-plex對網(wǎng)絡(luò)進(jìn)行分析的方法和應(yīng)用逐漸出現(xiàn)，但受沒有高效的k-plex發(fā)現(xiàn)算法的限制，都只能局限在小規(guī)模網(wǎng)絡(luò)上。我們提出了一種基于回溯的極大k-pleX挖掘算法并提出了若干剪枝策略來提升算法的性能。為了分析更大的網(wǎng)絡(luò)，我們也討論了算法的并行化，并研究了計算單元之間的負(fù)載均衡策略。我們還針對對k-plex規(guī)模的限制提出了一些近似算法策略以進(jìn)一步提高算法的性能。在這

3、一部分的最后，我們對算法和各種策略的效果進(jìn)行了實(shí)驗(yàn)并且進(jìn)行了分析。 應(yīng)用各種算法從網(wǎng)絡(luò)中挖掘出社群之后，為了進(jìn)一步應(yīng)用網(wǎng)絡(luò)社群信息，更好的了解在現(xiàn)實(shí)中社群的概況和動態(tài)，我們又提出了針對網(wǎng)絡(luò)社群的簡歷挖掘，并且研究了其中的三個問題：社群的特征化、社群的區(qū)分和社群演化歷史的挖掘。社群的特征化算法試圖提示社群形成的原因；社群區(qū)分算法則要尋找一個社群最獨(dú)特的特征；而社群的演化歷史挖掘則利用網(wǎng)絡(luò)中不同時刻的快照來挖掘社群的演化軌跡。最后，