- Source: LASCNN algorithm
In graph theory, LASCNN is a Localized Algorithm for Segregation of Critical/Non-critical Nodes The algorithm works on the principle of distinguishing between critical and non-critical nodes for network connectivity based on limited topology information. The algorithm finds the critical nodes with partial information within a few hops.
This algorithm can distinguish the critical nodes of the network with high precision, indeed, accuracy 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 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.
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
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.
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
External links
Critical Nodes application