LASCNN algorithm

In graph theory, 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 -hop neighbor list and a duplicate free pair wise connection list based on -hop information. If the neighbors are stay connected then the node is non-critical

Function LASCNN(MAHSN)
    For ∀ A ∈ MAHSN
        If (A->ConnList.getSize() == 1) then
            A->SetNonCritical() = LEAF
        Else
            Continue = TRUE
            While (Continue == TRUE)
                Continue = FALSE
                For ∀ ActiveConn ∈ ConnList
                    If (A∉ActiveConn) then
                        If (A->ConnNeighbors.getSize() == 0)
                            A->ConnNeighbors.add(ActiveConn)
                            Continue = TRUE
                        else
                            If (ActiveConn ∩ ConnNeighbors == TRUE)
                                ActiveConn ∪ ConnNeighbors
                                Continue = TRUE
                            Endif
                        Endif
                    Endif
                End For
            End While
        Endif
        If (A->ConnNeighbors.getSize() < A->Neighbors.getSize())
            A->SetCritical() = TRUE
        else
            A->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