几何设置下的社区检测与信息渗透
提出一种称为几何块模型(Geometric Block Model)的新随机图模型来捕捉许多社区检测问题的内在几何特征,并证明在这个模型中使用简单的三角计数算法是近乎最优的。
Sep, 2017
本研究考虑在具有二元社区标签和 R^d 值位置标签的欧几里得随机几何图上进行社区检测问题,其中边缘概率依赖于社区和位置标签。我们针对稀疏和对数度规则建立了相变现象,并给出了阈值的约束。此外,我们还展示了在我们的模型与没有社区标签的空模型之间进行测试的可区分性问题的阈值没有相变现象,并且特别地与 SBM 不同。
Jun, 2017
论文提出了信息论阈值的上下界,并进一步证明了当组数较大且特定参数取值时,物理条件下的凝聚阈值是具有严格界限的,若邻居间与组间边缘概率不同,则分配问题可以解决,否则无算法可优于随机。
Jan, 2016
该论文提出了一种强大、可扩展、综合的图中社区检测和比较方法,首先将图嵌入到一个适当的欧几里得空间中以获得低维表示,然后将顶点聚类成社区,并应用非参数图推理技术识别这些社区之间的结构相似性,然后可以递归地应用这两个步骤到社区上,以检测更细粒度的结构。最后,在模拟和真实数据上证明了该算法的有效性。
Mar, 2015
研究一种用于不规则网络与潜在属性的随机图模型,提出了一种计算有效性的光谱算法并展示了其可在部分可观察网络下进行渐近正确的推测,作为其分析的副产品,该模型提供了一种构建具有预先指定的特征谱的随机图模型的通用程序。
Jun, 2014
本文研究了几何块模型中的主动学习问题,提出了两个结合不同标签查询策略的主动学习算法。我们的主要贡献在于展示了在一些场景下,取极少量的节点标签进行样本探索就能精确恢复社区结构,并在真实和合成数据集上验证了我们算法的卓越性能。
Nov, 2019
通过将网络看作几何对象并将网络中的社群视为几何分解,我们应用曲率和离散 Ricci 流的几何方法来分解网络社群。在具有基本真实社群结构的网络上测试了我们的方法,并实验验证了此几何方法的有效性。
Jul, 2019
考虑在稀疏随机网络中检测紧密社区的问题,将其形式化为在随机图中测试是否存在密集子图。在本文中,我们研究渐近稀疏情况下的信息理论下限,并比较了各种测试方法的性能,发现我们的检测边界是尖锐的。
Aug, 2013