20210317 社交网络分析

社交网络分析算法SNA
社交网络物以类聚，人以群分，对不同人、物进行分类，这样我们能分析的东西会有很多。

一.适用场景
1.划分社交圈对于朋友间的互相推荐
2.微博，Twitter等消息的传播
3.京东，淘宝商品和服务的推荐，精准营销。
4.疾病传播由中心点向外扩散切断网络中的关键点可以有效阻止。
5.识别欺诈团伙进行反欺诈预测等。

二、分析指标
1.图、边、节点
2.度 比如A点的出度out degree，入度in degree（进出关系），则A点的度为D（A）=OD（A）+ID（A）

import pandas as pd
from igraph import *
g=Graph([(0,1),(0,3),(2,3),(0,2),(3,4),(2,4),(3,3)])
g

summary(g)
#输出g的节点和边

g.degree#输出节点度

权游数据爽一爽：

三、紧密中心性（closness centrality）——看距离
节点v到达其他节点的难易程度，也就是到其他所有节点距离的平均值的倒数。
这个紧密中心性越大，说明他越容易到达，也就是这些点密集。

四、介数中心性(betweenness centrality)——看连接的点多少
核心思想是两个非邻接成员间的相互作用依赖于网络中的其他成员，特别是两个成员（两个点）间路径上的成员，它们对两非邻接成员间起着某种控制或依赖关系。如果一个成员B位于其他成员的多条路径上（就是说一个点连出去的点多），那么成员A的作用比较大，也具有较大的介数中心性。

实质：网络中包含成员B的所有最短路径条数占所有最短路径条数的百分比。

计算步骤：

1. 计算每对节点的最短路径
2. 对各节点判断v是否再最短路径下
3. 统计经过v的最短路径条数

五、社区发现算法
社区相当于抱团，类似群的概念，同一个社区内的连接紧密，而社区间的连接非常稀疏。社区发现可以理解为在图中发现n个社区，他们连接非常紧密。一个社区就是一个点。
1.GN算法
边介数（betweenness）：网络中经过该边的最短路径占所有最短路径的比例
GN算法是一个经典的社区发现算法，它属于分裂的层次聚类算法，最初，由Michelle Girvan和Mark Newman提出。其基本思想是不断的删除网络中具有相对于所有源节点的最大的边介数的边，然后，再重新计算网络中剩余的边的相对于所有源节点的边介数，重复这个过程，直到网络中，所有边都被删除。

算法步骤：

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

2.Louvain算法
Louvain算法是基于模块度的算法，其优化目标就是最大化整个社区网络结构的模块度。
模块度：
它可以衡量一个社区紧密程度的度量，可以作为优化函数去优化社区的分类；它的物理含义是社区内节点的连边数与随机情况下节点的连边数之差。

算法思想：
（1）不断遍历网络中的节点，尝试把单个节点加入能使模块度提升得到最大的社区，直到所有节点不再改变
（2）将第一阶段形成的一个个小的社区并为一个节点，重新构造网络。这时边的权重为两个节点内所有原始节点的边权重之和。
（3）重复以上两步
4.LPA与SLPA
LPA算法思想：
（1）初始化每个节点，并赋予唯一标签
（2）根据邻居节点最常见的标签更新每个节点的标签
（3）最终收敛后标签一致的节点属于同一个社区

SLPA算法思想：
1.给每个节点设置一个list存储历史标签
2.每个speaker节点带概率选择自己标签列表中标签中标签传播给listener节点。（两个节点互为邻居节点）
3.节点将最热门的标签更新到标签列表中
4.使用阀值去除低频标签，产出标签一致的节点为社区。