基于社區(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ò)中的群落分布和競爭優(yōu)勢，是社會關(guān)系網(wǎng)絡(luò)分析中重要的基礎(chǔ)性研究，并已成為當(dāng)今學(xué)術(shù)界和工業(yè)界的熱點話題。
　　目前，經(jīng)典的社區(qū)發(fā)現(xiàn)算法包括Newman等人提出的GN算法及其改進、基于評價社區(qū)結(jié)構(gòu)的Q函數(shù)算法和基于clique發(fā)現(xiàn)的算法等。然而，這些算法時間復(fù)

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

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

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