引用

论文题目：基于 k-truss 的图社区发现算法研究
作者姓名：王岩

摘要

近几年图论领域提出一种新的运用团的思路来解决大型网络图中的图社区发现问题，即是通过团来定义图中拥有紧密关系的社区结构，进而只要在大图中查找出想要的团结构就能解决图社区发现问题。但是团由于本身定义太严格，在很多实际问题中不能得出想要的理想结果。更为严重的是精确的团查找、查找极大团等问题都是 NPC 问题。但是令人欣慰的是，最近又出现很多类团结构，例如 n-clan、k-core、k-truss等等。这些结构不仅不是 NPC 问题而且他们的结构特征更加符合实际生活中的社交网络模型。例如 k-truss 结构能很好的体现出一个社交网络中各个个体之间的关系。它的紧确程度要小于限制严格的团结构，但是大于 k-core 对于
个体之间关系限制程度的要求。

研究现状

复杂网络中的图社区发现问
题是解决图数据库管理的一种解决方法。而复杂网络中的图社区发现问题主要分为
两大类。一类是全局图社区发现方法，另一类是局部图社区发现方法。前者中包括
图划分方法、随机游走方法、模块度方法和密度子图方法。局部图社区方法中包括
基于模块度的方法和基于密度的方法两大类。在图划分方法中有很多著名的方法，
例如基于割的 KL 方法、G-N 算法、谱方法等；随机游走方法主要是 Markov链和随机游走；模块度的方法主要是指基于模块度的贪心算法和基于模块度的谱方法。密度子图方法主要包括以下下三个方面：枚举法、近似边界法和速启发式枚举法。枚举法中包括 clique、biclique、quasi-clique、k-core等不同的团结构和类团结构。近似边界法主要包括最大平均度数、最密集子图、θ密度子图等子图结构构成的解决方法。快速启发式枚举法包括极大 clique、极大k-core、极大 k-truss等几种类型。

目前的k-truss 算法主要是基于内存的算法、基于 I/O 操作的算法和基于 mapreduce 分布式算法。

基础知识

无向无权的简单图 G。

n = |V_G|表示简单图 G 中顶点的数量
m = |E_G|表示简单图 G 中边的数量
|G|=m+n 来代表图 G 的大小
nb(v)来表示顶点 v 的邻居集合，即nb(v)={u:(u,v) ~ E_G}
顶点 v 的度为 deg(v)= |nb(v)|。
本文图G用邻接表存储
图中每个顶点拥有一个惟一的 ID，并且顶点按照 ID 的大小进行升序排序。给定的任意两个顶点 u 和 v，本文使用 uv 或 vu 表示顶点 \Delta \forall \exists u 是否在顶点 v 之前。

支持度

在图 G 中的一条边 $e=(u，v)\in E_G$的支持度称为 sup(e，G)，定义为$|{ \Delta uvw:\Delta uvw\in\Delta G}|$，为了简单起见，本文在下文中均用符号 sup(e)来替换符号 sup(e，G)。
简单的说，图 G 中的一条边 e 的支持度就是利用这条边的三角形的个数。现在本文定义 k-truss。

k-truss

k-truss 是一个图 G 中的一个极大的子图，记为$Tk(k≥2)$，这个子图中的任意条边的支持度都大于等于(k-2)。用符号表示：$\forall e~E{Tk}，sup(e,T_k)>=(k−2)$。那么根据定义，2-truss 就是图 G 本身。

truss number

边所在的 k-truss 中极大的 k 值。符号表示为$(e)=max{k:e\in E{Tk}}$。即这条边$e\in E{TK}且e\in E_{TK+1}$。用K_max表示图G中每条边 e 的 truss number。

k-class

在图G 中所有 truss number 都为 k 边的集合称为k-class，记为。符号定义为:${e:e\in E_G,}$

k-truss和k-core的区别

k-truss 通过强制所有的边中包含至少(k−2)个三角形，进而加强到每条边都拥有至少(k−2)强关系。直观地说，本文在一个社交网络中两个人拥有的共同的朋友越多说明他们之间的关系越紧密。相反，k-core 仅仅是简单的边连接关系(即顶点的度)，只能整个朋友圈中的每个朋友都拥有很多朋友，但是不去强调任意两个朋友之间的关系是否非常紧密。

k-truss基本算法

迭代法

每条边被多少个三角形所利用来定义此支持度。然后基于整个图中每条边的支持度，利用类贪心算法的原理逐步去除图中
支持度值不足的边，然后重新计算新图中每天边的支持度再次迭代删除支持度不足的边，直到图中的边不能删除时停止算法。具体的基于内存的极大 k-truss 查找算法执行过程如算法所示。

未完不待续。。。

基于 k-truss 的图社区发现算法研究

引用

摘要