[發(fā)明專(zhuān)利]一種基于局部結(jié)構(gòu)的密度最大化重疊社團(tuán)發(fā)現(xiàn)方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202010678380.X
• 申請(qǐng)日: 2020-07-15
• 公開(kāi)（公告）號(hào): CN111861772A
• 公開(kāi)（公告）日: 2020-10-30
• 發(fā)明（設(shè)計(jì)）人: 陳潔;王惠君;趙姝;張燕平
• 申請(qǐng)（專(zhuān)利權(quán)）人: 安徽大學(xué)
• 主分類(lèi)號(hào): G06Q50/00
• 分類(lèi)號(hào): G06Q50/00;G06K9/62;G06F16/953
• 代理公司: 合肥市浩智運(yùn)專(zhuān)利代理事務(wù)所(普通合伙) 34124
• 代理人: 張祥

1.一種基于局部結(jié)構(gòu)的密度最大化重疊社團(tuán)發(fā)現(xiàn)方法，其特征在于：包括以下步驟：

步驟A：將待劃分社團(tuán)的網(wǎng)絡(luò)抽象成由節(jié)點(diǎn)連接成的抽象網(wǎng)絡(luò)；

步驟B：根據(jù)節(jié)點(diǎn)的連接屬性，獲得每個(gè)節(jié)點(diǎn)的度，以度最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，將種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)添加到初始化社團(tuán)中；

步驟C：對(duì)剩余節(jié)點(diǎn)重復(fù)步驟B，直到抽象網(wǎng)絡(luò)中不存在未劃分的節(jié)點(diǎn)；

步驟D：將所有社團(tuán)從大到小排序，依次判斷小社團(tuán)中的節(jié)點(diǎn)能否添加到大社團(tuán)中，對(duì)初始化社團(tuán)進(jìn)行擴(kuò)張；

步驟E：對(duì)擴(kuò)張后的社團(tuán)判斷是否滿足合并條件，將滿足合并條件的社團(tuán)進(jìn)行合并，輸出社團(tuán)劃分結(jié)果。

2.根據(jù)權(quán)利要求1所述的一種基于局部結(jié)構(gòu)的密度最大化重疊社團(tuán)發(fā)現(xiàn)方法，其特征在于：步驟A中對(duì)原始社團(tuán)進(jìn)行抽象得到抽象網(wǎng)絡(luò)G＝(X,f,T)，其中，X是抽象網(wǎng)絡(luò)G中的節(jié)點(diǎn)集合，f是抽象網(wǎng)絡(luò)G中的連邊集合，T是抽象網(wǎng)絡(luò)G的拓?fù)浣Y(jié)構(gòu)，連邊為連接兩個(gè)節(jié)點(diǎn)的連接線。

3.根據(jù)權(quán)利要求2所述的一種基于局部結(jié)構(gòu)的密度最大化重疊社團(tuán)發(fā)現(xiàn)方法，其特征在于：步驟B中節(jié)點(diǎn)的度為與該節(jié)點(diǎn)的連邊總數(shù)，鄰居節(jié)點(diǎn)為與種子節(jié)點(diǎn)直接相連的節(jié)點(diǎn)。

4.根據(jù)權(quán)利要求3所述的一種基于局部結(jié)構(gòu)的密度最大化重疊社團(tuán)發(fā)現(xiàn)方法，其特征在于：步驟D中如果兩個(gè)社團(tuán)A、B中存在相同的節(jié)點(diǎn)，則判斷小社團(tuán)B中的其他節(jié)點(diǎn)能否添加的大社團(tuán)A中，方法為：

計(jì)算大社團(tuán)A的子圖密度，

其中，e_ij為社團(tuán)A中節(jié)點(diǎn)i,j的連邊，w(e_ij)為節(jié)點(diǎn)i,j之間的相似度，V(A)為社團(tuán)A中的節(jié)點(diǎn)數(shù)量；

計(jì)算社團(tuán)B中的節(jié)點(diǎn)j對(duì)社團(tuán)A的貢獻(xiàn)度C(j,A)，

其中，α∈(0,1)用來(lái)控制相似度值的比例，i為社團(tuán)A中的節(jié)點(diǎn)，w(e_ij)為節(jié)點(diǎn)i,j之間的相似度，Adj(i,j)為節(jié)點(diǎn)i,j之間的連接屬性，如果節(jié)點(diǎn)i,j存在連邊，Adj(i,j)＝1，否則為0；如果

C(j,A)≥a_nd(A)

則將節(jié)點(diǎn)j加入社團(tuán)A中，否則不添加；其中，

n＝|V(A)|,r≥1,t≥1

r和t為經(jīng)驗(yàn)值。

5.根據(jù)權(quán)利要求4所述的一種基于局部結(jié)構(gòu)的密度最大化重疊社團(tuán)發(fā)現(xiàn)方法，其特征在于：節(jié)點(diǎn)i和j的相似度計(jì)算方法為，

N_ij為節(jié)點(diǎn)i和j的共同鄰居節(jié)點(diǎn)。

6.根據(jù)權(quán)利要求5所述的一種基于局部結(jié)構(gòu)的密度最大化重疊社團(tuán)發(fā)現(xiàn)方法，其特征在于：步驟E中進(jìn)行社團(tuán)合并的條件為：

|C_A∩C_B|≥βmin(|C_A|,|C_B|)

如果滿足該條件，則合并社團(tuán)A和B，否則不能合并，其中，|C_A∩C_B|為社團(tuán)A和B所包含的共同節(jié)點(diǎn)的數(shù)量，|C_A|為社團(tuán)A所包含的節(jié)點(diǎn)的數(shù)量，min(|C_A|,|C_B|)表示社團(tuán)A和B的節(jié)點(diǎn)數(shù)的最小值；β∈(0,1)為經(jīng)驗(yàn)值。

7.一種基于局部結(jié)構(gòu)的密度最大化重疊社團(tuán)的發(fā)現(xiàn)系統(tǒng)，其特征在于：包括

網(wǎng)絡(luò)構(gòu)建模塊：將待劃分社團(tuán)的網(wǎng)絡(luò)抽象成由節(jié)點(diǎn)連接成的抽象網(wǎng)絡(luò)；

社團(tuán)劃分模塊：根據(jù)節(jié)點(diǎn)的連接屬性，獲得每個(gè)節(jié)點(diǎn)的度，以度最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，將種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)添加到初始化社團(tuán)中；對(duì)剩余節(jié)點(diǎn)重復(fù)以上劃分方法，直到抽象網(wǎng)絡(luò)中不存在未劃分的節(jié)點(diǎn)；

擴(kuò)張模塊：將所有社團(tuán)從大到小排序，依次判斷小社團(tuán)中的節(jié)點(diǎn)能否添加到大社團(tuán)中，對(duì)初始化社團(tuán)進(jìn)行擴(kuò)張；

合并模塊：對(duì)擴(kuò)張后的社團(tuán)判斷是否滿足合并條件，將滿足合并條件的社團(tuán)進(jìn)行合并，輸出社團(tuán)劃分結(jié)果。