LASCNN algorithm

LASCNN is a Localized Algorithm for Segregation of Critical/Non-critical Nodes The algorithm worked on the principle of distinguishing between the critical and non-critical nodes for the network connectivity based on limited topology information The algorithm find the critical nodes with the partial information within a few hops.

This algorithm can distinguish the critical nodes of the network with high precision, and the accuracy can reach 90%. The accuracy of this algorithm can reach 100% when identifying non-critical nodes The performance of LASCNN is scalable and quite competitive compared to other schemes

Pseudocode

The LASCNN algorithm establishes k hop neighbor list and a duplicate free pair wise connection list based on k hop information. If the neighbors are stay connected then the node is non critical

Function LASCNN(MAHSN)
 For∀𝐴∈𝑀𝐴𝐻𝑆𝑁
   If (𝐴→𝐶𝑜𝑛𝑛𝐿𝑖𝑠𝑡.getSize()==1)then
      𝐴→SetNonCritical()=LEAF
   Else
      Continue = TRUE
      While (Continue==TRUE)
         Continue = FALSE
            For∀𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛∈𝐶𝑜𝑛𝑛𝐿𝑖𝑠𝑡
               If (𝐴∉𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛)then
                 If (𝐴→𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠.getSize()==0)
                    𝐴→𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠.add(𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛)
                    Continue = TRUE
                 else
                    If (𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛∩𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠==TRUE)
                       𝐴𝑐𝑡𝑖V𝑒𝐶𝑜𝑛𝑛∪𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠
                       Continue = TRUE
                    Endif
                 Endif
              Endif
           End For
     End While
  Endif
  If (𝐴→𝐶𝑜𝑛𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠.getSize()<𝐴→𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟𝑠.getSize())
     𝐴→SetCritical()=TRUE
  else
     𝐴→SetNonCritical()=INTERMEDIATE
  Endif
 End For
End Function

See also

• Connectivity (graph theory)
• Dynamic connectivity
• Strength of a graph
• Cheeger constant (graph theory)
• Critical point (network science)
• Depth-first search
• Breadth-first search

References

Category:Networks Category:Network theory