在社区数量不确定的非参数加权随机块模型中的一致社区检测方法

《Journal of Statistical Planning and Inference》:Consistent community detection approach in the nonparametric weighted stochastic blockmodel with unspecified number of communities

【字体: 大 中 小 】 时间:2026年02月11日 来源:Journal of Statistical Planning and Inference 1.1

编辑推荐:

  费烨|肖景松|马伟东|苗玉来|杨颖 中国北京100070,首都经济贸易大学统计与数据科学学院 摘要 随机块模型是一种广泛用于表示图的模型。已有许多方法被应用于该模型,以检测图中的潜在社区结构,这些方法通常使用两种一致性标准(强一致性和弱一致性)来评估其性能。大多数方

  费烨|肖景松|马伟东|苗玉来|杨颖
中国北京100070,首都经济贸易大学统计与数据科学学院

摘要
随机块模型是一种广泛用于表示图的模型。已有许多方法被应用于该模型,以检测图中的潜在社区结构,这些方法通常使用两种一致性标准(强一致性和弱一致性)来评估其性能。大多数方法已被研究,并证明在随机块模型框架下是一致的。然而,作为该模型重要扩展的加权随机块模型的一致性却鲜有关注。此外,当社区数量未知时,能够检测社区的方法也很少。本文提出了一种非参数方法,用于在社区数量未知的配对型非参数加权随机块模型下有效检测社区,并证明了该方法的一致性。我们还引入了一个新概念——“关系一致性”,作为评估社区检测算法性能的更实用标准。由于在较大样本规模下解决该方法中的优化问题变得困难,我们提出了一种高效的近似算法。仿真结果表明,我们的社区检测方法既高效又稳健,尤其是在不平衡网络中。我们还通过三个真实世界网络展示了该方法的有效性。

引言
社区检测是统计学、网络分析和社会科学等多个领域中的重要问题。其目标是将图中的顶点划分为若干簇,使得同一簇内的顶点之间连接更为紧密。传统的社区检测方法,如基于割集的方法(Hagen和Kahng,1992;Shi和Malik,1997;Stoer和Wagner,1997)以及模块度方法(Newman和Girvan,2004),都是通过优化某种直观的目标函数来实现的。由于这些方法并未假设真实社区结构的存在,因此没有统一的性能衡量标准。更多细节可参见Fortunato(2010)的研究。

Holland等人(1983)提出的随机块模型是一种常用的图模型,在过去几十年里受到了广泛关注。在该模型框架下,图中存在潜在的社区结构,同一社区内的顶点具有相似的行为特征。在随机块模型框架下的核心任务就是确定这一社区结构。该模型可应用于社区检测问题,而社区检测所寻求的社区结构被称为配对结构。例如,可参考Gopalan等人(2012)、Li等人(2016)以及Lu和Szymanski(2019)的研究。需要注意的是,随机块模型也可以用来模拟非配对结构,比如那些外部连接更为密集的社区。

在随机块模型框架下,已有许多方法被提出用于检测潜在的社区结构。Newman(2006)提出了一种基于特征向量的算法,用于最大化模块度;Bickel和Chen(2009)研究了最大化Newman-Girvan模块度和似然模块度的性质。Amini等人(2013)提出了一种计算速度较快且能处理大型稀疏图的伪似然方法。基于谱的方法,如谱聚类(Rohe等人,2011)和谱嵌入(Sussman等人,2012),也被应用于这一问题。此外,大量文献还聚焦于对该模型的贝叶斯推断,例如Peixoto(2019)、Suwan等人(2016)以及Zhang和Zhou(2020)的研究。

在随机块模型框架下,有两种一致性标准用于评估方法的性能。Bickel和Chen(2009)提出的强一致性意味着,随着节点数量趋于无穷大,所有节点被正确分类的概率会趋近于1。Zhao等人(2012)定义的弱一致性则要求,随着节点数量趋于无穷大,被错误分类的节点比例在概率意义上趋近于0。由于标签的排列不会改变节点之间的关系,因此估计得到的标签向量中被错误分类的节点数被视为该标签向量经过排列后可能得到的最小值。大多数方法已被证明要么具有弱一致性,要么具有强一致性。Bickel和Chen(2009)表明,似然模块度最大化方法是强一致的。Amini等人(2013)证明了伪似然方法具有弱一致性。此外,Zhao等人(2012)研究了社区检测的一般准则,并给出了基于这些准则的方法具有强一致性或弱一致性的条件。另一方面,Rohe等人(2011)证明了谱聚类的弱一致性,而Su等人(2020)则表明谱聚类是强一致的。此外,Sussman等人(2012)和Lyzinski等人(2014)也证明了谱嵌入同样具有弱一致性和强一致性。

随机块模型有多种扩展形式。Karrer和Newman(2011)提出了度校正随机块模型,该模型通过引入额外参数来控制顶点的期望度数。Heimlicher等人(2012)提出了带标签的随机块模型,允许边从有限集合中获取标签。此外,Aicher等人(2013)将随机块模型推广到边带权重的情况,这些权重来自指数族分布。Jog和Loh(2015)提出了加权随机块模型,其中边的权重可以遵循任意分布。Ahn等人(2018)进一步对加权随机块模型进行了扩展。关于随机块模型扩展的更多细节,可参见Abbe(2018)以及Lee和Wilkinson(2019)的研究。

加权随机块模型是随机块模型的重要扩展。标准随机块模型仅适用于二值网络;但实际上,许多二值网络都是通过对加权网络进行阈值处理得到的(Aicher等人,2013;Thomas和Blitzstein,2011),这一过程会导致信息损失。加权随机块模型可直接应用于加权网络,从而避免了这一问题。目前关于加权随机块模型的大部分研究都假设采用参数化模型并运用参数化方法,例如Aicher等人(2015)、Ludkin(2020)、Mariadassou等人(2010)以及Ng和Murphy(2021)的研究。对于非参数化方法,可参见Peixoto(2018)的研究,该研究采用了基于积分似然的贝叶斯方法。

尽管已有许多针对加权随机块模型中的社区检测方法被提出,但这些方法的理论结果几乎尚未建立。Xu等人(2020)为加权随机块模型下的社区检测建立了最优速率,并提供了一种能够达到这些速率的估计算法,但他们的结果仅适用于均匀加权随机块模型。Ng和Murphy(2021)提出了具有伽马权重的加权随机块模型,并开发了一种一致性的社区检测方法。他们假设网络是密集的,即节点之间的连接概率不为零。而对于在非均匀和非参数假设下的稀疏加权网络,目前还没有任何方法能够获得理论上的保证。此外,即使是在原始随机块模型下,当社区数量未知时,除非先估计出社区数量,否则大多数方法都无法发挥作用。这一问题促使人们提出了多种估计社区数量的方法,例如:基于似然的方法(Daudin等人,2008;Hu等人,2020;Latouche等人,2012;Peixoto,2013;Salda?a等人,2017;Wang和Bickel,2017);贝叶斯方法(Passino和Heard,2020;Peixoto,2019;Yan,2016);交叉验证方法(Chen和Lei,2018;Li等人,2020);基于归一化邻接矩阵的方法(Hu等人,2021;Lei,2016);以及谱方法(Le和Levina,2019)。正如Le和Levina(2019)所指出的,这些方法通常计算成本较高。此外,如果社区数量的估计有误,那么就不可能得到一致的社区结构估计值。

本文提出了一种非参数方法,用于分析社区数量未指定的非参数加权随机块模型。具体而言,我们将社区检测作为主要目标,并假设存在配对型社区结构。我们证明了,无论社区数量是否已知,我们的方法在配对型非参数加权随机块模型下都具有弱一致性。此外,由于弱一致性的定义需要计算被错误分类的节点数——而这涉及标签的排列,当社区数量较大时可能会比较复杂——因此我们采用了Rand(1971)提出的Rand指数作为更便捷的性能衡量标准。我们基于Rand指数定义了关系距离,用以比较代表不同社区结构的两个向量,并以此定义关系一致性。我们证明了关系一致性蕴含弱一致性。此外,我们还表明,在网络较为密集的情况下,关系一致性能够带来一致的链接预测结果。

本文的其余结构如下:第2节阐述模型假设;第3节基于Rand指数定义关系距离,并用其定义关系一致性;第4节提出基于M估计的方法,并阐述本文的主要结论。首先,我们证明关系一致性蕴含弱一致性。然后,我们表明,无论社区数量是否已知,我们的M估计量都具有关系一致性。此外,当社区数量已知时,对于密集网络,关系一致性能够带来一致的链接预测结果。第5节鉴于精确计算在较大样本规模下难以实现,因此提出了一种高效的近似算法。第6节展示了仿真结果及实际数据应用案例。第7节对全文进行总结。

章节片段

配对型非参数加权随机块模型
在本节中,我们介绍配对型非参数加权随机块模型。考虑一个具有顶点集1,…,n的无向图G。假设块的数量为一个固定的整数k?>1。我们分别探讨k?已知和未知两种情况。令z?∈[k?]n表示顶点的(固定但未知的)社区标签,其中对于任意正整数k,[k]={1,…,k}。观测到的相似性矩阵W为wijn×n大小的对称随机矩阵,其对角线元素为0,对于i≠j的情况,

关系一致性
在随机块模型中,评估一种方法时通常会考虑强一致性和弱一致性,这两种一致性均基于被错误分类的节点数量。正如Bickel和Chen(2009)所阐述的,如果当n趋于无穷大时,Pmin1n∑i=1nIτ(z?i)≠zi:τ∈L[n]=0的趋势趋于1,则标签向量z∈[n]n的估计量z?被认为是强一致的。而正如Zhao等人(2012)所阐述的,如果当n趋于无穷大时,min1n∑i=1nIτ(z?i)≠zi:τ∈L[n]的趋势趋于P0,则z?被认为是弱一致的,此处L[n]表示[n]上所有排列的集合。节点数的

主要结论
在本节开头,我们先概述我们的方法。其思路与传统の社区检测算法——最小割算法类似。图聚类中的最小割算法旨在最小化簇内权重之和,即z?mincut=argminzSW?W⊙Mz,其中⊙表示逐元素乘法,对于任意对称矩阵A=aijn×n∈Rn×n,有SA=∑i≠jaij/n2?n=2∑i
近似算法
在离散标签空间上最大化h(z)是一个组合优化问题。当k?已知时,搜索空间为[k?]n;而当k?未知时,我们则在[k?≤rn?≤n]范围内进行优化。因此,搜索空间的基数会随n呈指数级增长,这使得对大型图进行h(z)的完全最大化在计算上不可行。这就需要采用近似优化方法。贪心算法通过迭代地做出局部最优决策,自然是这类问题的理想选择。

数值研究及示例
在本节中,我们展示了仿真结果及实际数据分析。首先,我们将我们的方法应用于模拟网络。为了评估这些方法的性能(当k?已知时称为me,即m估计量;当k?未知时称为meun),我们将其与ng等人(2001)提出的标准化谱聚类方法(称为nsc)、zhang和zhou(2020)提出的平均场变分推断方法(称为mf),以及基于模块度的谱聚类方法进行了比较。

讨论
我们提出了一种针对社区数量未知的配对型非参数加权随机块模型的非参数社区检测方法,并证明了其一致性。我们的方法灵感来源于最初无需模型假设的经典图聚类算法,我们发现它在这一统计模型中表现良好。尽管我们必须使用近似算法,但它仍然能够优于其他竞争性方法。这为未来研究更精确的方法提供了方向。 n2?n。正如von luxburg(2007)所指出的,这类算法往往会使单个顶点与图的其他部分分离。 近似算法 在离散标签空间上最大化h(z)是一个组合优化问题。当k?已知时,搜索空间为[k?]n;而当k?未知时,我们则在[k?≤rn?≤n]范围内进行优化。因此,搜索空间的基数会随n呈指数级增长,这使得对大型图进行h(z)的完全最大化在计算上不可行。这就需要采用近似优化方法。贪心算法通过迭代地做出局部最优决策,自然是这类问题的理想选择。 数值研究及示例 在本节中,我们展示了仿真结果及实际数据分析。首先,我们将我们的方法应用于模拟网络。为了评估这些方法的性能(当k?已知时称为me,即m估计量;当k?未知时称为meun),我们将其与ng等人(2001)提出的标准化谱聚类方法(称为nsc)、zhang和zhou(2020)提出的平均场变分推断方法(称为mf),以及基于模块度的谱聚类方法进行了比较。 讨论>

近似算法
在离散标签空间上最大化h(z)是一个组合优化问题。当k?已知时,搜索空间为[k?]n;而当k?未知时,我们则在[k?≤rn?≤n]范围内进行优化。因此,搜索空间的基数会随n呈指数级增长,这使得对大型图进行h(z)的完全最大化在计算上不可行。这就需要采用近似优化方法。贪心算法通过迭代地做出局部最优决策,自然是这类问题的理想选择。

数值研究及示例
在本节中,我们展示了仿真结果及实际数据分析。首先,我们将我们的方法应用于模拟网络。为了评估这些方法的性能(当k?已知时称为me,即m估计量;当k?未知时称为meun),我们将其与ng等人(2001)提出的标准化谱聚类方法(称为nsc)、zhang和zhou(2020)提出的平均场变分推断方法(称为mf),以及基于模块度的谱聚类方法进行了比较。

讨论
我们提出了一种针对社区数量未知的配对型非参数加权随机块模型的非参数社区检测方法,并证明了其一致性。我们的方法灵感来源于最初无需模型假设的经典图聚类算法,我们发现它在这一统计模型中表现良好。尽管我们必须使用近似算法,但它仍然能够优于其他竞争性方法。这为未来研究更精确的方法提供了方向。>
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号