基于社區(qū)發(fā)現(xiàn)的社交網(wǎng)絡(luò)結(jié)構(gòu)洞并行迭代挖掘算法.pdf

1、隨著Facebook，Twitter等網(wǎng)站的興起，社交網(wǎng)絡(luò)的規(guī)模日趨復(fù)雜和龐大。通常，網(wǎng)絡(luò)呈現(xiàn)社區(qū)分布結(jié)構(gòu)，而社區(qū)間非冗余關(guān)系的存在形成了網(wǎng)絡(luò)的漏洞。分析這些社區(qū)和漏洞可以了解網(wǎng)絡(luò)中的群落分布和競(jìng)爭(zhēng)優(yōu)勢(shì)，是社會(huì)關(guān)系網(wǎng)絡(luò)分析中重要的基礎(chǔ)性研究，并已成為當(dāng)今學(xué)術(shù)界和工業(yè)界的熱點(diǎn)話題。
　　目前，經(jīng)典的社區(qū)發(fā)現(xiàn)算法包括Newman等人提出的GN算法及其改進(jìn)、基于評(píng)價(jià)社區(qū)結(jié)構(gòu)的Q函數(shù)算法和基于clique發(fā)現(xiàn)的算法等。然而，這些算法時(shí)間復(fù)

2、雜度較高，不適用于大型社交網(wǎng)絡(luò)的處理。本文借鑒COPRA算法的標(biāo)簽傳播機(jī)制，簡(jiǎn)化社區(qū)發(fā)現(xiàn)的過(guò)程，提出一種基于BSP模型的并行迭代算法PCOPRA，并最終應(yīng)用于BC-BSP系統(tǒng)中。與此同時(shí)，針對(duì)COPRA算法的缺點(diǎn)，本文進(jìn)行了兩點(diǎn)改進(jìn):(1)為避免因COPRA算法的同步標(biāo)簽傳播而導(dǎo)致的標(biāo)簽振蕩現(xiàn)象，使得算法無(wú)法收斂;也為避免因異步標(biāo)簽傳播而導(dǎo)致挖掘結(jié)果的不穩(wěn)定，本文提出了標(biāo)簽傳播的半異步迭代機(jī)制。通過(guò)同/異步交替運(yùn)行的方式，算法可結(jié)合兩種

3、迭代各自的優(yōu)點(diǎn)，在確保結(jié)果穩(wěn)定性的同時(shí)加快算法收斂速度，獲得更好的性能。(2)為避免COPRA算法因?qū)W(wǎng)絡(luò)未知全局參數(shù)的過(guò)度依賴而影響社區(qū)挖掘結(jié)果的準(zhǔn)確性，本文通過(guò)各節(jié)點(diǎn)對(duì)周圍鄰居社區(qū)情況的判別來(lái)自主決定網(wǎng)絡(luò)參數(shù)，增加了社區(qū)發(fā)現(xiàn)過(guò)程的靈活性，提高了挖掘效率。除此之外，為支持標(biāo)簽的異步迭代更新，本文對(duì)BC-BSP系統(tǒng)的同步模型做了擴(kuò)展。通過(guò)在當(dāng)前超步提前獲取下一超步的消息來(lái)實(shí)現(xiàn)頂點(diǎn)的跨步更新，用以支持對(duì)增量迭代、標(biāo)簽傳播等應(yīng)用的快速處理。

4、
　　社交網(wǎng)絡(luò)上的結(jié)構(gòu)洞挖掘仍缺乏一個(gè)完備的理論算法，特別是對(duì)大型網(wǎng)絡(luò)的挖掘。針對(duì)以上問(wèn)題，本文貢獻(xiàn)如下：(1)基于社區(qū)發(fā)現(xiàn)的結(jié)果，并借鑒Tang等人提出的HIS結(jié)構(gòu)洞模型，設(shè)計(jì)并實(shí)現(xiàn)了一種改進(jìn)后的基于BSP模型的并行結(jié)構(gòu)洞挖掘算法PHIS，并最終應(yīng)用于BC-BSP系統(tǒng)之上。(2)通過(guò)對(duì)節(jié)點(diǎn)更新規(guī)則的分析，從減少節(jié)點(diǎn)計(jì)算量和消息通信量的角度對(duì)算法進(jìn)行了優(yōu)化，很大程度地提升了性能。
　　本文所提出的并行化算法基于BSP模型。實(shí)