[發明專利]一種k?core?truss社區模型及分解、搜索算法

在審

• 申請號: 201611221291.2
• 申請日: 2016-12-26
• 公開（公告）號: CN106844500A
• 公開（公告）日: 2017-06-13
• 發明（設計）人: 李振軍;李榮華;楊烜;毛睿;郭君
• 申請（專利權）人: 深圳大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06Q50/00
• 代理公司: 深圳市恒申知識產權事務所(普通合伙)44312
• 代理人: 王利彬

技術領域

本發明屬于圖和社區網絡的社交挖掘技術領，尤其涉及一種k-core-truss社區模型及分解、搜索算法。

背景技術

隨著科學技術的迅猛發展，社會上的各行各業都積累和采集了大量的圖數據，例如在線社交網絡中的社交圖譜、因特網的網絡拓撲、銀行信貸網絡、蛋白質交互網絡、公路交通網絡、無線傳感器網絡、通訊網絡、以及智能電網等等。這些圖數據有兩個較為顯著的特性：一是它們的規模龐大，圖中頂點的數目往往都是千萬乃至十億級別，比如社交網絡的臉書圖譜、騰訊QQ網絡以及新浪微博圖譜等；二是這些圖數據中往往都存在頂點之間緊密相連的凝聚子圖(cohesive subgraph)結構。

近年來，對圖和社交網絡中的社區挖掘問題引起學術界和工業界了廣泛的關注。在社區挖掘問題上，大多數的研究工作僅致力于探測原圖中的社區結構。然而，在很多應用情景中，我們關心的是找出包含查詢節點的社區結構。例如，在一個社交網絡中，我們要查詢某個或者幾個用戶所在的社區結構，進而了解他們的共同興趣愛好，或者團體活動等；再比如在電話通信網絡中，我們要查詢一個用戶與其緊密聯系的一個社群，進而了解其的社會關系網絡，這一應用有助于幫助公安刑偵，打擊團伙犯罪，恐怖組織等。這些應用都需要解決對于給定的一個或者多個查詢節點的社區搜索問題。

在圖的社區搜索上，主要包括兩種代表性的模型，k-核(k-core)及k-truss。k-core的概念是由Seidman首次提出的。k-core是一個誘導子圖，該子圖中的頂點的度都大于或等于k，且該子圖是具備這種性質的最大子圖。為了求解大圖數據的k-core分解問題，Vladimir和Matjaz率先提出了一個線性時間算法。該算法依次從圖中刪除度最小的頂點，并利用一個類似于桶排序的數據結構來組織頂點，從而實現快速的k-core計算。該算法首先是發現core數較低的頂點，然后依次發現core數較高的頂點。正因為K-core主要關注圖中度數較高的節點，往往會忽略一些度數較低但卻在現實中有關聯的社區。

相對于k-core，k-truss是一個較新的概念，這一概念是由Cohen首次提出。同樣的，k-truss也是一個誘導子圖，該子圖中的任意一條邊都至少包含在k-2個三角形中，且該子圖是具備這種性質的最大子圖。最大k-邊連通子圖同樣也是一個誘導子圖，該子圖中的任意兩個頂點都至少存在k條邊不相交的路徑，且該子圖是具備這種性質的最大子圖。值得注意的是，一個k-truss是一個(k-1)-core，反之不一定成立。由此可見，k-truss是一種精煉的k-core結構。然而，與k-core不同的是，k-truss的定義是基于圖中頂點所形成的三角形結構。因此，對于那些三角形較為稀少的網絡(例如二分圖或近似二分圖)，這種定義并不合適。這是因為這種三角形稀少的網絡可能依舊存在凝聚子圖的結構。但是，根據k-truss的定義，我們無法發現這一結構，這是k-truss定義的一個最主要缺陷。

發明內容

本發明實施例提供一種k-core-truss社區模型，旨在解決現有技術中k-core及k-truss模型不能全面挖掘凝聚子圖的技術問題。

本發明實施例是這樣實現的，一種k-core-truss社區模型，包括一個無向、無權圖G＝(V，E)，在圖G中具有一個最大子圖，所述子圖滿足：每條邊e的度≥α*k或者邊e被包含在k-2個三角形中；

對于圖G的任意節點u，其核值core(u)＝max{k|u∈V_k-core}，其中V_k-core為圖G中的k-core社區；

對于圖G中的任意邊e，其trussnessλ(e)＝max{k|e∈E_k-truss}，其中E_k-truss為圖G中的k-truss社區；

對于圖G中的任意邊e，其最大度δ(e)＝min(core(u),core(v))；

其中，邊e＝(u,v)，節點u的度為deg(u)＝|{v|(u,v)∈E}|，邊e的度為d(e)＝min{deg(u),deg(v)}，圖G中節點的最大度為dmax，參數α>0，k≥3。

優選地，當α*k>d_max時，所述k-core-truss社區模型為k-truss模型。

優選地，當α*k≤(k-1)時，所述k-core-truss社區模型為α*k-core模型。

優選地，當α＝1/k，整個圖G都為k-core-truss社區。