用R语言和python进行社交网络中的社区检测

在这篇文章中,我用R语言和python检测社交网络中的社区

由Kaizong Ye,Coin Ge撰写

Kaggle数据 在110个.egonet文件中(对应于110个匿名Facebook用户),每个文件都包含他的朋友的网络。 

×

模块度定义其实很好理解,我们可以根据一个网络的空模型去进行理解。网络的空模型可以理解为只有节点的而没有连边,这时候一个节点可以和图中的任意其他节点相连,并且节点 i j 相连的概率可以通过计算得到。随机选择一个节点与节点 i 相连的概率为 k j / 2 m ,随机选择一个节点与节点 j 相连的概率为 k j / 2 m ,那么节点 i 和节点 j 相连的概率为 p i p j = k i k j / ( 4 m 2 ) ,边数的期望值 P i j = 2 m p i p j = k i k j / ( 2 m ) 所以模块度其实就是指一个网络在某种社区划分下与随机网络的差异,因为随机网络并不具有社区结构,对应的差异越大说明该社区划分越好。

  Newman提出的模块度具有两方面的意义:

  (1)模块度的提出成为了社区检测评价一种常用指标,它是度量网络社区划分优劣的量化指标;

  (2)模块度的提出极大地促进了各种优化算法应用于社区检测领域的发展。在模块度的基础之上,许多优化算法以模块度为优化的目标方程进行优化,从而使得目标函数达到最大时得到不错的社区划分结果。

  当然,模块度的概念不是绝对合理的,它也有弊端,比如分辨率限制问题等,后期国内学者在模块度的基础上提出了模块度密度的概念,可以很好的解决模块度的弊端,这里就不详细介绍了。

  常用的社区检测方法主要有如下几种:

  (1)基于图分割的方法,如Kernighan-Lin算法,谱平分法等;

  (2)基于层次聚类的方法,如GN算法、Newman快速算法等;

  (3)基于模块度优化的方法,如贪婪算法、模拟退火算法、Memetic算法、PSO算法、进化多目标优化算法等。


让我们关注文件0.egonet,其中包含有关用户0的网络的所有信息。文件的每一行都是该行中直接属于网络一部分的第一个用户的朋友的列表。 


热门课程

R语言数据分析挖掘必知必会

面对扑面而来的数据浪潮,包含Google、Facebook等国际企业,都已采用R语言进行数据分析

探索课程

 在下面,我附加了访问每个egonet文件的Python代码,并构建了Networkx构造函数的节点和边的列表。 构建图后,将计算其邻接矩阵并将其保存在csv文件中。

提供的代码的结果是110个CSV文件,其中包含每个自我网络图的邻接矩阵。

检测社区

首先,让我们绘制一个图,看看它在社区聚类检测之前的样子。在R代码下方,从CSV文件加载数据,构建网络(我们使用0.egonet)并进行绘制。

R 提供了几种强大的社区检测算法。 

模块化本质上是属于给定组的边缘的分数减去如果边缘随机分布的期望分数。所以越高越好。

在这里,您可以在用户0网络上找到结果。

 spinglass.community算法是最好的算法,其模块化为0.4649。事实证明,可以发现小型自我社会网络中的社区 。

在下面,您也可以在R中发现检测到的群集的良好可视化效果。 


可下载资源

关于作者

Kaizong Ye拓端研究室(TRL)的研究员。

本文借鉴了作者最近为《R语言数据分析挖掘必知必会 》课堂做的准备。

​非常感谢您阅读本文,如需帮助请联系我们!

 
QQ在线咨询
售前咨询热线
15121130882
售后咨询热线
0571-63341498