社交网络分析

图与网络

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

衡量指标

  • 度（degree）

    一个节点所对应的边数；

  • 紧密中心性（closeness centrality）

    衡量某个节点到达其他节点的难易程度，也就是该结点到其他所有结点距离的平均值的导数。
    C_v = \frac{|V|-1}{\sum_{i\neq v}d_{vi}}
    igraph可以用 g.closeness() 计算某个节点的紧密中心性。

  • 介数中心性（betweenness centrality）

    衡量某个节点在图中结构的重要性。计算每对结点 (i, j) 之间的最短路径，各个节点判断是否在该路径上，最后将刚刚的判断进行累加得到从i到j的最短路径经过该结点的数量
    B_v=\sum_{i\neq j,i\neq v,j\neq v}\frac{g_{ivj}}{g_{ij}}
    igraph可以用 g.betweenness() 计算某个节点的介数中心性（又称点介数）。

PageRank

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

假定向量
B=(b_1, b_2,...,b_N)^T
是N个网页的排名，矩阵
A=\left[\begin{matrix}a_{11}&\cdots&a_{1n}&\cdots&a_{1M}\\\vdots&\vdots&\vdots&\vdots&\vdots\\a_{m1}&\cdots&a_{mn}&\cdots&a_{mM}\\\vdots&\vdots&\vdots&\vdots&\vdots\\a_{M1}&\cdots&a_{Mn}&\cdots&a_{MM}\\\end{matrix}\right]
是网页之间链接的数目，如 amn 表示第m个网页指向第n个网页的链接数，我们需要在已知A的情况下求得B。

假设 Bi 是第i次迭代的结果，那么
B_i=A\cdot B_{i-1}
初始假设每个网页的排名都是 1/N，那么通过上式可以求得B1，再不断迭代求得B2, B3, ...。可以证明最后 Bi 会收敛，无限趋近于B，一般需要10次的迭代就可收敛。

由于很多网页间并没有链接，所以矩阵A会比较稀疏，计算需要进行平滑处理，即将上式换为
B_i=[\frac{\alpha}{N}\cdot I+(1-\alpha)A]\cdot B_{i-1}
其中α为一较小常数，I为单位矩阵。

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

社区发现算法

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

而所谓社区发现就是在一个图中发现若干个社区
C=\{C_1,C_2,...,C_{nc}\}
使得各社区的顶点集合构成V的一个覆盖。若任意两个社区的顶点集合的交集为空，则称C为非重叠社区，否则为重叠社区。

GN算法

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

  1. 计算网络中所有边的边介数；
  2. 找到介数最高的边，将其移除；
  3. 重复，直到每个节点就是一个社区为止。

Louvain算法

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

LPA算法

  1. 初始化每个节点，给予唯一标签；
  2. 根据邻居节点最常见的标签，更新每个节点的标签；
  3. 最终收敛后标签一致的节点属于一个社区。

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

评价指标：模块度

Q=\frac{1}{2m}\sum_{vw}(A_{vw}-\frac{k_vK_w}{2m})\delta _{vw}

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

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

评价指标：阻断率（conductance）

阻断率用来评估单个社区的紧密程度，越小越好。它的计算公式为
\Phi (S)=\frac{连接到社区外的边数}{社区内节点连接的边数}

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容