共计 4363 个字符，预计需要花费 11 分钟才能阅读完成。
★ halo，大家好~ 很开心又和大家见面了~
★ 在第一篇 楠姐技术漫画：图计算的那些事 公布之后，楠姐收到了很多倡议、激励和反对，非常感谢大家的喜爱，所以楠姐尽本人所能快马加鞭开始第二篇的创作，虽迟但到~
★ 本篇仍然是风控算法分享，其实也仍然算是图算法系列。社区发现 作为最根底的图算法之一，也是楠姐在 2020 年入职后，第一个跟着大腿有样学样，学习、上手和利用的图算法，因而在第一期之后，楠姐就立即决定把它独自拿进去写一期，进一步来说，无论图计算明天和日后倒退如何，咱们都不该遗记最后的前人基石，同时也心愿本人和每个小伙伴，无论路已走多远，都能不忘初心，不忘滴水之恩。
— ★ PART 1 ★—
其实社区发现
也并不是什么难懂的名词
置信所有看过第一期漫话的宝子们
应该还没遗记图的概念
那社区又是什么呢？
社区其实反映的是
网络中的个体行为的局部性特色
以及其相互之间的关联关系
换艰深一些的说法 …
用户之间的点赞、私信、关注等动作造成了边
那些关联尤为严密的用户就造成一个社区
而分属不同社区的用户之间
关联则十分稠密或基本不存在关联
近几年风行的饭圈文化就是一个很好的例子
明确了什么是社区
其实社区发现所要做的事也就很易懂了
正是要发现这些潜在的、有特定关系的节点汇合
以及每个社区中都有哪些节点
这样做的目标和成果也有很多
咱们京东的注册 / 营销 / 领取 / 物流 / 信贷等各大零碎
黑产团伙在很多细节上的关联总是十分严密的
与失常用户显得心心相印
再比方 生物学畛域 内
基因调控网络分析、主控基因辨认
还有 疾病传播学 中
传染要害社区辨认以及易感人群发现等
还有上一期评论区中提到的
👍基于社交网络的海王识别器👍
都能够用到社区划分
一是要确认以后应用场景内
的确存在着显著汇集法则
节点间存在肯定的逻辑能够造成社区构造
而不是无规律扩散
二是不要把 社区拓扑构造 与欧式空间结构 混同
尽管在欧式空间中
向量夹角小的点向量彼此间隔近
向量夹角大的点向量彼此距离远
但即便间隔相近的点向量
也不肯定就存在业务或者逻辑上的拓扑关联
牢记以上两点
才不会让你的社区划分被限度应用形式或生效
— ★ PART 2 ★—
那说到这呢
可能会有算法的小伙伴发现
社区发现如同和 聚类 十分类似
它们都属于无监督算法
聚类要做的是
“簇内间隔最小化，簇间间隔最大化”
社区发现要做的是
“社区外部节点关联严密，社区之间节点关联稠密”
的确二者之间存在着很多相似性
但仍然也是有区别的
机器学习中常见的聚类算法
实质上是一种更通用的办法
实用于多种常见的数据类型
而社区发现实质上则是图构造上的聚类
而对于社区自身
其实也有两种不同的类型
非重叠社区 和重叠社区
前者说的是图中的每个节点只属于一个社区
而后者则容许同一个节点能够分属于多个社区
— ★ PART 3 ★—
社区发现算法类别繁多
不同算法划分的社区天然也是不同的
不论是人还是模型去执行一些学习工作
都有对于学习是否到位的评判办法
那咱们如何评估一个社区发现算法的好坏呢？
此时就不得不先提一个重要的基本概念
模块度（modularity）
这是一种罕用的社区划分评估指标
为了怕大家睡着从而遗记一键三连
楠姐贴一个简化版的模块度计算公式
艰深来说
模块度的物理含意是
社区外部的边数与随机状况下的边数的差距
如果越大，阐明社区外部密集度高于随机状况
这里的随机状况指的是图中节点和边的数量不变
把节点之间连贯关系随机打乱
一个图如果看起来不像随机产生的
那可能就是存在社区的
如果一个社区发现算法
尽可能多的将关联严密的点划分在同一社区中
尽量避免所得社区之间还存在过多的边
这样就能失去较高的模块度
也会被认为是较好的一种划分形式
— ★ PART 4 ★—
自从 2002 年“社区”概念被提出后
社区发现算法就始终在疾速倒退
★
首先是比拟间接基于模块度的社区发现
这类算法间接把模块度作为优化指标
有着良好的解释性
Louvain 算法是其中的典型代表
它的二阶段思路十分清晰
第一个阶段称为模块度优化阶段
先把图中的每个节点都视作一个独立的社区
对每个节点
顺次尝试将其调配到它每个街坊节点的社区中
计算调配前后模块度的变动
并将该节点调配至 模块度增益最大的一个街坊社区 中
如果没有任何一个街坊社区能晋升模块度
则该节点的社区放弃不变
对所有节点进行一轮以上计算后
一些节点便曾经被划分在了同一个社区
接着开始 第二阶段——社区聚合阶段
把同一个社区的节点视作一个新的节点
社区外部的边视作权重和累加的自环边
社区之间的边视作新节点之间的边
依据这个新的图构造再反复第一阶段
两个阶段周而复始
直到模块度不再更优为止
Louvain 算法因为其较低的工夫复杂度
非常实用于大规模网络的社区检测
也成为利用最宽泛的算法之一
★★
第二种经典办法
是基于节点表白的社区发现
该类办法将图节点表白和映射到多维向量空间
并联合传统聚类算法将它们汇集成社区
这种办法不可避免的要进行矩阵计算
或者应用额定的节点表征算法
计算开销很大
但它能间接应用传统聚类的成绩
因而灵活性十分好
比方，典型的一个计划就是
应用 node2vec 进行图节点编码
再应用聚类将类似的节点向量进行聚合
node2vec 其实是借鉴了 NLP 畛域中的 word2vec
简略来讲，它先会在图构造中进行随机游走
通过随机游走
采样出多条节点序列
相似于文本序列
而咱们要表征的节点
就相似于文本中的字词
再应用 NLP 畛域中罕用的 SkipGram 算法
将节点示意成量化的向量表白
以文本了解为例
如果咱们想让人工智 (zhi) 能(zhang)了解上面这句话：
那是不是能够把这句话中“技术漫话”遮挡住
让模型进行填空：
“楠姐发了____，很快就要火了”
如果模型能正确填上
就能够肯定水平代表模型学会了这句话中每个字词的含意
或者反过来也能够
把除了“技术漫话”之外其余的字全副遮挡住
让模型进行补写：
“技术漫话，_____”
要是模型补充的很不错
也代表模型学会了这句话和外面的字词
下面做的这些事
就是 NLP 畛域内的 word2vec 算法
第一种填空的形式叫 CBOW 模型
第二种补充的形式就是 SkipGram 模型
在图的节点表征中
用于图节点序列也是一样的情理
那么说回社区发现
有了节点的数值示意
就能够借助任意一个传统的聚类算法
达成最终的节点社区划分的指标
然而分两步的办法究竟费时费力
也有一些优良的算法
能够将节点编码和聚类合二为一
一起进行优化
单纯是因为懒
楠姐就不再赘述
★★★
明天要说的第三种经典的社区发现思路
是基于信息论的社区发现
外面的典型代表是楠姐的“老熟人”
——赫赫有名的 infomap 算法
它也采纳了在图中随机游走的形式进行节点序列的采样
但它社区发现的指标
是最小化节点的均匀编码长度
所谓编码
其实就是用无限个标记的组合来示意原始信息
大家最熟知的就是二进制编码
即只用 0 和 1 两个数字
编码与原始对象通常是一一对应的
比方“楠”可能对应着“11”，“姐”对应着“1001”，那么“楠姐”就对应着(11,1001)
如果须要咱们疾速地记录下所看到的文字
记录的形式须要将每个字对应一个二进制编码
那为了记得更快
咱们显然是心愿经常出现的字用短的编码
比方“楠姐”这个词如果呈现的很频繁
如果用“11000010001”来示意“楠姐”
要是每次听到“楠姐”都须要写这么长的数字
该是如许一件糟心的事件
如果用短的编码，比方“10”来示意“楠姐”
那相对而言记录速度就能有显著晋升
也显得“楠姐”没有那么厌恶了
那么该如何找到一种最优的节点编码
使得均匀编码最短呢
这个在信息论中曾经给出了谨严的公式计算
也就是存在着一个“信息熵”的极限
不论用什么样的编码方式
其均匀编码都不可能低于信息熵
这个信息熵也正是无损压缩的能力极限
这也正是信息论中的最小熵原理
回到 Infomap 算法自身
它额定借助了一个分组编码的思路
把最小信息熵和社区发现联合了起来
有没有一种可能
大家抉择的记忆形式是酱紫的：
后面五个是人类流动
其次两个是搬砖我的项目
再往后三个是好吃的
前面三个是游戏
最初大家再别离记住四种分组里具体都有什么
是的，没错
这样的记忆形式就是一种更高效的形式
也是 infomap 所采纳的编码方式——档次编码
它把每个节点都尝试进行分类
节点的编码均为在类内的编码
额定还有一套独立的类别编码
因为有了分类的思维
不同类的节点能够应用雷同的编码
比方“楠姐”和“东坡肘子”都能够用应用“01”
这样就无形中压缩了整体的编码长度
再加上后面提到的最小熵指标
咱们就能够搜查一种最优的分层编码
来使得最短均匀编码长度越小越好
最初每个节点编码时的分类
就是最终所属的社区
Infomap 最大的长处也在于此
真是一种弱小且丑陋的算法
还有一些其余类型的社区发现
比方基于 标签流传 的办法
基于 图宰割 的办法
狭义社区发现等等
感兴趣的宝子们能够卷起来了！
— ★ PART 5 ★—
社区发现算法算是图计算中的一条重要分支
也是咱们风控技术中离不开的工具
它在纷繁复杂的网络结构中
总能提供给咱们一种宏观视角
揭示着事物的构造和实质
只有你的想象力足够丰盛
就相对有社区发现算法所能施展的空间
事在人为，行则终至！
加油吧，算法攻城狮们~
—- 写在最初 —-
★ 本篇文章图片构思、创意、整体构造、前期批改，全副版权归楠姐所有，素材生成均源自于 Midjourney 以及楠姐原创提醒词生成。楠姐出图不易，并非完满，请勿未经容许用于其余场合及目标。
★ 本篇文章图片创意均只为了阐明及示意，且带有肯定夸大和风趣元素，切勿对号入座哦~ 如有雷同，纯属巧合~ 无心触犯~
★ 本篇文章文字均依据以下参考文献汇总撰写：
[1]. 马耀，汤继良. 图深度学习[M]. 电子工业出版社.
[2]. 张长水，唐杰，邱锡鹏[M]. 图神经网络导论[M]. 人民邮电出版社.
[3]. CSDN. 写综述想到的[EB/OL]. https://blog.csdn.net/loptimistic/article/details/8173555
[4]. CSDN. 社区发现 (Community Detection) 算法[EB/OL]. https://blog.csdn.net/huangxia73/article/details/11801661
[5]. 博客园. 社区发现算法总结[EB/OL]. https://www.cnblogs.com/nolonely/p/6262508.html
[6]. 知乎. 简析社区发现和聚类[EB/OL]. https://zhuanlan.zhihu.com/p/428821516
[7]. 知乎. 万物皆网络，万字长文详解社区发现算法 Louvain[EB/OL]. https://zhuanlan.zhihu.com/p/556291759
[8]. CSDN. infomap 最全面易懂的解释 – 最小熵原理：“层层递进”之社区发现与聚类[EB/OL]. https://blog.csdn.net/jinking01/article/details/103511553
作者：京东科技 丁楠
起源：京东云开发者社区 转载请注明起源