专栏首页社交图中的社区检测

社交图中的社区检测

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

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

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

删除高边介数的边(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 条评论
登录 后参与评论

相关文章

  • redis主从之全量复制及增量复制

    部署主从节点时需要考虑网络延迟、宽带使用率、防灾级别等因素,如要求低延迟时,建议同机房部署并关闭repl-disable-tcp-nodelay,如考虑容灾性,...

    gaobinzhan
  • 为什么有红黑树?什么是红黑树?看完这篇你就明白了

    想必大家对二叉树搜索树都不陌生,首先看一下二叉搜索树的定义: 二叉搜索树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树:若...

    乔戈里
  • 2-3树与红黑树

    张风捷特烈
  • 数据结构与算法(七)-树

    前言:回顾一下前面学习的内容,大概说了下数据结构中的线性结构,从物理存储方面来说又分为顺序存储和链式存储结构,各自有自己的优缺点,顺序存储结构读快写慢,链式存储...

  • 数据结构:树与二叉树

    一颗高度为h,并含有2^h-1个节点的二叉树称为满二叉树,即树中的每一层都含有最多的节点。

    HLee
  • 多叉树 & B树 & B+树 & B*树

    二叉树虽然操作效率比较高,但是如果数据一多,就会有好多好多的节点,需要进行好多次的I/O操作,构建出来的二叉树就会很高很高,也会降低操作速度。

    贪挽懒月
  • 像管理 Pod 一样管理 Node | TKE 节点池全面上线

    晏子怡,腾讯云产品经理,目前负责TKE集群、网络及调度模块。 从 K8s 的声明式设计理念谈起 Pod 模板 K8s 最优雅精妙的一个设计理念在于声明式  A...

    腾讯云原生
  • DOM(文档对象模型)基础加强

    黑泽君
  • [译]寻路优化

    寻路对很多游戏来讲都是不可或缺的元素,在一般的游戏中,使用一些基本的寻路算法(譬如 BFS, Dijkstra 或者 A* 等等)就可以很好的解决寻路问题,但是...

    用户2615200
  • 一万字详解 Redis Cluster Gossip 协议

    大家好,我是历小冰,今天来讲一下 Reids Cluster 的 Gossip 协议和集群操作,文章的思维导图如下所示。

    黄泽杰

扫码关注云+社区

领取腾讯云代金券