LASCNN algorithm

In graph theory, LASCNN is a Localized Algorithm for Segregation of Critical/Non-critical Nodes^[1] The algorithm works on the principle of distinguishing between critical and non-critical nodes for network connectivity based on limited topology information.^[2] The algorithm finds the critical nodes with partial information within a few hops.^[3]

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

Pseudocode

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

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

Implementation

Critical Nodes Application - An implementation for the LASCNN algorithm using PWCT

The Critical Nodes application is a Free Open-Source implementation for the LASCNN algorithm. The application was developed in 2013 using Programming Without Coding Technology software.^[8]

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