基于GPGPU的復(fù)雜網(wǎng)絡(luò)分析算法的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、復(fù)雜網(wǎng)絡(luò)的研究可應(yīng)用于眾多領(lǐng)域之中，現(xiàn)實(shí)生活和研究領(lǐng)域的復(fù)雜系統(tǒng)均可看成是復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)的分析算法可以揭示出復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和特性，其中社團(tuán)結(jié)構(gòu)的識(shí)別和平均路徑長(zhǎng)度對(duì)于研究復(fù)雜網(wǎng)絡(luò)具有重要的理論意義和極大的應(yīng)用價(jià)值。但是，當(dāng)今所研究的復(fù)雜網(wǎng)絡(luò)的規(guī)模越來越大，如何在大規(guī)模的復(fù)雜網(wǎng)絡(luò)中準(zhǔn)確的、快速的識(shí)別出隱藏的社團(tuán)結(jié)構(gòu)以及快速正確的計(jì)算出平均路徑長(zhǎng)度是目前研究的熱點(diǎn)問題。GPU眾所周知由于其結(jié)構(gòu)特點(diǎn)，擁有強(qiáng)大的計(jì)算能力，適用于密集型計(jì)算而復(fù)

2、雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)識(shí)別以及平均路徑長(zhǎng)度計(jì)算的方法均為密集型的計(jì)算。因此考慮到對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)進(jìn)行分析的算法對(duì)于準(zhǔn)確性和即時(shí)性的要求，將GPU用于復(fù)雜網(wǎng)絡(luò)的分析算法中。
　　 本文對(duì)社團(tuán)結(jié)構(gòu)識(shí)別算法進(jìn)行分析，找出可以在GPU進(jìn)行并行的部分，設(shè)計(jì)并行策略并將其實(shí)現(xiàn)，將社團(tuán)結(jié)構(gòu)識(shí)別算法性能提高了2倍。通過進(jìn)一步對(duì)算法本身進(jìn)行優(yōu)化，并對(duì)優(yōu)化后的GPU并行實(shí)現(xiàn)，最終得出性能優(yōu)化后的GPU并行算法比優(yōu)化后的CPU串行算法性能提高了13倍。最