[發(fā)明專利]基于社區(qū)緊密度的快速社區(qū)發(fā)現(xiàn)方法

無效

• 申請?zhí)枺?/td>: 201110177772.9
• 申請日: 2011-06-28
• 公開（公告）號: CN102779142A
• 公開（公告）日: 2012-11-14
• 發(fā)明（設(shè)計(jì)）人: 藺智挺;吳秀龍;陳軍寧;孟堅(jiān);徐超;李正平;譚守標(biāo)
• 申請（專利權(quán)）人: 安徽大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)技術(shù)，其特征在于，該技術(shù)基于一種緊密度矩陣，并且實(shí)現(xiàn)的復(fù)雜度接近線性。

2.根據(jù)權(quán)利要求1所述的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)技術(shù)，其特征在于，所述的緊密度矩陣中的元素記錄的是當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)下任意兩個(gè)社區(qū)之間的緊密度值。

3.根據(jù)權(quán)利要求1所述的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)技術(shù)，其特征在于，所述的技術(shù)實(shí)現(xiàn)的復(fù)雜度在最壞情況下為?其中m為網(wǎng)絡(luò)中的總邊數(shù)，?是劃分出的社區(qū)的平均節(jié)點(diǎn)度，t代表該技術(shù)在實(shí)現(xiàn)過程中迭代的次數(shù)。

4.根據(jù)權(quán)利要求1中所述的社區(qū)結(jié)構(gòu)發(fā)現(xiàn)技術(shù)，其特征在于，該技術(shù)包含三方面的工作，分別為計(jì)算緊密度矩陣，合并社區(qū)以及更新緊密度矩陣。

5.根據(jù)權(quán)利要求4中所述的計(jì)算緊密度矩陣，其特征在于，在計(jì)算過程中對于如下兩種情況，計(jì)算的方法是不同的

A、當(dāng)前網(wǎng)絡(luò)是無權(quán)網(wǎng)

B、當(dāng)前網(wǎng)絡(luò)是加權(quán)網(wǎng)。

6.根據(jù)權(quán)利要求5中所述的計(jì)算緊密度矩陣，其特征在于，在情況A下計(jì)算緊密度矩陣時(shí)，包括如下情況

A1、當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有一個(gè)共同的鄰接點(diǎn)k(稱為公共鄰接點(diǎn))時(shí)，則節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的緊密度會增加1

A2、當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有多個(gè)公共鄰接點(diǎn)時(shí)，則節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的緊密度值則增加相應(yīng)次。

7.根據(jù)權(quán)利要求5中所述的計(jì)算緊密度矩陣，其特征在于，在情況B下計(jì)算緊密度矩陣時(shí)，包括如下情況

B1、當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j有公共鄰接點(diǎn)k時(shí)，則節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的緊密度值將增加?其中a_ij是當(dāng)前網(wǎng)絡(luò)的鄰接矩陣中的元素

B2、當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間公共鄰接點(diǎn)有多個(gè)時(shí)，節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的緊?密度值增加的值則為?其中a_ij是當(dāng)前網(wǎng)絡(luò)的鄰接矩陣中的元素，τ(i)是頂點(diǎn)i的鄰接點(diǎn)的集合，k指節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的公共鄰接點(diǎn)。

8.根據(jù)權(quán)利要求4中所述的合并社區(qū)，其特征在于，該工作通過累加即將合并的社區(qū)之間的緊密度值來更新緊密度矩陣M，并且使用新的M矩陣來重復(fù)這個(gè)合并過程。

9.根據(jù)權(quán)利要求4中所述的更新緊密度矩陣，其特征在于，假定在社區(qū)合并之前有k個(gè)社區(qū)，其相應(yīng)的緊密度矩陣為k×k維的矩陣M_k×k，而合并后的社區(qū)個(gè)數(shù)為k′，則該工作包含以下步驟

a、首先，初始化一個(gè)k′×k′的矩陣M′

b、然后計(jì)算合并前的社區(qū)集合中任意兩個(gè)社區(qū)間的緊密度值；

c、再就是歸一化緊密度值，并記入M′。

10.根據(jù)權(quán)利要求9中所述步驟，最后得到的M′就是M被更新后的矩陣。?