[SIGMOD 2022] DMCS : Density Modularity based Community Search
介绍
目标是找到含有查询点的社区。文章的切入点是高质量的社区一定也是高模块化的，及社区内密度高，且社区同外界的连接稀疏。利用模块化找社区是np难问题，文章提出的模型可以将时间复杂度控制在log里。
动机
常规的k-core, k-truss等方法需要定一个k。如果k太小，就会得到太大的子图，但如果太大，又容易筛掉需要的社区。
在这篇文章之前，已经有利用模块来检测社区的工作了，但他们没用查询点的约束。因此，没法直接用之前的模块化定义，不然很容易得到大量和查询点无关的点。
新的模块化定义
给定一个图\(G=(V,E)\)和一个点集\(C \subseteq V\)。\(G[C]\)被定义为一个诱导子图，保证\(E[C]=\{(u,v) \in E | u,v \in C\}\)
模块的经典的定义方式：
\[CM=(G,C)=\frac{1}{2|E|}(2l_C-\frac{d^2_C}{2|E|}) \]其中\(d_C\)是C的所有度之和，\(l_C\)是所有\(G[C]\)的内部边之和。
最终目标就是找一组不相连的\(\mathcal{C} = \{C_1, C_2, \dots, C_g\}\)，使得\(\sum_{C \in \mathcal{C}}CM(G,C)\)最大。
这个定义下，容易忽视密集但很小的社区，还会找到很多和查询点无关的点。因此，文章重新进行了定义：
\[DM(G,C)=\frac{1}{|C|}(w_C-\frac{d^2_C}{4w_G}) \]其中\(w_C\)是内部边权重和，\(d_C\)是内部点权重（连接的边权重和）和，\(w_G\)是全图的点权重和。
对于无权重的图：
\[DM(G,C)=\frac{1}{2|C|}(2l_C-\frac{d^2_C}{2|E|}) \]其中\(L_c\)是内部边数，\(d_C\)是内部点在全图中的度数和
最终的问题定义：
寻找一个包含Q点集的连通子图G[C]，使得DM（G,C）最大。
模型
整体算法：
也就是每次都找出那个去掉之和分数能最高的点，最终返回所有子图中最好的一个。很明显，整个算法最核心的就是 goodness function M。
为了实现这个函数，模型会首先判断哪些点移除后不会使得查询点脱离子图，然后利用一个更新分数的方程得到去掉某个点后的分数：
\[\frac{l_S-k_{v,S}}{|S|-1}-\frac{(d_S-d_v)^2}{4|E|(|S|-1)} \]其中的\(k_{v,S}\)是这个点对子图的边数，\(d_S\)是子图内的边数和，\(d_v\)是点的边数。
一个点在该子图中的回报：
\[\Lambda^S_v = -4|E|k_{v,S}+2d_Sd_v-d^2_v \]密度比：
\[\Theta^S_v=\frac{d_v}{k_v,S} \]其中\(k_{v,S}\)是v连向子图的边数，\(d_v\)全图中\(d_v\)的度。
最终的实现方式，文中提出了两种：NCA和FPA。
NCA
思路就是利用点的密度回报去找最好的点
FPA
为了提高效率，模型还会事先进行剪枝，策略是从查询点出发做基于层的剪枝：
实验
数据集
结果
