基于正则拉普拉斯矩阵的LEMON改进算法
发布时间：2021-02-08 07:58
重叠社团检测是复杂网络中的一个重要研究领域,在众多重叠社团检测算法中,基于局部谱提出的LEMON（Local Expansion via Minimum One Norm）算法复杂度小、效率高,但在处理含有噪声的数据集时并不能得到很好的社团检测结果。针对噪声问题提出了一种基于正则拉普拉斯矩阵的LEMON改进算法。该算法通过矩阵扰动的方式构建正则拉普拉斯矩阵来表征复杂网络的结构信息,提高了原LEMON算法的抗噪性。在Amazon,Youtube,DBLP,Orkut数据集上的实验表明本文算法相较于原LEMON算法可以获得更鲁棒的结果。
【文章来源】：西南科技大学学报. 2020,35(02)
【文章页数】：6 页
【部分图文】：
本文算法与LEMON算法的带噪实验结果
在复杂网络的计算中，数据集常常由大量的节点与边组成，如果对所有节点和边进行逐一计算无疑会加大计算成本。考虑到对于单一节点来说，它的邻居(或者距离较近的)节点群对比于离它较远的节点群来说有更大的概率属于同一社团，通过局部图[10]方法我们可以围绕种子节点来生成一个子图GS，替代全图G进行计算，这样的话我们既可以尽可能多地找到待测社团中的节点，同时又能减少计算复杂度。构建子图的过程大致如图1所示，对于初始种子节点3来说，通过随机游走算法我们选择距离其较近的节点6,2,5,10,9，剔除掉较远的1,4,7,8节点，构建一个相较于原图G={1,2,3,4,5,6,7,8,9,10}来说节点更少的子图GS={2,10,3,9,5,6}。在本实验中，我们采用的是局部图的方法从初始的种子节点的集合开始随机游走选择出其中概率较大的节点(概率越大表示越有可能是待测社团中的节点)，剔除掉概率较小的节点。直到概率分布扩散到β|C|avg个节点当中。其中β|C|avg需要足够大，应尽可能多地包含待测社团中的节点。其中β是一个常数，|C|avg为数据网络中社团的平均大小。最初的种子集合中一般只含有2个节点[6]，算法的迭代过程中，种子集合中不断加入新的节点，这些节点都是大概率为待测社团中的节点。直觉上来说向种子集合中加入与种子节点不相关的节点会不可避免地造成节点传导率(conductance)[11]的增加，所以找到一个低传导率的集合更能确保集合内节点之间的链接更紧密，也就是说其包含的节点更大概率属于同一社团。同时，通过对传导率的计算[12]，可以对算法的输出进行界定，防止添加过多的不相关节点导致社团检测的效率降低。
其中，Acca表示算法a在某一数据集上的聚类准确率，mjaxAcca表示对于同一数据集而言参与比较的算法中最高聚类准确率的值。由上式可知，对于一个数据集来说最好的算法a*代表其Ra*=1，同时其他的算法。Ra越大，代表算法a在该数据集上有更好的表现。因此，对于所有数据集的Ra的和可以看作是算法a的鲁棒性的度量，和越大表示鲁棒性越好。对于本文算法与LEMON算法来说，我们分别在8种不同的数据集上对两种算法进行了测试，结果如图3所示。本文算法在8种数据集上的Ra值分别为1.000,1.000,1.000,0.579,1.000,0.778,1.000,1.000，即本文算法的总Ra=7.357大于原LEMON算法的总Ra=7.106(如柱状图3所示，左边本文算法的总Ra值明显高于右边LEMON算法的总Ra值)。综上所述，虽然本文算法在“Youtube with Noise”以及Orkut数据集上的表现稍差于原LEMON算法，但总体而言，本文算法的表现依然优于原LEMON算法，即本文算法比LEMON算法更具鲁棒性。5 结论
本文编号：3023609
【文章来源】：西南科技大学学报. 2020,35(02)
【文章页数】：6 页
【部分图文】：
本文算法与LEMON算法的带噪实验结果
在复杂网络的计算中，数据集常常由大量的节点与边组成，如果对所有节点和边进行逐一计算无疑会加大计算成本。考虑到对于单一节点来说，它的邻居(或者距离较近的)节点群对比于离它较远的节点群来说有更大的概率属于同一社团，通过局部图[10]方法我们可以围绕种子节点来生成一个子图GS，替代全图G进行计算，这样的话我们既可以尽可能多地找到待测社团中的节点，同时又能减少计算复杂度。构建子图的过程大致如图1所示，对于初始种子节点3来说，通过随机游走算法我们选择距离其较近的节点6,2,5,10,9，剔除掉较远的1,4,7,8节点，构建一个相较于原图G={1,2,3,4,5,6,7,8,9,10}来说节点更少的子图GS={2,10,3,9,5,6}。在本实验中，我们采用的是局部图的方法从初始的种子节点的集合开始随机游走选择出其中概率较大的节点(概率越大表示越有可能是待测社团中的节点)，剔除掉概率较小的节点。直到概率分布扩散到β|C|avg个节点当中。其中β|C|avg需要足够大，应尽可能多地包含待测社团中的节点。其中β是一个常数，|C|avg为数据网络中社团的平均大小。最初的种子集合中一般只含有2个节点[6]，算法的迭代过程中，种子集合中不断加入新的节点，这些节点都是大概率为待测社团中的节点。直觉上来说向种子集合中加入与种子节点不相关的节点会不可避免地造成节点传导率(conductance)[11]的增加，所以找到一个低传导率的集合更能确保集合内节点之间的链接更紧密，也就是说其包含的节点更大概率属于同一社团。同时，通过对传导率的计算[12]，可以对算法的输出进行界定，防止添加过多的不相关节点导致社团检测的效率降低。
其中，Acca表示算法a在某一数据集上的聚类准确率，mjaxAcca表示对于同一数据集而言参与比较的算法中最高聚类准确率的值。由上式可知，对于一个数据集来说最好的算法a*代表其Ra*=1，同时其他的算法。Ra越大，代表算法a在该数据集上有更好的表现。因此，对于所有数据集的Ra的和可以看作是算法a的鲁棒性的度量，和越大表示鲁棒性越好。对于本文算法与LEMON算法来说，我们分别在8种不同的数据集上对两种算法进行了测试，结果如图3所示。本文算法在8种数据集上的Ra值分别为1.000,1.000,1.000,0.579,1.000,0.778,1.000,1.000，即本文算法的总Ra=7.357大于原LEMON算法的总Ra=7.106(如柱状图3所示，左边本文算法的总Ra值明显高于右边LEMON算法的总Ra值)。综上所述，虽然本文算法在“Youtube with Noise”以及Orkut数据集上的表现稍差于原LEMON算法，但总体而言，本文算法的表现依然优于原LEMON算法，即本文算法比LEMON算法更具鲁棒性。5 结论
本文编号：3023609
本文链接：https://www.wllwen.com/kejilunwen/yysx/3023609.html
