⚡ electrical engineering

Katz Centrality-Based Security Allocation in Positive Networks

This paper addresses security allocation in positive networked control systems under stealthy false data injection attacks by demonstrating that worst-case performance loss can be bounded via semi-definite programming, linking this bound to Katz centrality to enable a network-size-independent heuristic for optimal monitor node selection.

Original authors: Anh Tung Nguyen, Sribalaji C. Anand, André M. H. Teixeira

Published 2026-08-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Anh Tung Nguyen, Sribalaji C. Anand, André M. H. Teixeira

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city where traffic lights, water pipes, and power grids don't just sit there; they talk to each other. They form a giant, invisible web where a change in one neighborhood ripples through the whole city. In the world of engineering, we call these "networked control systems." Think of them like a massive game of telephone where every node (a water pump, a traffic sensor, a power station) whispers its status to its neighbors. The catch? These systems are "positive," meaning the numbers they deal with—like water volume or electricity flow—can never be negative. You can't have -5 gallons of water in a pipe.

Now, imagine a sneaky hacker trying to mess with this game. They don't want to blow things up; they want to be invisible. They inject tiny, fake numbers into the whispers between the nodes, trying to make the whole system panic or slow down without anyone noticing. This is called a "stealthy false data injection attack." The defenders are the city's security team, trying to place a limited number of "listening posts" (monitors) to catch the liar. The big question is: Where do you put your limited number of listening posts to stop the worst possible damage? If you pick the wrong spots, the hacker wins. If you pick the right ones, the city stays safe. This paper dives into that exact puzzle, trying to find the smartest way to protect these vital, positive networks.

The Paper's Big Idea: The "Influence Score" for Security

This paper tackles the problem of how to best protect these interconnected, positive networks from invisible hackers. The authors, Anh Tung Nguyen, Sribalaji C. Anand, and André M. H. Teixeira, realized that trying to calculate the perfect defense for every possible attack scenario is like trying to count every grain of sand on a beach while the tide is coming in—it's too slow and too hard for big networks. Instead, they found a clever shortcut using a concept called "Katz centrality."

To understand their solution, imagine the network as a social circle. Some people are just popular because they have many friends (that's a simple "degree" count). But Katz centrality is different; it asks, "How much influence does this person have if we count not just their friends, but their friends' friends, and their friends' friends' friends?" It measures how far a ripple can travel from a specific person. The authors adapted this idea for security. They created two special "influence scores": one that measures how much damage a specific node can cause to the whole network (the "Performance Katz"), and another that measures how well a specific node can be heard by the security monitors (the "Monitor Katz").

The paper's main finding is that under certain conditions, the worst damage a hacker can do is directly linked to these influence scores. Instead of running a massive, complex computer simulation to find the perfect defense, the authors showed that you can use these scores to guess the best spots for your monitors. They proved mathematically that if the network is robust enough, the answer to "how bad can it get?" is exactly equal to a simpler calculation involving these scores. This turns a problem that used to take forever to solve into one that scales easily, even for huge networks.

The "Heuristic" Search: A Smart Guessing Game

Since finding the absolute perfect set of monitors is still computationally heavy (like trying to solve a Sudoku puzzle with a billion squares), the authors didn't stop at just measuring the damage. They built a "heuristic search," which is a fancy way of saying a smart guessing strategy.

Here is how their strategy works, using the analogy of a game of "Capture the Flag":

The Attackers' Move: The hackers pick a group of nodes to attack. The authors calculate the "principal directions" of the attack—basically, the specific ways the attack ripples through the network.
The Defenders' Move: The defenders need to place monitors to block these ripples. The authors' algorithm looks at the "Monitor Katz" scores and asks: "Which node, if we put a monitor there, would best align with the direction of the attack?"
The Scoreboard: They assign a "score" to every node in the network. If a node is great at catching a specific type of attack ripple, its score goes up.
The Selection: The algorithm picks the top-scoring nodes to be monitors. If the initial pick doesn't quite cover all the attack directions (a condition they proved is necessary), the algorithm adds one more monitor until the job is done.

What the Simulations Showed

The authors tested their ideas on random networks, similar to how you might test a new bridge design on a computer model before building it. They ran simulations on networks ranging from 100 to 200 nodes.

The Math Check: They found that their simplified math (using the Katz scores) was almost identical to the heavy, complex math they were trying to replace. The difference was so tiny (less than 0.00004%) that for all practical purposes, the shortcut was perfect.
The Speed Check: The complex math took a long time to run as the network got bigger. Their new method? It stayed fast and efficient, proving it could handle large-scale networks without crashing the computer.
The Defense Check: When they compared their "smart guess" monitors against the "perfect" monitors (found by a very slow, heavy-duty method), the results were impressive. In most cases, their heuristic found a solution that was just as good as the perfect one. Sometimes, because their method was so thorough, it actually picked one extra monitor to be safe, which made the defense even better than the budget-limited "perfect" solution.

What This Means (and What It Doesn't)

The paper is very clear about what it has and hasn't done. They have proven mathematically that their simplified formula works perfectly if the network is robust enough. They have simulated that their smart-guessing algorithm works well in practice, often matching the best possible outcome.

However, they are not claiming this is a magic wand that solves every security problem forever. They explicitly note that their method relies on the network being "positive" (numbers can't be negative) and that the "perfect" solution is still a hard problem to solve directly for huge networks. Their contribution is a practical, scalable tool that gives defenders a very strong, mathematically backed way to place their monitors without needing a supercomputer. It turns a nightmare of complex equations into a game of "who has the most influence," making it possible to secure the massive, interconnected systems that keep our modern world running.

Technical Summary: Katz Centrality-Based Security Allocation in Positive Networks

Problem Formulation

This paper addresses the security allocation challenge for positive networked control systems (NCS) represented by positive-weighted directed graphs (digraphs) under stealthy false data injection (FDI) attacks. The system consists of interconnected one-dimensional subsystems (nodes) where state variables are constrained to be non-negative, reflecting real-world applications such as transportation and water distribution networks.

The scenario involves two opposing agents:

The Adversary: Selects a specific set of $\alpha$ nodes to inject additive, non-negative FDI signals into the information broadcast to their neighbors. The adversary aims to maximize the network performance loss (defined as the $L_2$ -norm of the weighted state vector) while remaining stealthy. Stealthiness is defined by the condition that the energy of the output at monitored nodes does not exceed a predefined alarm threshold.
The Defender: Selects a set of at most $\beta$ nodes to monitor. The defender's objective is to minimize the worst-case network performance loss caused by the adversary, subject to the stealthiness constraints.

The core research problems are:

Problem 1 (Scalable Assessment): Compute the worst-case disruption (security metric) in a manner independent of network size.
Problem 2 (Optimal Selection): Graph-theoretically select a monitor set for a fixed attack scenario to minimize the worst-case disruption.
Problem 3 (Robust Selection): Graph-theoretically select a monitor set robust against all admissible attack scenarios.

Methodology

The authors leverage the positivity of the system dynamics and dissipative systems theory to transform the non-convex security assessment problem into a tractable optimization framework.

SDP Upper Bound: Initially, the worst-case disruption is shown to be upper-bounded by a Semi-Definite Programming (SDP) problem derived using a storage function and supply rate. However, this standard SDP involves a matrix variable of size $N \times N$ (where $N$ is the network size), leading to computational complexity scaling as $O(N^6)$ , which is intractable for large networks.
Exact Computation via Robustness Condition: By introducing a sufficient robustness condition (relating the worst-case disruption without monitors to the alarm thresholds and performance weights), the authors prove that the SDP solution becomes exact and simplifies significantly. Under this condition, the matrix variable $P$ can be restricted to be a non-negative diagonal matrix.
Katz Centrality Connection: The simplified SDP is further reduced to a formulation independent of the network size $N$ $N$ . This reduced problem establishes a direct relationship between the security metric and two adapted Katz centrality measures:
- Monitor Katz Centrality ( $K_\delta$ ): Incorporates alarm thresholds.
- Performance Katz Centrality ( $K_W$ ): Incorporates performance weighting factors.
  The security metric is characterized by the geometric relationship between an ellipsoid representing the attack impact (derived from $K_W$ ) and an ellipsoid representing the monitor coverage (derived from $K_\delta$ ).
Geometric Heuristic: Based on the geometric interpretation of the simplified SDP, the authors propose a principal-direction heuristic (Algorithm 1). This algorithm:
- Computes the eigenpairs of the attack impact matrix.
- Calculates a score for each node based on how well its "growth direction" (derived from $K_\delta$ ) aligns with the principal axes of the attack impact ellipsoid.
- Selects monitor nodes with the highest scores to cover the attack directions, ensuring the necessary rank condition for a finite solution is met.

Key Contributions

The paper makes the following specific contributions:

Tractable Upper Bound: Demonstrates that the worst-case network performance loss under stealthy attacks is upper-bounded by a tractable SDP problem using dissipative systems theory.
Network-Size Independence: Establishes that under a sufficient robustness condition, the worst-case disruption equals the solution to a simplified SDP that is independent of the network size. This is achieved by proving the optimal solution matrix $P$ is diagonal.
Geometric Characterization: Provides a necessary and sufficient geometric condition for the existence of a finite solution, linking the problem to two adapted versions of the Katz centrality measure. This reveals that the security metric depends on the alignment between attack directions and monitor-induced growth directions.
Heuristic Search Algorithm: Develops a heuristic search algorithm (Algorithm 1) based on the Katz centrality measures to select sub-optimal monitor nodes. This approach bypasses the need to solve complex mixed-integer optimization problems, making it scalable for large networks.

Results

The proposed methods were validated through extensive simulations on Erdős–Rényi random graphs with varying network sizes ( $N=100$ to $200$ for assessment, $N=20$ to $30$ for allocation due to the computational cost of the baseline comparison).

Validation of Theorem 1: Simulations confirmed that under the sufficient robustness condition, the simplified diagonal SDP and the non-P formulation yield values nearly identical to the full SDP (relative differences $< 4 \times 10^{-5}\%$ ). Even when the condition does not strictly hold, the simplified formulations provide meaningful upper and lower bounds with a ratio consistently close to 1.
Computation Time: The simplified formulations (diagonal and non-P) demonstrated significantly lower computation times compared to the full SDP, confirming their scalability.
Algorithm Performance: The heuristic monitor set ( $M^*_{Katz}$ ) achieved a worst-case disruption comparable to the budget-constrained optimal set ( $M^*_{MISDP}$ ) obtained via mixed-integer SDP. In the majority of cases, the heuristic required only one additional monitor node beyond the budget $\beta$ to satisfy the rank condition (Theorem 2), resulting in a performance ratio ( $\rho_Q$ ) close to zero.

Significance and Claims

The paper claims to offer practical insights for safeguarding large-scale networked control systems against stealthy false data injection attacks. Its significance lies in:

Scalability: Moving away from NP-hard mixed-integer SDP formulations and $O(N^6)$ complexity to graph-theoretic heuristics that scale with network size.
Interpretability: Providing a clear graph-theoretic interpretation of the security metric through Katz centrality, linking system dynamics, network topology, and security parameters.
Feasibility: Offering a method to identify "vulnerable" attack sets and "effective" monitor nodes without solving complex optimization problems, thereby enabling security assessment and resource allocation in large-scale positive networks where previous methods were computationally prohibitive.

The authors note that while the heuristic does not guarantee the absolute optimal monitor set, it provides a feasible candidate set that often outperforms the budget-constrained optimal set by slightly relaxing the budget constraint to ensure feasibility (finite disruption).