然后再说一下图划分问题。先给出一个比较好的图切割方法，叫做归一化割，归一化割的公式如下：
归一化割的本质是一种切分效果评价标准，如果我们将S和T切开，Cut(S,T)定义为连接S中节点和T中节点的边的数目，Vol(S)定义为，至少有一个端点在S中的边的数目。
我们计算切分的归一化割，找到使归一化割最小的切分。
然后再讲一下拉普拉斯矩阵，在这之前首先要介绍邻接矩阵，就是如果节点i和j之间有边，那么矩阵的第i行、第j列的元素为1，否则为0。邻接矩阵是对称阵，且对角线上对的元素均为0
然后还要介绍度数矩阵，度数矩阵是对角阵，只有对角线上有元素，第i行第i个元素给出的是第i个节点的度数。
假定某个图有邻接矩阵A和度数矩阵D，那这个图的拉普拉斯矩阵就定义为L=D-A。
那图的拉普拉斯矩阵有什么用呢，我们计算出拉普拉斯矩阵第二小的特征值对应的特征向量，然后将特征向量中的正负值对应的节点分成两组，通常能得到不错的效果。
然后是重叠社区问题，考虑这样的情况：
其实很多时候，如上图所示，多个社区交集内的边可能会更加密集，因为他们（同属于多个社区的人）有了更多认识的可能性。
针对这样的问题，有一种关系图模型的机制，该机制可以从社区生成社会网络图。一旦明白该模型的参数如何影响观察到的给定图，就可以想办法利用最大似然估计来求得参数值。社区-关系图机制中的规定如下：
- 存在给定数目的社区，存在给定数目的个体（图的节点）
- 每个社区可以拥有任意的个体集合作为成员，也就是说，个体对社区的隶属关系是模型的参数
- 每个社区C都有一个pc与之关联，该概率表示C中两个成员由于都是C中成员而通过边连接的概率。这些概率也是模型的参数
- 如果一对节点属于两个或更多社区，那么如果包含这两个节点的社区按照上一条规则判定节点间有边的话，它们之间就有边
这其实就是一个生成模型。
另外，因为对每个社区来说，存在因为该社区而导致两个成员成为朋友的概率，因此，两个节点间有边的概率是1减去所有包含两个成员的社区都不导致两者有边的概率的乘积。然后我们利用最大似然估计和梯度下降法来找到模型的最优参数。
当然，这里直接使用梯度下降会有点问题，因为如果隶属或者不隶属以0和1表示，梯度下降法是无法处理这种不连续的数据的，我们将这种隶属关系修改为隶属强度，越接近0，是成员的可能性就越低。然后就可以利用梯度下降法求解了。
然后是SimRank，SimRank也是一种链接分析算法，它可以计算多类型节点图中两个点之间的相似度，其基本思路是，让一个随机游走者从某个点出发进行游走，并且在相同节点上有一个固定的重启概率（类似于PageRank中以远程跳转来缓解链接陷阱的影响）。游走着的期望分布概率可以看成节点到起始节点的一个很好的相似度度量。如果需要得到所有节点对之间的相似度，就需要以每个节点为初始点重复上述过程。与PageRank一样，SimRank在迭代中也会有震荡，整个收敛会需要时间，但一般而言，对于任意连通的k分图来说，都会收敛。
