  Many real-world applications can be modelled as complex networks, and such
networks include the Internet, epidemic disease networks, transport networks,
power grids, protein-folding structures and others. Network integrity and
robustness are important to ensure that crucial networks are protected and
undesired harmful networks can be dismantled. Network structure and integrity
can be controlled by a set of key nodes, and to find the optimal combination of
nodes in a network to ensure network structure and integrity can be an
NP-complete problem. Despite extensive studies, existing methods have many
limitations and there are still many unresolved problems. This paper presents a
probabilistic approach based on neighborhood information and node importance,
namely, neighborhood information-based probabilistic algorithm (NIPA). We also
define a new centrality-based importance measure (IM), which combines the
contribution ratios of the neighbor nodes of each target node and two-hop node
information. Our proposed NIPA has been tested for different network benchmarks
and compared with three other methods: optimal attack strategy (OAS), high
betweenness first (HBF) and high degree first (HDF). Experiments suggest that
the proposed NIPA is most effective among all four methods. In general, NIPA
can identify the most crucial node combination with higher effectiveness, and
the set of optimal key nodes found by our proposed NIPA is much smaller than
that by heuristic centrality prediction. In addition, many previously neglected
weakly connected nodes are identified, which become a crucial part of the newly
identified optimal nodes. Thus, revised strategies for protection are
recommended to ensure the safeguard of network integrity. Further key issues
and future research topics are also discussed.
