使用许多互联网数据，我们都可以构建出这样的网络，其节点为某一种信息资源，如图片，视频，帖子，新闻等，连边为用户在资源之间的流动。对于这样的网络，使用社区划分算法可以揭示信息资源之间的相关性，这种相关性的发现利用了用户对信息资源的处理信息，因此比起单纯使用资源本身携带的信息来聚类（例如，使用新闻包含的关键词对新闻资源进行聚类），是一种更深刻的知识发现。

　　社区划分的算法比较多，大致可以分为两大类：拓扑分析和流分析。前者一般适用于无向无权网络，思路是社区内部的连边密度要高于社区间。后者适用于有向有权网络，思路是发现在网络的某种流动（物质、能量、信息）中形成的社区结构。这两种分析各有特点，具体应用取决于网络数据本身描述的对象和研究者想要获得的信息。

我们可以将已知的一些算法归入这两类：

　　Q-Modularity是一个定义在[-0.5,1)区间内的指标，其算法是对于某一种社区结构，考虑每个社区内连边数与期待值之差。实际连边越是高于随机期望，说明节点越有集中在某些社区内的趋势，即网络的模块化结构越明显。Newman在2004年提出这个概念最初是为了对他自己设计的社区划算法进行评估，但因为这个指标科学合理，而且弥补了这个方面的空白，迅速成为一般性的社区划分算法的通用标准。 Q的具体计算公式如下：

其中A是网络G对应的邻接矩阵，如果从i到j存在边，则Aij=1，否则为0。m是总连接数，2m是总度数，Aij/2m是两节点之间连接的实际概率。Ki和kj分别是i和j的度数。如果我们保持一个网络的度分布但对其连边进行随机洗牌，任意一对节点在洗牌后存在连接的概率为kikj/(2m)2。上式中中括号表达的就是节点之间的实际连边概率高于期待值的程度。后面跟着一个二元函数，如果节点ij属于同一个社区，则为1，否则为0，这就保证了我们只考虑社区内部的连边。刚才这个定义是以节点为分析单位。实际上，如果以社区为分析单位看Q指标，可以进一步将其化简为eii和ai之间的差。其中eii是在第i个社区内部的link占网络总link的比例，ai是第i个社区和所有其他社区的社区间link数。

上式已经清楚定义了Q，但在实际计算里，上式要求对社区及其内部节点进行遍历，这个计算复杂度是很大的。Newman(2006)对上式进行了化简，得到矩阵表达如下： 我们定义Sir为n * r的矩阵，n是节点数，r是社区数。如果节点i属于社区r，则为1，否则为0。

于是有

其中B是modularity matrix，其元素为

该矩阵的行列和都是0，因为实际网络和随机洗牌后的网络度分布是不变的。特别地，在仅仅有两个社区的情况下（r=2），可以s定义为一个n长的向量，节点属于一个社区为1，属于另一个社区为-1，Q可以写成一个更简单的形式：

通过对社区的划分可能空间进行搜索，可以得到最大化Q值的社区划分。在这个过程会涉及数值优化的部分，例如表一中的fast greedy和multilevel就是用不同方法进行快速搜索的例子。以fast greedy为例Newman（2006），它通过不断合并社区来观察Q的增加趋势，得到了一个在最差的情况下复杂度约为O( |E|*log(|V|) )，在最好的情况下接近线性复杂度的算法。

　　这个思路出现得比较早(Newman, 2001)。Freeman (1975) 提出过一个叫betweenness的指标，它衡量的是网络里一个节点占据其他n-1节点间捷径的程度。具体而言，首先对每一对节点寻找最短路径，得到一个n * (n-1)/2的最短路径集合S，然后看这个集合中有多少最短路径需要通过某个具体的节点。Newman借鉴了这个标准，但不是用来分析节点而是分析连边。一个连边的edge betweenness就是S集合里的最短路径包含该连边的个数。 定义了连边的betweenness后，就可以通过迭代算法来进行社区划分了。具体做法是先计算所有连边的betweenness，然后去除最高值连边，再重新计算，再去除最高值连边，如此反复，直到网络中的所有连边都被移除。在这个过程中网络就逐渐被切成一个个越来越小的component。在这个过程中，我们同样可以用Q-modularity来衡量社区划分的结果。这种算法定义比较清晰，也不涉及矩阵数学等运算，但问题是计算复杂度比较大。

　　一个有n个节点的网络G可以被表达为一个n x n的邻接矩阵（adjacency matrix）A。在这个矩阵上，如果节点i和j之间存在连边，则Aij=1，否则为0。当网络是无向的时候，Aij=Aji。另外我们可以构造n x n的度矩阵（degree matrix）D。D对角线上的元素即节点度数，例如Dii为节点i的度数，所有非对角线的元素都是0。无向网的分析不存在度数的选择问题，有向网则要根据分析目标考虑使用出度还是入度。将度数矩阵减去邻接矩阵即得到拉普拉斯矩阵，即L = D-A。

　　L的特征根lambda_0 {a, c, d, e}, {b, h}, {e, f}}。回到图中考察，我们发现这个社区分类基本是合理的。