[發明專利]適用于社交網絡的基于核心三角的局部社團發現方法

在審

• 申請號: 201710372354.2
• 申請日: 2017-05-24
• 公開（公告）號: CN107222334A
• 公開（公告）日: 2017-09-29
• 發明（設計）人: 吳駿;王曉彤;喬羽;王崇駿
• 申請（專利權）人: 南京大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;G06Q50/00
• 代理公司: 南京瑞弘專利商標事務所(普通合伙)32249
• 代理人: 陳建和

技術領域

本發明涉及社會網絡分析中的社團發現領域，具體涉及一種基于核心三角用于分析社交網絡中的局部社團發現應用方法。

背景技術

目前，社團發現研究領域的研究熱點主要有社團的重疊性，局部社團發現，異構網絡的社團發現，動態網絡的社團發現等等。本發明著重于社團網絡的局部性特征。隨著社團發現研究的進展，以及現實世界中社交網絡規模的不斷增大，社團發現方法研究方向也逐漸向超大規模社交網絡的社團發現傾斜。在信息爆炸的當代，在海量數據生成的社交網絡之中，獲取網絡的全局結構信息變得十分困難，且通過全局的網絡結構信息來生成整個網絡的社團劃分所需時間及計算成本變得過于高昂。而傳統的應用于社交網絡之上的社團發現方法通常依賴于全局網絡結構信息的獲取，進而難以應用于大規模社交網絡，因此基于局部信息社團結構發現越來越受到重視。

所謂局部社團發現，即不依賴網絡全局結構信息，基于一個初始節點或社團，通過某個節點或者邊的局部信息進行擴散的方法。該類方法由于在生成一個社團時不需要獲取網絡的全局結構信息，大大加快了社團生成的速度。社交網絡規模通常非常龐大，獲取全局網絡的社團劃分通常成本較高且沒有必要，基于單個用戶的社團結構分析往往更具有實用價值。

發明內容

本發明即針對社交網絡的社團發現問題提出了一種解決方案，即適用于社交網絡的基于核心三角的局部社團發現方法。

具體技術方案如下：適用于社交網絡的基于核心三角的局部社團發現方法包括如下步驟：

1)核心三角選取階段：

a確定核心節點；

b找到核心節點與其鄰居節點構成的所有三角形；

c選取度數最高的作為核心三角；

d結束；

2)局部社團擴張階段：

a核心三角作為初始社團；

b計算每個社團鄰居節點的節點適應度；

c選取節點適應度最大的鄰居節點加入社團迭代生成局部社團；

d結束；

3)局部社團合并階段：

a計算兩局部社團之間相似度；

b基于相似度閾值兩兩合并局部社團；

c結束。

本發明中，步驟1)-a中所述核心節點由使用者自行確定。

本發明中，步驟1)-b中所述的三角形由以下公式定義：

T＝Δ{v_a|(v_b，v_c)∈A}

其中A是節點v_a的所有鄰居節點集合，v_b、v_c是集合A中的節點。

本發明中，2)-b中所述節點適應度的定義如下：

對于當前局部社團，社團適應度由以下公式定義：

其中，α∈(0，1]為一個用以控制社團規模大小的參數。為局部社團內部的邊度數，公式中為局部社團外部的邊度數；

根據以上局部社團適應度F_G的定義，可以給出一個不屬于社團G的節點v的節點適應度，即將節點v加入局部社團后，局部社團G的適應度的增量：

其中，F_G+v表示加入了節點v后的局部社團的適應度，F_G+v與F_G的差值即是節點v對局部社團G的適應度的貢獻度

本發明中，步驟3)-b中所述兩局部社團之間相似度由以下公式定義：

其中C_i∩C_j為社團C_i和C_j中共有節點總數，MIN(C_i，C_j)為C_i和C_j兩者中節點數最少的數值。制定參數∈，若兩社團間相似度將其合并為一個社團。

本發明的有益效果：本發明的一種適用于社交網絡的基于核心三角的局部社團發現方法，通過核心三角尋找，局部社團擴張等階段，能夠有效地生成社交網絡中局部社團結構劃分。有效解決了基于全局網絡結構信息的社團發現方法計算效率低的問題。

附圖說明

圖1為適用于社交網絡的基于核心三角的局部社團發現方法的流程圖。

圖2為選取核心三角的流程圖。

圖3為基于核心三角擴張生成一個局部社團的流程圖。

具體實施方式

為了更了解本發明的技術內容，特舉具體實施例并配合所附圖式說明如下。