社交图中的社区检测

在进行社交网络分析时,一个常见的问题是如何检测社区,如相互了解或者经常互动的一群人。社区其实就是连通性非常密集的图的子图。

在这篇文章中,我将列举一些寻找社区的常用算法。

首先,社区检测可以看作图分区问题。在这种情况下,单个节点将只属于一个社区。换句话说,社区之间不会相互重叠。

删除高边介数的边(High Betweenness Edge Removal)

通常来讲,社区内的成员之间联系紧密,并可以通过许多路径相互连接。另外,不同社区的节点需要跨社区连接才能相互访问,而这些跨社区连接往往具有较高的边介数。

因此,通过删除这些高边介数的边,社交图将被分成不同的社区。

算法:

  1. 对于每个边,计算边介数
  2. 删除最高边介数的边
  3. 直到分离的区域足够

然而,尽管这种方法可以得到不错的结果,但是当节点超过两千个,并且节点之间联系紧密时,这种方法非常慢并且效率不高。

层次聚类

这是社区检测中一种非常普遍的方法。首先定义每对节点之间的距离(或相似度)的度量方式,并进行相应的计算。然后可以使用经典的层次聚类技术。应该选择能使得同一社区的成员之间的距离较小,而不同社区的成员之间的距离较大的距离度量方式。

随机游走

随机游走可以用来计算每对节点之间的距离、以及节点B(node-B)和节点C(node-C)。我们先来关注无向图。一个随机游走者从节点B开始,投掷一个骰子得到一个概率β,它根据链接的权重随机挑选一个邻居进行访问,并且它会有(1-β)的概率回到原始节点v。在无限次的访问之后,如果节点B和节点C属于相同的社区,则节点w上的着落概率分布将很高。直观上讲,随机游走者趋于被困在社区中,因此具有高概率分布的所有节点倾向于与节点B(随机游走者开始的节点)在同一社区内。

请注意,概率β大小的选择很重要。如果它太大(接近1),则收敛后的概率与起始节点无关(即:概率分布仅反映每个节点的中心性,而不反映起始节点的社区)。如果概率β太小(接近零),那么在完全探索社区的连通性之前,随机游走者会过快地停止。

这个问题有一个解析解。

定义M为每对节点之前的转换矩阵。V代表随机行走者的概率分布。

节点B与其他所有节点之间的“距离”是M的特征向量。我们可以重复相同的步骤来找出所有节点对的距离,然后将结果反馈给层次聚类算法。

标签传播

其基本思想是,统计一个节点的相邻节点的标签,并将其这个节点的标签设置为其相邻节点中数量最多的标签。

  1. 开始时为每个节点分配一个唯一的标签。
  2. 在每一轮中,每个节点检查其所有相邻节点的标签都将其自己的标签设置为其相邻节点中数量最多的标签,当出现两种标签数量相同的情况时,将进行随机选择。
  3. 直到标签分配没有更多变化

模块度优化

在一个社区内,2个节点有链接的概率应该比链接刚好在整个图中随机形成的概率要高。

随机链接的概率= deg(node-B) * deg(node-C) / (N * (N-1))

实际链路=邻接矩阵[B, C]

定义com(B)为节点B的社区,com(C) 为节点C的社区

所以创建一个实用功能“模块度”,如下所示...

sum_over_v_w((actual - random) * delta(com(B), com(C)))


算法:

1.开始时每个节点都有自己的社区,所以Q=0因为δ(k,s)会变成0

2.合并两个在Q中获得最大值结果的社区

3.直到结果小于一个阈值


接下来我们来研究可以重叠的社区。即:单个节点可以属于多个社区。

寻找团

简单的社区检测通常从团开始。团是一个子图,每个节点是否连接到任何其他节点。在一个K团(K-Clique)中,它们之间有K个节点和K^2条边。

然而,社区的定义较为宽松,我们并不要求每个人都认识社区内的其他人,但我们需要他们认识“足够多”的(可能是一个确定的比例) 同一个社区的其他人。K核心(K-core)的定义更宽松,它要求K核心的节点至少连接了K个其他成员。还有有一些不算特别流行的宽松的限定,K宗派(K-Clan)要求每个节点在K个步骤(路径长度小于K)内连接每个其他成员。K丛(K-plex)要求节点连接到K丛(K-plex)中N个成员总数中的(N-K)个成员。

该社区被定义为发现的K核心(K-core),或K宗派(K-Clan)或K丛(K-plex)。

K-团(K-Clique)渗滤

社区检测的另一种流行方式是在邻近的K-团(K-Clique)上滚动。如果两个K-Clique共享K-1个节点,则它们相邻。我们要根据期望的社区人群密度选取K这个参数。

该算法如下图所示。

第一步:寻找所有K团(K-Clique)
第二步:组合相邻的团(有K-1=3个共享节点)
第三步:组合相邻的团(有K-1=3个共享节点)

K团(K-Clique)渗透法是识别可能相互重叠的社区的流行方式。

本文的版权归 52Heartz 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

学界 | 谷歌提出基于强化学习的优化配置方法:可让TensorFlow更充分利用CPU和GPU

选自arXiv 作者:Azalia Mirhoseini等 机器之心编译 参与:吴攀、李泽南 众所周知,深度学习是非常计算密集的,合理分配计算资源对于提升运算速...

36510
来自专栏iOSDevLog

Python机器学习:Scikit-Learn教程

一个易于理解的scikit-learn教程,可以帮助您开始使用Python机器学习。

4755
来自专栏CreateAMind

keras中文文档

Keras是一个极简和高度模块化的神经网络库,Keras由纯Python编写而成并基于Theano或Tensorflow。Keras 为支持快速实验而生,如果你...

2345
来自专栏专知

【干货】用PyTorch进行RNN语言建模 - Packed Batching和Tied Weight

【导读】PyTorch是一个日益流行的神经网络框架,自然支持RNN。但是关于RNN,Pytorch的官方教程描述的不怎么详细,这篇文章将介绍使用Pytorch实...

4532
来自专栏SimpleAI

【DL笔记5】一文上手TensorFlow,并搭建神经网络实现手写数字识别

从【DL笔记1】到【DL笔记N】,是我学习深度学习一路上的点点滴滴的记录,是从Coursera网课、各大博客、论文的学习以及自己的实践中总结而来。从基本的概念、...

996
来自专栏机器之心

资源 | 谷歌官方开源tf-seq2seq:一种通用编码器-解码器框架

选自Google 机器之心编译 参与:吴攀 谷歌又开源了!tf-seq2seq 是一个用于 TensorFlow 的通用编码器-解码器框架(encoder-de...

3117
来自专栏SIGAI学习与实践平台

时空建模新文解读:用于高效视频理解的TSM

接着之前的《浅谈动作识别TSN,TRN,ECO》,我们来谈谈最近 MIT和IBM Watson 的新文 Temporal Shift Module(TSM)[1...

1083
来自专栏北京马哥教育

Python数据挖掘:Kmeans聚类数据分析及Anaconda介绍

糖豆贴心提醒,本文阅读时间8分钟 今天我们来讲一个关于Kmeans聚类的数据分析案例,通过这个案例让大家简单了解大数据分析的基本流程,以及使用Python实现...

48813
来自专栏jeremy的技术点滴

tensorflow学习笔记_01

3077
来自专栏AI科技大本营的专栏

AI实践精选:艺术家如何应用RNN(循环神经网络)创作AI化的艺术作品

文章导读:这篇文章不是为了全面深入的介绍循环神经网络(recurrent neural networks),而是为那些没有任何机器学习(machine lear...

3567

扫码关注云+社区