毕业论文移动版

2。2 复杂网络

根据钱学森的定义，复杂网络（Complex Network）是指具有自组织、自相似、吸引子、小世界、弱连接性、无标度中部分或全部性质的网络。不难发现，社交网络复合复杂网络中小世界性、弱连接性、以及无标度性的特点，所以，社交网络属于一种典型的复杂网络。其中，小世界性指的是在存在巨大数量的节点的情况下，任意两个节点可以以较少的步骤连接起来。这与前文提及社交网络的六度分离原理是相吻合的。一个节点关系较为疏远的节点之间的关系称为弱连接性，一般而言，人们认为强链接，即关系较为密切的节点对于自身较为有用，但是事实却是在实际生活中，人们受到弱连接节点的帮助比强链接的帮助要多得多。无标度性，指的是网络中很少存在具有大量连接的节点，整个网络与网络的尺度几乎没有关系。这种无标度性反应了用户聚集的特点，也就引出了下一小节社区划分的定义。

2。3 社区划分

由于具有相同属性或者都有一样的兴趣爱好的人他们就更加比较靠向于集中在一块由此组成了社交网络中的地区，而社区的划分对社交网络的模式和对了解它的特性有非常重要的意义。近几年对于它的划分研究都认为是有效性的，但是实际的社交网络中的节点到底在哪个社区还是不确定的，由此变成了它的结果不准确，和现实中的偏差有点大。文章采用了谱分法，凝聚法，分裂法等一些方法对社区进行划分，对它存在的一些问题进行了解决。

3。经典社区发现算法

3。1 谱分法

谱分法的思想来自图像识别与处理方向中图像分割理论，其主要思想是把具有个节点的复杂网络抽象化为一个无向图，并用一个的矩阵来表示这个图，使用来代表节点的度，使用来表示两个节点和之间的连接关系，如果这两个节点之间有关联，则用0表示，如果没有关联，则使用-1来进行表示。此时，设定矩阵的特征向量，如果特征值的时候，则认为在它对应的特征向量所表示的各个节点中，值较为近似的节点属于同一个社区。

3。2 凝聚法

凝聚法认为，可以将整个网络中的所有节点当为一个社区，通过判断社区与社区之间的相似度，将相似度较大的两个进行融合，并一直进行迭代，直到遍历完所有的子节点并获得了设定的社区，算法才会停止。这个过程可以使用图1来表示，如图所示，从上到下，最大社区的形成是由较为小的节点进行凝聚后得到的三级社区，三级社区与相似的其他社区凝聚后得到二级社区，又通过同样的方法得到了最大的社区也就是一级社区。

图1 社区凝聚算法示意图

Newman的快速算法是凝聚方法的代表，以下给出该方法的伪代码：

Step 1: initialization, save all Node as a Community, and initialize eij and ai

      I and j have connection ,other situations

ai=ki&pide;2m

其中，ki表示节点i的度，m表示网络中存在的边的个数。

Step 2: merge: △Q=eji + eij -2aiaj=2(eij-aiaj)

Step 3: go to Step 2, until need to stop

3。3 分裂法

分裂法与凝聚法的思想正好相反，凝聚法是一个融合的过程，而分裂法则是一个拆分的过程。该算法将所有的节点看做为同一个社区的节点，然后对相似度进行判断，将节点与节点间相似度较小的边断开，并重复以上过程，如果节点相似度不高，则分裂结果极有可能是每一个节点属于一个独立的社区，自成一派，该算法实际为凝聚法的“逆运算”的过程，所以在伪代码上不再进行赘述，在这里仅对算法过程以图片的方式进行说明，如图2所示。文献综述 (责任编辑：qin)