导语：自用的论文笔记
Su S, Guan J, Chen B, et al. Nonnegative Matrix Factorization Based on Node Centrality for Community Detection[J]. ACM Transactions on Knowledge Discovery from Data, 2023, 17(6): 1-21.
文章目录
-
一、摘要
二、文章创新点
三、本文模型
1.准备工作
1、符号（Notations）
2、相似度量（Similarity Measures）
3、Symmetric NMF
4、homophily preserving NMFmodel (HPNMF)
2.模型框架
2.读入数据
总结
一、摘要
研究背景：社区检测是网络分析中的一个重要话题。近年来，在非负矩阵分解（NMF）技术的基础上，发展了许多社区检测方法。大多数基于NMF的社区发现方法只利用邻接矩阵中的一阶邻近信息，存在一定的局限性。此外，许多基于NMF的社区检测方法涉及稀疏正则化，以促进更清晰的社区成员。然而，在大多数正则化中，不同的节点被平等对待，这似乎是不合理的。
本文贡献：针对上述局限性，本文在NMF框架下提出了一种基于节点中心度的社区发现方法。具体来说，我们设计了一种新的相似性度量，它考虑了高阶邻居的接近程度，形成了一种更具信息量的图正则化机制，从而更好地细化检测到的社区。此外，我们引入节点中心度和基尼不纯度来分别衡量节点的重要性和社区成员的稀疏性。然后，我们提出了一种新的稀疏正则化机制，迫使具有较高节点中心性的节点具有较小的基尼杂质。
二、文章创新点
（1）我们提出了一种新的相似性度量，即h阶加权Jaccard，并使用它作为一个重要的成分来正则化检测到的社区。好的一面是，我们提出的h阶加权Jaccard包含更多的信息，高阶邻居比现有的局部相似性措施，这是很好的社区检测。
（2）我们利用节点中心性和基尼不纯性形成一种社区正则化机制，使得中心性较高的节点的社区成员关系变得稀疏。通过降低具有低节点中心性的节点的重要性并增加具有高节点中心性的节点的重要性，可以更有效地进行针对社区检测的非负矩阵分解过程。
（3）我们提出了一种新的NCNMF社区检测方法，它利用新提出的相似性度量和稀疏正则化机制下的NMF框架。
（4）我们推导出一个有效的优化算法的基础上，理论上保证收敛的梯度下降法求解NCNMF。此外，整个社区检测过程的计算复杂度进行了分析。它的规模与网络中的节点数，这是相同的许多现有的NMF为基础的算法，从而保证其效率的立方。
（5）我们在8个真实世界的基准网络上进行了广泛的实验，以测试NCNMF，并与13种最先进的社区检测方法进行比较。实验结果不仅表明了NCNMF的巨大优越性，而且表明NCNMF在有效性和效率之间取得了很好的平衡。此外，我们验证了理论分析，并进行敏感性分析。
三、本文模型
1.准备工作
介绍本文中使用的主要符号和术语。然后，我们提出了几个现有的相似性度量，the symmetric NMF model, and the homophily-preserving NMF model。
1、符号（Notations）
2、相似度量（Similarity Measures）
分为局部相似性和全局相似性。（local similarity measures and global similarity measures.）
局部相似性：朴素相似性测度[44]（the naive similarity measure）、共同邻居测度[27]（the Common Neighbor measure）、余弦测度[49]（the Cosine measure ）和Jaccard测度[49]（the Jaccard measure），等等。
由于余弦度量基本上用于计算文档相似度。由于Jaccard测度是Common Neighbor测度的增强版本，研究人员现在基本上使用Jaccard测度而不是Common Neighbor测度来计算节点相似性。接下来，我们只关注朴素相似性度量和Jaccard相似性度量。
（1）the naive similarity measure：等价于邻接矩阵。即，节点与节点有边时值为1，否则值为0。定义如下：
（2）the Jaccard measure。利用相邻节点集来计算相似度。它被定义为交集的大小除以两个节点的邻居集Γ（vi）和Γ（vj）的并集的大小。定义如下：
局部相似性度量有两个主要优点。一个是它们提供了一种直观的方法来表征节点相似性。二是计算方便，耗时少。然而，局部相似性度量的缺点也是显而易见的。它们只考虑了直接连接的邻居对相似性计算的影响，忽略了许多有用的信息，例如节点的高阶邻居[42]。
全局相似性：全局相似性度量包括著名的Katz指数[17]、LHN-II指数[1]等。
Katz指数是通过在图中搜索路径并将由用户指定的权重加权的每个路径长度的计数相加来计算的，这是一种基于图的计算方法，并计算全局网络中节点之间的相似性。
LHN-II指标是基于正则等价性[1]提出的，当节点x的邻居与节点y相似时，表明节点x和y相似，即节点的相似性是传递的。此外，子空间聚类模型[40]中构造的相似性矩阵也属于全局相似性度量。在这些模型中构建相似性矩阵的最常用方法是全连接方法，其中所有点的权重值都大于0。可以选择不同的核函数来定义边缘权重，最常用的是高斯核函数。它们可以通过考虑整个网络拓扑来克服局部相似性度量的缺点，但它们的时间复杂度高于局部相似性度量，而局部相似性度量在大型网络上不可扩展[42]。
3、Symmetric NMF
对称NMF试图通过两个相同的因子矩阵来重建邻接矩阵A，表示节点社区成员关系，它可以作为我们提出的NCNMF方法的构建块。
模型定义：
其中，将社区成员矩阵表示为，其中每个元素反映的趋势，SymmNMF将vi和vj之间的期望边数建模为：很明显，对于任何（vi，vj）∈E，a_aij应该与aij一致（使得边缘建模是精确的）
4、homophily preserving NMFmodel (HPNMF)
我们引入了保同态NMF模型（HPNMF）[44]。HPNMF的基本思想是考虑节点的相似性。两个节点越相似，它们的社区成员关系就应该越相似。根据[44]，给定一个定义良好的相似矩阵S ∈ Rn×n，实现上述思想的一个好方法是优化以下优化问题：
其中λ是控制节点相似性信息的重要性的正参数，γ也是控制H上的稀疏正则化的正参数，正则化器实际上是对H的l1-范数正则化以使它们更稀疏，并且L是定义为
其中，S是上述相似度矩阵，S'是对角矩阵，其中。
2.模型框架
在本节中，我们首先提出了一种新的相似性度量，即h阶加权Jaccard，它利用了网络中h阶邻域的结构信息。然后，我们开发了一种新的稀疏正则化机制的基础上的节点中心性和基尼杂质。结合这两种技术，我们提出了我们的NCNMF模型的社区检测问题。
1、h阶加权Jaccard相似公式
设h为表示跳数的非负常数，p为[1，h]范围内的整数。对于一个给定的节点i，我们将其直接连接的邻居记为Γ（vi），将其高阶邻居记为Γp（vi）= {vj ∈V:vj位于vi的p跳邻域中且2 ≤ p ≤ h}。基于这两个邻域集，我们提出了一种新的计算节点相似度的方法，即h阶加权Jaccard（记为w-Jaccard）相似度。其具体计算如下
其中是子相似度的权重
在我们的方案中，随p或q的增大而减小。这里的参数h建议在{1，2，3} [42]中设置为常数，表示节点vi最多可以取h阶邻居。
如第3.2节所述，等式（1）中的正常Jaccard相似性仅利用直接连接的邻居的信息。这忽略了一些有用的信息，如节点的高阶邻居，导致节点相似性的准确性有限。我们使用下面的例子来具体说明w-Jaccard相似性相对于Jaccard相似性的改进。
例1.考虑图2（a）和图2（B），超图G在G上添加了两个新节点{v8，v9}和三条新边{（v3，v8），（v4，v9），（v8，v9）}。让我们关注两个网络中的社区c3。直觉上，图2（b）中G中节点v3和v4之间的关系应该比图2（a）中G中的关系更接近。当我们应用w-Jaccard相似性（即，方程（3）），在两个节点上h = 2，Ωp，q =（5/8）pq [42]，我们得到图2（a）中的Simw-Jaccard（v3，v4）= 73/128，图2（B）中的Simw-Jaccard（v3，v4）= 361/605，这与实际相符。然而，如果我们应用正常的Jaccard相似性（即，方程（1）），我们发现SimJaccard（v3，v4）= 3/5在图2（a）和SimJaccard（v3，v4）= 3/7在图2（B），这与现实相矛盾。
思考：假设h=2时，节点vi和节点vj的sim计算为：节点vi的一阶邻居和节点vj的一阶邻居、节点vi的一阶邻居和节点vj的二阶邻居、节点vi的二阶邻居和节点vi的一阶邻居，以及节点vi的二阶邻居与节点vj的二阶邻居的加权之和。
2、基于节点中心性的稀疏正则化
在社交网络中，社区的核心节点通常具有较高的度和较大的节点中心度。节点中心性度量节点的中心属性，反映了节点在网络中的重要性。通常，节点vi的中心性越大，它与邻居节点形成社区的可能性就越大。受这一现象的启发，我们在这一部分提出了一种新的基于节点中心性的稀疏正则化方案，即，强制具有更高节点中心性的节点的社区成员关系更稀疏。
（1）计算度矩阵
把每个节点的度表示节点的中心性。其中dii表示节点i的度
（2）计算基尼不纯度
基尼不纯度的介绍：[翻译转载] 基尼杂质(Gini Impurity)的简单介绍-CSDN博客
基尼不纯度就是在决策树中用于量化聚类划分的好坏程度
Gini Impurity 就是将来自数据集合中的某种随机结果应用到数据集合中的随机数据所得到预期误差率。它的计算公式是：
C是数据类型的种类，p(i)是随机一个数据是类型i的概率。
当训练一个决策树时，选择最佳划分方案的依据就是：Gini Gain 越高越好。
Gini Gain = 原Gini Impurity - 划分后Gini Impurity
划分后Gini Impurity = sum(各个分区所占权重 * 分区Gini Impurity)
在基于NMF的社区检测的背景下，我们提出了以下公式来评估vi的社区成员是否是混沌的。
其中H =（hij）∈ Rn×k +是H1k = 1n的社区成员矩阵。
我们稀疏正则化方案的重点是降低具有较大节点中心性的vi的Gini（vi）值，从而使其社区成员更稀疏并增加其可分性。具体地说，我们的模型中所涉及的稀疏正则化项公式化
3.基于节点中心性的非负矩阵分解
基于上述讨论，提出了一种基于节点中心性的变型NMF模型，即，NCNMF，提出检测不相交社区。图3显示了我们提出的NCNMF方法如何检测社区的流程图。首先，根据输入数据构造邻接矩阵，然后从邻接矩阵中获得相似度矩阵和度矩阵。随后，我们利用NCNMF模型获得社区成员矩阵，从而划分社区。相应的优化模型被公式化为
(1)
:SymmNMF的目标函数，它是我们提出的社区检测方法NCNMF的骨干。
(2)
:旨在将两个相似的节点分配给同一个社区。这里，λ是控制节点相似性信息重要性的正参数，L是由等式（2）定义的图拉普拉斯矩阵（其中S被我们的wJaccard相似性矩阵代替）。
(3)
:回想一下，[H（Ek×n − HT）]ii表示节点vi的社区成员资格的基尼不纯，因此项Tr[H（Ek×n − HT）D]旨在降低具有更高节点中心性的所有vi的基尼（vi）。以这种方式，具有较高节点中心性的节点将被迫拥有更纯的（即，稀疏）社区成员。这一项起着稀疏正则化的作用。在这里，α是控制该正则化的重要性的正参数。
四、实验
1、实验设置
（1）数据集
我们使用了8个真实网络的数据集，如表2所示。在每个网络数据集中，社区由同一机构隶属关系内的节点形成。作为预处理步骤，我们从网络中删除所有孤立的节点。得克萨斯州、康奈尔州、华盛顿州和威斯康星州的网络从LINQS下载。2 Gene、Citeseer、Reality-call和BZR网络从Network Repository下载。
1 https://github.com/wowoHead/NCNMF.
2 https://linqs.soe.ucsc.edu/data.
3 https://networkrepository.com/index.php.
（2）比较方法
我们将我们的算法NCNMF与十三种最先进的社区检测方法进行比较，包括PNMF [48]，LPA [33]，GNMF [6]，SymmNMF [18]，DeepWalk [30]，ONMF [31]，MNMF [41]，Ego-Splitting [12]，NNSED [38]，DANMF [45]，HPNMF [44]，EdMot [21]和AGC [50]。
（3）参数设置
默认情况下，我们将所有基于NMF的方法的最大迭代次数设置为500。对于每种方法，我们运行20次，并报告平均值和标准差。对于我们的方法NCNMF，我们在{10−3，10−2，10−1，1，10，102，103}的范围内调整λ和α，设置停止准则为（Jt−1 − Jt）/Jt−1 ≤ 10−4，其中Jt表示第t次迭代的目标函数值，并设置参数δ = 105，h = 3，Ωp，q =（|V|/|E|）pq [42]，β = 0.5[11]。PNMF、LPA、SymmNMF、DeepWalk、ONMF、MNMF、EgoSplitting、NNSED、EdMot和AGC是无参数方法，其中不需要参数设置。对于GNMF，我们设置λ = 100 [6]。对于HPNMF，我们设置λ = 1和γ = 10−2 [44]，对于DANMF，我们设置层大小为n → 256 → 128 → k，预训练迭代的最大次数为100 [45]。本实验旨在评估所发现的社区w.r.t.地面真相社区。因此，对于所有竞争性方法，我们将检测到的社区数量设置为地面真实社区的数量，如表2所示。
（4）评价指标
F-score
准确率
2.社区检测方法的质量评价
本实验评估了所有社区检测方法的有效性。表3和表4列出了NCNMF和其他最先进的比较方法在所有8个网络数据集上的F-Score和准确率性能(NCNMF的参数在6.1节介绍的范围内调整，并报告了在最优参数下的结果)，我们观察到NCNMF在3/8和6/8的情况下表现最好，与13种最先进的社区检测方法相比，NCNMF的离分和准确率最高。虽然NCNMF在德克萨斯、康奈尔、华盛顿和Citeseer网络的F-Score方面不是最好的，但它达到了第二好的性能，并且性能几乎与最好的方法一样好。此外，NCNMF在F-Score和准确性方面均位居前2/8。这一出色的表现有力地证明了NCNMF的有效性。
3.相似性度量比较
在这个实验中，我们测试了三种相似性度量的有效性，包括Naive相似性，Jaccard相似性和我们的w-Jaccard相似性（分别当h = 2和h = 3时）。具体来说，我们在所有网络上运行不同版本的NCNMF，其中λ = 102，α = 1。F-score结果如图4所示。我们发现，在所有的数据集上，无论h的值是2还是3，w-Jaccard相似性的效果都优于朴素相似性和Jaccard相似性。特别地，在Reality-call网络上对应于w-Jaccard相似性（h = 3）的F-得分值为0.9809，这远大于naive和Jaccard相似性度量的F-得分值，其分别为0.6209和0.6235。从这个实验中，我们可以得出结论，我们的新的相似性度量在所有数据集上都有绝对大的优势。此外，我们发现在小数据集上（即，Texas，Cornell，华盛顿，和Wisconsin网络），w-Jaccard相似性在h = 2和h = 3时均获得相似的性能。这是因为在小数据集上，可能没有足够的高阶邻居。但是在更大的数据集上（即，Citeseer和Reality-call网络），h = 3的w-Jaccard相似度比h = 2的w-Jaccard相似度表现出更好的性能，这验证了h = 3的w-Jaccard相似度在大规模网络上可以获得更多有用的信息。
4.消融实验
在这一部分中，我们提出了一个消融研究，以显示NCNMF的每个成分的有效性。具体地说，我们在不同的参数设置下运行了几个NCNMF的消融版本，如下所述：
(1)设置λ=0和α=0，这显示了构建块A−HHT2F的性能。
(2)设置λ=10和α=0，这显示了4.1节中提出的新相似性度量的性能。
(3)设置λ=0和α=10，这表明了第4.2节中提出的稀疏正则化的性能。
(4)设置λ=10和α=10，体现了新的相似性度量和稀疏正则化的融合性能。
我们报告了德克萨斯州、康奈尔、华盛顿州和威斯康星州网络上所有不同NCNMF方法的F-Score结果。图5显示了新的相似性度量和稀疏正则化的结合可以产生更好的效果。文章来源：https://www.toymoban.com/news/detail-810989.html
总结
在这篇文章中，我们提出了一种新的社区检测方法，NCNMF。与现有的基于NMF的社区检测方法不同，NCNMF不仅利用h阶加权Jaccard相似度来提取更丰富的结构信息，而且引入节点中心度和Gini不纯度来规范节点社区成员关系.为了优化NCNMF，我们推导出了一个有效的算法，理论上可以保证收敛。我们已经进行了广泛的实验，以评估我们的NCNMF方法在八个真实世界的基准网络，实验结果表明，NCNMF优于国家的最先进的显着。在未来的工作中，我们计划研究如何将NCNMF扩展到有向网络并检测重叠社区。文章来源地址https://www.toymoban.com/news/detail-810989.html
到了这里，关于Nonnegative Matrix Factorization Based on Node Centrality for Community Detection 论文笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
