Question

社交网络分析

Answer 1

一个具体的网络可抽象为一个由节点（vertex或node）集合V和边（edge）集合E组成的图 G=(V, E)，节点数记为 n=|V|，边数记为 m=|E|。

PageRank的核心思想是，被大量高质量网页引用的网页也是高质量网页，假如某个网页被大量其他网页，特别是其他高质量网页引用，那么它的排名就高。

假定向量

是N个网页的排名，矩阵

是网页之间链接的数目，如 a _mn 表示第m个网页指向第n个网页的链接数，我们需要在已知A的情况下求得B。

假设 B _i 是第i次迭代的结果，那么

初始假设每个网页的排名都是 1/N，那么通过上式可以求得B ₁ ，再不断迭代求得B ₂ , B ₃ , ...。可以证明最后 B _i 会收敛，无限趋近于B，一般需要10次的迭代就可收敛。

由于很多网页间并没有链接，所以矩阵A会比较稀疏，计算需要进行平滑处理，即将上式换为

其中α为一较小常数，I为单位矩阵。

igraph可以用 g.pagerank() 计算PageRank值。

社区是图中的小集团，同一社区内节点之间的连接很紧密，而社区与社区之间的连接比较稀疏。

而所谓社区发现就是在一个图中发现若干个社区

使得各社区的顶点集合构成V的一个 覆盖 。若任意两个社区的顶点集合的交集为空，则称C为非重叠社区，否则为重叠社区。

边介数 ：网络中经过每条边的最短路径的数目。igraph可以用 g.edge_betweenness() 计算PageRank值

一种启发式的社区发现算法，先将每一个节点作为一个独立的社区，然后分别计算各个节点加入其他社区后的模块度增量，从中选出模块度最高的一个邻居节点，合并为一个社区。

LPA算法不需要预先知识，而且时间复杂度接近于 O(n)，适合处理海量数据下的社区划分。

其中m表示图里的边数；k _v 和 k _w 分别表示节点v和w的度；δ _vw 表示两个节点是否在同一个社区，是则为1不是则为0；A _vw 为网络的邻接矩阵，为1表示两个节点在同一社区，为-1则表示不在同一个社区。

模块度的取值范围为 [-1/2, 1)，越高说明网络的社区划分得越好。

阻断率用来评估单个社区的紧密程度，越小越好。它的计算公式为