基于SCAN算法中増量计算无影响节点的内部情况

  这个算法,在上一篇文章中,已经采用了各种实例来验证算法的正确性,但是确实有一种情况,我们没有考虑,因此这篇文章继续补充增量的计算情况。

  在增添边缘的过程中,确实会出现增添之后,所有有可能变化的节点都没有变为核心节点,我们本来是不对这部分进行操作,直接输出原来的聚类,但是我没有考虑到的是,添边之后,会对这些有可能变化的节点有其他影响,就是结构相似度会发生改变,因为增量之后,节点会有额外相连接的节点,根据结构相似度的公式,对原来节点会产生结构相似度的影响,因此我们不能简单的将原来聚类输出,因为不满足结构相似度的邻居是不能被赋予与它相连接的聚类核心节点ID的,因此我们如果判断,当有可能变化的节点均没有变为核心节点后,对每一个原来聚类中的核心节点进行重新聚类,创建新的队列,将满足结构相似度的邻居加入其中,之后继续判断是否是核心,将那些原来是聚类中,现在由于添边导致结构相似度不满足的点,标记为异常值,之后将聚类结果输出,这是一种额外情况,我们同时要考虑到。新增程序清单如下,其中DOM为标记点,用来判断是否节点均没有变化为核心节点。

             if(DOM==0)
                      {
                             for(int number=0;number<V.length;number++)
                                 {
                                    if(IsCore(number,u,e))                   
                                    {  
                                     D[dd]=number;
                                     dd++;
                                     Numbers++;
                                    }
                                 }
                           for(int R=0;R<Numbers;R++)
                           {
                               community[D[R]]=community[D[R]]+V.length;
                               for(int i=0;i<edge.length;i++)
                               {
                                   if(edge[i][0]==D[R])
                           {     
                       NeighboR = edge[i][1]; 
                       double Sim = computeSim( D[R],NeighboR );   
                       if(Sim>e)                   
                       {                                 
                        community[NeighboR]=community[D[R]];      
                        Qq.offer(NeighboR);                                  
                       }
 
                    }
                    if(edge[i][1]==D[R])
                   {                           
                       NeighboR = edge[i][0];             
                       double Sm = computeSim(D[R],NeighboR);
                       if(Sm>e)
                       {
                         community[NeighboR]=community[D[R]];
                         Qq.offer(NeighboR);             
                       }                   
                   }
                               }
                   while(Qq.size()!=0)    
                {       
                    int x=0;
                    int y = Qq.poll();      
                    if(isCore(y,u,e))    
                    {
                    for(int i=0;i<edge.length;i++)   
                    {
                     if(edge[i][0]==y)
                    {
                      x = edge[i][1];

                      double Sim = computeSim(y,x);
                      if(Sim>e)
                      {
                              community[x]=community[D[R]];  

                      }
                    }
                      if(edge[i][1]==y)                  
                     {
                       x = edge[i][0];

                      double Sim = computeSim(y,x);
                      if(Sim>e)
                      {

                          community[x]=community[D[R]];

                      }
                    }
                    } 
                    } 
               }    
                       }
                           for(int s=0;s<V.length;s++){
                               if(community[s]>0&&community[s]<V.length+1)  //将那些原来是聚类中,现在由于添边导致结构相似度不满足的点,标记为异常值
                               {
                                   community[s]=-3;
                               }
                           }
                       }

基于SCAN算法中増量计算无影响节点的内部情况

首先我们输入e=0.7,u=2,进行聚类,之后进行増边3,7

基于SCAN算法中増量计算无影响节点的内部情况

  因为在添边之后,节点3与节点5的结构相似度不再大于0.7,因此将节点3排除出聚类,并标记为异常值,7也是同理,正确验证。

基于SCAN算法中増量计算无影响节点的内部情况

  之后我们再将e=0.7,u=2进行聚类操作,并增添边缘3,7。原聚类结果为节点4,5,11,12为核心节点。

基于SCAN算法中増量计算无影响节点的内部情况

  由于在增添完边缘3,7之后,节点3与节点5并不满足结构相似度,但是核心节点5与核心节点4满足结构相似度,因此归为一类,而节点3与节点4依旧满足结构相似度,所以归入一类中,因此依旧为两个聚类,并没有被标记为异常值,正确运行。

  这就是我们之前并没有考虑到的增量计算的另一种情况,在这里补充上完善增量算法,希望我们大家一起学习,共同进步,谢谢。

来源:琢磨先生DataBase,本文观点不代表自营销立场,网址:https://www.zyxiao.com/p/95234

发表评论

电子邮件地址不会被公开。 必填项已用*标注

侵权联系
分享本页
返回顶部