基于改进对称二值非负矩阵分解的重叠社区发现方法.docx

基于改进对称二值非负矩阵分解的重叠社区发现方法
基于改进对称二值非负矩阵分解的重叠社区发现方法
摘要：社区发现是复杂网络分析的重要任务之一，对于提取网络中具有内在联系的节点群体具有重要的应用价值。目前，对称二值非负矩阵分解（SymmetricBinaryNonnegativeMatrixFactorization，简称SB-NMF）作为一种有效的社区发现方法得到了广泛应用。然而，传统的SB-NMF方法存在一些问题，如无法准确识别重叠社区、易受初值选择的影响等。为了解决这些问题，本文提出了一种改进的SB-NMF算法，并将其应用于重叠社区发现。
关键词：社区发现；对称二值非负矩阵分解；重叠社区
1.引言
社区发现是复杂网络分析中的核心问题之一，旨在发现具有紧密联系的节点群体。社区发现在社交网络分析、生物信息学、推荐系统等领域具有广泛的应用。经典的社区发现方法包括基于图划分的方法、基于模块度优化的方法等。然而，这些方法在面对复杂网络时往往会遇到性能退化的问题。
近年来，基于矩阵分解的方法得到了广泛应用，并取得了较好的效果。对称二值非负矩阵分解（SymmetricBinaryNonnegativeMatrixFactorization，简称SB-NMF）是一种有效的矩阵分解方法，在社区发现中得到了广泛的应用。然而，传统的SB-NMF方法存在无法准确识别重叠社区、易受初值选择的影响等问题。因此，本文提出了一种改进的SB-NMF算法，用于重叠社区发现。
2.方法
2.1对称二值非负矩阵分解（SB-NMF）
对称二值非负矩阵分解是一种将一个对称矩阵分解为两个非负矩阵的方法。给定一个对称矩阵A，我们希望找到两个非负矩阵W和H，使得A≈W*H'，其中≈表示近似相等。在SB-NMF中，矩阵W和H都是二值矩阵。
2.2改进的SB-NMF算法
为了解决传统SB-NMF方法无法准确识别重叠社区的问题，本文提出了一种改进的SB-NMF算法。具体步骤如下：
（1）初始化矩阵W和H；
（2）更新矩阵W：将矩阵A与H相乘得到矩阵B，然后按行归一化B，并将大于阈值的元素设置为1，小于阈值的元素设置为0；
（3）更新矩阵H：将矩阵A与W相乘得到矩阵C，然后按列归一化C，并将大于阈值的元素设置为1，小于阈值的元素设置为0；
（4）重复步骤（2）和（3）直到收敛。
3.实验与结果
本文在现有数据集上进行了实验，评估了改进的SB-NMF算法在重叠社区发现上的性能。实验结果表明，改进的算法在准确识别重叠节点方面相比传统的SB-NMF方法有明显的提升。同时，该算法对于初值选择的依赖性较低。
4.结论与展望
本文提出的基于改进的SB-NMF的重叠社区发现方法在准确度和稳定性上都取得了较好的效果。然而，该方法仍有一些可以改进的地方。例如，可以考虑引入正则项来提高算法的稀疏性，或结合其他社区发现方法进行进一步优化。在未来的研究中，我们将继续改进和完善该方法，以使其能够更好地适用于各种复杂网络场景。
参考文献：
[1]NewmanMEJ.Detectingcommunitystructureinnetworks[J].TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystems,2004,38(2):321-330.
[2]WuF,HubermanBA.Findingcommunitiesinlineartime:aphysicsapproach[J].TheEuropeanPhysicalJournalB-CondensedMatterandComplexSystems,2004,38(2):331-338.
[3]DingC,HeX,ZhaH,etal.Adivisiveinformation-theoreticfeatureclusteringalgorithmfortextclassification[J].JournaloftheAmericanSocietyforInformationScienceandTechnology,2005,56(9):978-992.