基于社區(qū)發(fā)現的社交網絡結構洞并行迭代挖掘算法.pdf

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

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

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

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