社会网络图挖掘
社会网络中的一个很重要的问题是识别『社区』，而所谓的社区是指具有非同寻常的强连通性的节点子集（节点可以是构成网络的人或其他实体）。举例来说，同一社区的人通常互相认识，而不同社区的人很少会认识对方。
社会网络可以很自然的用图来建模，有时被称为社会图。社会图通常是无向图，比如朋友关系，但也可以是有向图，比如微博的关注关系。
有的社会现象会涉及多个不同类型的实体，那这样的图就会由多个类型的节点构成，同类节点之间不连接，描述这种信息很自然的可以采用k分图。
使用传统的聚类算法对社会网络聚类会存在不少问题，有人提出了多种发现社会网络社区的专用聚类技术，这里先介绍中介度。
一条边的中介度定义为节点对(x,y)的数目，其中(a,b)处于(x,y)的最短路径上。(a,b)的中介度高，说明它们处于两个社区之间，也就是说a和b更倾向于不属于同一社区。
为了利用边的中介度，必须要计算所有边上的最短路径数目，这里采用Girvan-Newman算法。该算法访问每个节点X一次，计算X到其他连接节点的最短路径数目。算法首先从节点X开始对图进行广度优先搜索（BFS）。在BFS表示中，每个节点的深度就是该节点到X的最短路径长度。因此处于统一深度的两个节点之间的边永远都不可能处于X到其他点的最短路径上。
GN算法的第二步是将每个节点用根节点到它的最短路径的数目在标记。首先将根基点标记为1，然后从上往下，将每个节点Y标记为其所有父节点上的标记值之和，如下图所示：
第二步是一个准备阶段，GN算法的第三步真正去求每条边的中介度。其整个计算规则如下：
- 图中的每个叶节点（叶节点指那些不存在与下层节点的边的节点）都赋予分值1（这里的分值和上面的标记值不是一个意思）
- 每个非叶节点给的分值是1加上从该节点到其下层节点的所有边的分值之和
- 下层节点根据第二步的标记值分配自己的分值给到上层节点的边
当每个节点都作为根节点计算过一遍之后，将每条边的分值求和。由于每条最短路径会重复发现两次（以这条边的不同节点为根节点），因此最后每条边的分值还要再除以2
给张图会好理解一些：
从下到上进行计算，先给A、C、G这三个叶子节点赋予分值1，然后把自己的分值向上传给边，如果就一条边，就把自己的分值全部赋予这条边，如果有多条边，按照第二步里的标记值的比例关系划分，第二步中，G上面的D和F的标记值都是1，所以这里G的分值也平分给到D和F的两条边，将边的分值求和加1得到自己的分值，再按同样的规则往上计算，直到根节点。
我们可以利用中介度来发现社区，比如优先去除掉中介度高的边。利用中介度来划分社区非常便捷，但缺点是它不可能把一个点划分到两个社区中。
我们也可以通过在社会图中寻找二分图的方式来发现社区，完全二分图包括两组节点，两组之间的所有节点对都存在边，而每组内部节点之间不存在边。任一足够密集的社区（存在很多边的节点子集）都包含一个大的完全二分图。
我们可以利用发现频繁项集的技术来发现完全二分图。我们可以选定二分图的一边看成购物篮，这一边中某个节点的购物篮是其邻接节点集合，而每个邻接节点可以看成项。一个两组节点集合大小分别为t和s的完全二分图可以看成是寻找支持度为s、大小为t的频繁项集。
更详细一点说，我们可以通过计算给定t大小项集的平均支持度，来推断出社区中存在什么样的二分图实例。
