[發(fā)明專(zhuān)利]重疊社區(qū)并行發(fā)現(xiàn)的方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 201410302016.8
• 申請(qǐng)日: 2014-06-27
• 公開(kāi)（公告）號(hào): CN105302823A
• 公開(kāi)（公告）日: 2016-02-03
• 發(fā)明（設(shè)計(jì)）人: 徐敏;周修莊;劉卉;吳敏華;周麗娟
• 申請(qǐng)（專(zhuān)利權(quán)）人: 首都師范大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京科龍寰宇知識(shí)產(chǎn)權(quán)代理有限責(zé)任公司 11139
• 代理人: 孫皓晨;朱世定

1.一種重疊社區(qū)并行快速發(fā)現(xiàn)方法，其特征在于，包括以下步驟：

S1：從數(shù)據(jù)集文件中讀取節(jié)點(diǎn)分布網(wǎng)絡(luò)圖；創(chuàng)建社區(qū)集合；將所述節(jié)點(diǎn)分布網(wǎng)絡(luò)圖與所述社區(qū)集合相關(guān)聯(lián)；

S2：設(shè)定初始社區(qū)的個(gè)數(shù)為n；計(jì)算所述節(jié)點(diǎn)分布網(wǎng)絡(luò)圖中每個(gè)節(jié)點(diǎn)的度數(shù)，并獲取前n個(gè)節(jié)點(diǎn)度數(shù)最高的節(jié)點(diǎn)分別作為n個(gè)初始社區(qū)的中心節(jié)點(diǎn)；此時(shí)每個(gè)初始社區(qū)的聚集度為0；n個(gè)初始社區(qū)儲(chǔ)存于所述社區(qū)集合；

S3：對(duì)上述n個(gè)初始社區(qū)的每一個(gè)同時(shí)執(zhí)行以下程序：將所述中心節(jié)點(diǎn)的直接相鄰節(jié)點(diǎn)選為該社區(qū)的候選成員節(jié)點(diǎn)，并將所述候選成員節(jié)點(diǎn)加入該社區(qū)的候選成員集合；依次判斷所述候選成員集合中的所述候選成員節(jié)點(diǎn)是否屬于該社區(qū)，將屬于該社區(qū)的節(jié)點(diǎn)并入該社區(qū)，對(duì)屬于該社區(qū)的節(jié)點(diǎn)的直接相鄰節(jié)點(diǎn)選為該社區(qū)的候選成員節(jié)點(diǎn)，重復(fù)該步驟；對(duì)不屬于該社區(qū)的節(jié)點(diǎn)移出所述候選成員集合；將該社區(qū)數(shù)據(jù)存入所述社區(qū)集合；

S4：判斷所述節(jié)點(diǎn)分布網(wǎng)絡(luò)圖中是否有節(jié)點(diǎn)未并入任何社區(qū)，若是，則對(duì)未并入任何社區(qū)的節(jié)點(diǎn)重復(fù)執(zhí)行步驟S2、S3、S4，直至所述節(jié)點(diǎn)分布網(wǎng)絡(luò)圖中的所有節(jié)點(diǎn)都屬于一個(gè)社區(qū)；

S5：對(duì)所述社區(qū)集合中的所有社區(qū)兩兩計(jì)算其社區(qū)重疊度，若兩個(gè)社區(qū)的所述社區(qū)重疊度大于設(shè)定閾值，則將該所述社區(qū)重疊度大于設(shè)定閾值的兩個(gè)社區(qū)合并為一個(gè)社區(qū)，并更新所述社區(qū)集合的相應(yīng)數(shù)據(jù)；

S6：對(duì)所述社區(qū)集合中任意兩個(gè)具有公共節(jié)點(diǎn)的社區(qū)，計(jì)算將其合并為一個(gè)新社區(qū)的新社區(qū)聚集度，將該新社區(qū)聚集度分別與合并前該兩個(gè)具有公共節(jié)點(diǎn)的社區(qū)的所述社區(qū)聚集度進(jìn)行對(duì)比，若該新社區(qū)聚集度分別大于合并前該兩個(gè)具有公共節(jié)點(diǎn)的社區(qū)的所述社區(qū)聚集度，則將該兩個(gè)具有公共節(jié)點(diǎn)的社區(qū)合并為一個(gè)新社區(qū)，該新社區(qū)聚集度為該兩個(gè)具有公共節(jié)點(diǎn)的社區(qū)合并后的新社區(qū)的社區(qū)聚集度，并更新所述社區(qū)集合的相應(yīng)數(shù)據(jù)。

2.根據(jù)權(quán)利要求1所述的重疊社區(qū)并行快速發(fā)現(xiàn)方法，其特征在于，步驟S3中，對(duì)上述n個(gè)初始社區(qū)的每一個(gè)同時(shí)執(zhí)行的程序以多線(xiàn)程并行方式實(shí)現(xiàn)，判斷所述候選成員集合中的節(jié)點(diǎn)是否屬于該社區(qū)的方法是：計(jì)算每個(gè)所述候選成員節(jié)點(diǎn)的節(jié)點(diǎn)貢獻(xiàn)度；將所述節(jié)點(diǎn)貢獻(xiàn)度為1的節(jié)點(diǎn)并入該社區(qū)，并計(jì)算該社區(qū)的初始社區(qū)聚集度；對(duì)于所述節(jié)點(diǎn)貢獻(xiàn)度不為1的節(jié)點(diǎn)，根據(jù)其所述節(jié)點(diǎn)貢獻(xiàn)度由高到底進(jìn)行排序，并從其中所述節(jié)點(diǎn)貢獻(xiàn)度最高的節(jié)點(diǎn)開(kāi)始，依次假設(shè)所述候選成員集合中的節(jié)點(diǎn)屬于該社區(qū)并計(jì)算該社區(qū)的第一中間社區(qū)聚集度，假設(shè)不將所述候選成員集合中的節(jié)點(diǎn)并入時(shí)該社區(qū)的聚集度為初始聚集度，該社區(qū)若該第一中間社區(qū)聚集度大于該初始社區(qū)聚集度，則將相應(yīng)節(jié)點(diǎn)并入該社區(qū)；若該第一中間社區(qū)聚集度小于該初始社區(qū)聚集度，則相應(yīng)節(jié)點(diǎn)及其后面的節(jié)點(diǎn)不并入該社區(qū)，當(dāng)沒(méi)有所述第一中間社區(qū)聚集度大于該初始社區(qū)聚集度時(shí)判斷為該社區(qū)發(fā)現(xiàn)完畢，該初始社區(qū)聚集度即為該社區(qū)的社區(qū)聚集度。

3.根據(jù)權(quán)利要求1所述的重疊社區(qū)并行快速發(fā)現(xiàn)方法，其特征在于，步驟S3中，對(duì)上述n個(gè)初始社區(qū)的每一個(gè)同時(shí)執(zhí)行的程序在MapReduce框架下實(shí)現(xiàn)，判斷所述候選成員集合中的節(jié)點(diǎn)是否屬于該社區(qū)的方法是：

分別假設(shè)所述候選成員集合中的所有節(jié)點(diǎn)屬于該社區(qū)，同時(shí)分別計(jì)算所述候選成員集合中的節(jié)點(diǎn)屬于該社區(qū)時(shí)該社區(qū)的第二中間社區(qū)聚集度，并將所述候選成員集合中的所有節(jié)點(diǎn)按照所述第二中間社區(qū)聚集度從大到小進(jìn)行排序，假設(shè)不將所述候選成員集合中的節(jié)點(diǎn)并入時(shí)該社區(qū)的聚集度為初始聚集度，依次用各節(jié)點(diǎn)的所述第二中間社區(qū)聚集度與該初始社區(qū)聚集度比較，若節(jié)點(diǎn)的所述第二中間社區(qū)聚集度大于該初始社區(qū)聚集度，則將相應(yīng)的節(jié)點(diǎn)并入該社區(qū)；若該第二中間社區(qū)聚集度小于該初始社區(qū)聚集度，則相應(yīng)節(jié)點(diǎn)機(jī)器后面的節(jié)點(diǎn)不并入該社區(qū)，當(dāng)沒(méi)有所述第一中間社區(qū)聚集度大于該初始社區(qū)聚集度時(shí)判斷為該社區(qū)發(fā)現(xiàn)完畢，該初始社區(qū)聚集度即為該社區(qū)的社區(qū)聚集度。