社团发现，又名社区发现、社团检测等，英文名community detection. 是一种传统的聚类算法。
从Girvan和Newman 于2002年提出的分裂算法，社团发现应该有20年的历史了。相对于bert等神经网络算法，社团发现已经研究20几年了，但是相对于70多年的某数值模拟学科，它又是比价新的领域。
社团在历史上有很多方面的优化：
- 社团度量 + 最优解
- 切、聚
- 样本表征（降维、embedding）
- 减少计算复杂度（因为样本很大）
- 重叠社团
目前的主要方式是三步：数据 -> 邻接矩阵 -> 聚类。相应的有许多方法，下面简单介绍几个的。
1. 表征
1.1 SBM
https://zhuanlan.z**u.com/p/485607150
https://arxiv.org/pdf/2101.01669.pdf
SBM是一个传统的图生成模型，认为每个节点从属于不同的社区，每个社区之间的节点会以不同的概率相连接，由此生成一张图，这就是它基本的思想。他可以用于社区检测，图聚类，主题建模等任务。
1.2 LDA
LDA（线性判别分析）本质是有监督的正交变换，通过对数据集的旋转+投影（降维）让不同的类别聚在一起。
1.3 非负矩阵分解
NMF（Non-Negative Matrix Factorization）也是降维表征。
3.2 Spectral Clustering
4. 标签传播
4.1 Label Propagation Algorithm（LPA）
可以做无监督、也可以做半监督。
4.2 SLPA
https://blog.***.net/itplus/article/details/9286905
与LPA相比，记录每一个节点在刷新迭代过程中的历史标签序列（例如迭代 T 次，则每个节点将保存一个长度为 T 的序列），当迭代停止后，对每一个节点历史标签序列中各（互异）标签出现的频率做统计，按照某一给定的阀值过滤掉那些出现频率小的标签，剩下的即为该节点的标签（通常有多个）。
5. 模块度启发
5.1 Louvain
5.2 Leiden
由Louvain改进过来的，多了refine过程，保证社团内部是连通的。本质上由于模块度寻优算法是个np问题，需要通过搜索来确定最优解，目前通过贪婪方式获取每一步更优，直到最优，有可能不是最优解。所以搜索方式是优化的一个点。Leiden在这个方面更优。
6. 隶属度吸引度启发
6.1 近邻传播(AP)聚类算法
7. infomap
对图里的节点随机采样出一个序列，按顺序依次尝试将每个节点赋给邻居节点所在的社区，取平均比特下降最大时的社区赋给该节点，如果没有下降，该节点的社区不变。（启发式）
8. 谱聚类（spectral clustering）
https://www.c***blogs.com/sparkwen/p/3155850.html
谱聚类能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。为切算法。
问题
- 算法很多，但是可能我用的不好，实际用的效果都不咋好，特别是一些特定领域。
- 算法没有继承性，有些算法提出后就放到那儿了，没有继续优化出非常优的算法（也可能都是没发现）。这么看模块度启发那块儿算是比较好的了，一直在发展。
