lines
lines
lines
Earth Interconnected
E Ecosystems, drug smuggling routes, airline traffic, the internet.

All are networks, and all networks have points of vulnerability and points representing potential improvement. Surprisingly, even the most dissimilar networks are similar enough for strategic planners to use the same models to explore them. This flexibility of network models is what makes the research of Tim Matisziw, an assistant professor with a joint appointment in civil and environmental engineering and geography at MU, so far-reaching. The models he develops have applications for everything from national security to saving salamanders.

Consider him an expert in all sorts of decision support.

“You have limited resources and want to induce a change in a network,” he says. “I develop models that can search for the best- or worst-possible scenarios of network change — the scenarios that would be the most damaging in cases of loss or most beneficial in cases of improvement.”

As Matisziw defines it, a network is the set of relationships among components of a system. Networks can take all kinds of forms — from physical and biological to social and economic — but, at their most basic level, all can be understood as collections of “nodes” and “arcs:” Nodes are the points representing elements of a system and arcs the lines representing connections between pairs of nodes.

Matisziw (pronounced MAT-uh-shoe) first became fascinated with the connections and interdependencies that networks represent in his undergraduate geography courses.

“One of the things we talk about a lot in geography is how it’s hard to take things out of their geospatial contexts and study them because everything is linked to something else; everything is somehow influenced by the things going on around it,” he says.

M

Matisziw brought that mindset to his more advanced studies, realizing that what he had considered to be a geographical notion about linkages was also a significant area of research in the network sciences: namely, mathematics and graph theory.

“I was realizing, 'Hey, in geography there’s a lot of complex interactions out there we want to explore,’ and, 'Hey, here are approaches capable of accounting for and analyzing these types of complex interactions.’ ”

The kind of network modeling Matisziw does uses a mathematical problem-solving approach termed “optimization” or “mathematical programming.” This is the same kind of math — and the same kind of modeling — that is used in business and economics to identify optimal financial outcomes.

High school algebra students get the basics of mathematical optimization when learning to graph linear equations, an exercise that involves searching for possible values of x and y, given specified constraints. In Matisziw’s research, nodes and arcs become the variables whose values must be solved in order to find the best outcome for a given objective. These problems, too, involve specified constraints.

Take the example of a government that needs to prevent attacks on its digital infrastructure or of an HR manager who needs to avoid disadvantageous personnel cuts. For the government, the objective is to prevent destruction of vital infrastructure, while for the HR manager, it is to avoid the personnel cuts that would be the most damaging to the performance of the organization. But as Matisziw sees it, the objective for both is to identify the scenarios of change that would minimize or maximize damage to the system.

If there are no constraints, the solution for both problems is easy: The scenario resulting in the greatest loss for either the government or the HR manager would be if all nodes and arcs were eliminated. Obviously, most planners aren’t worried about this absolute worst-case scenario but want to find the worst scenario within certain practical limitations. So the government might know that a terrorist has enough resources to take out just three routers and so wants to find which three would be most important to secure, while the HR manager might be looking to cut just one position and want to know which cut would have the smallest impact on the performance of the organization.

Providing a limit on the number of network nodes and arcs that can be damaged, Matisziw says, is an example of a constraint that can be modeled using linear equations. “That gives the model more structure so it won’t permit unrealistic solutions,” he says.

When networks are simple, with few nodes and arcs, planners can pretty easily locate the components that represent the greatest vulnerabilities or best prospects for improvement. But when network activities are complex, like, say, the traffic flow of a nation’s highway system, the movement of data on the Internet, or the patterns of endangered amphibian movements, the possibilities become too vast.

“Using intuition, the expert can look at a network and come up with different components that he feels is important,” Matisziw says. “But given that most systems are far too complex to understand via visual inspection alone, we need methods and tools that can assist in the search for scenarios of change that can best characterize the importance of arcs and nodes in a network.”

“That is what my methods are designed to do: look for those non-intuitive, sometimes counterintuitive, relationships within a network, that can represent weaknesses or places where resources can be best utilized.”

“That's what my methods are designed to do: Look for those non-intuitive, sometimes counterintuitive, relationships within a network that can be weaknesses...”
D

Defining a Network’s nodes and arcs is the first step planners must take in exploring it for vulnerabilities and strengths. In some cases, that basic descriptive information is readily available. A road map, for example, will show towns (nodes) and highways (arcs). But in many other cases, creating a visual representation of a network requires a tremendous amount of time and resources. It might be that a network has been poorly documented over the years. Imagine, for example, the challenge of locating every last mile of natural gas pipeline in the U.S. Or it might be a conceptual challenge in which the arcs are hard to define, such as a social network in which data reflecting interactions among members and their level of interaction are not readily apparent. Or it might be that the person wanting to understand the network is an outsider with limited access, like a police investigator attempting to break up a drug smuggling network.

Matisziw can’t tell planners what their own networks look like. Instead, his models help them explore what Matisziw calls “scenarios of interest.” Finding the right model for these interests doesn’t depend necessarily on the kind of network — the same general type of model can be used to explore a social network and a transportation network — but on users’ objectives and constraints. For example, if the HR manager were looking to hire more employees, that would require a different model than one for planning cuts. If a government needed to find the most efficient way to restore a power grid following an attack, that would require a different model than the one for finding its vulnerabilities.

The trick for Matisziw is figuring out how to represent both networks and users’ planning objectives in a way that is not too unwieldy for a regular computer platform to handle. That’s not too hard when there are few paths between any pair of nodes. But modeling becomes far more difficult when the number of possible paths expands.

“For most networks, even of a modest size, there could be millions and millions and millions of possible paths capable of providing connectivity between any pair of nodes, so it is not feasible to go in and enumerate all of them,” Matisziw explains.

Traditional analysis approaches have gotten around this difficulty by accounting for only the shortest path — or a limited number of paths — between any pair of nodes. This approach seems reasonable, Matisziw says, because often the shorter paths are the preferred paths.

“But at the end of the day, that’s just one out of a huge number of paths that exist,” he says. “That’s where a lot of the shortcomings in the research have fallen: How can you adequately represent connectivity when you don’t know all the ways of moving between pairs of nodes?”

This is also where one of Matisziw’s latest models, published the journal PLoS ONE in June 2012, made an important advancement. His model is the first that doesn’t require enumeration when considering all of the possible paths between all pairs of nodes in a network simultaneously.

“It allows all paths in a network to be represented; it doesn’t force us to reduce them to some manageable set,” he says. “It allows us to maintain the full integrity of the system without falling into the pitfall of erroneously leaving out some path that might turn out to be important in the end. ... And our model does it with a very nice constraint structure that makes it easy for linear programming and integer programming methods to find a provably optimal solution.”

How Matisziw arrives at his models involves a lot of “experimenting and tinkering around with equations,” he says. “Then, eventually, you have an, 'Aha!’ moment where you realize, 'I don’t have to do all of this work to represent the network; I can do it in a very concise, easy way.’ ”

The tools Matisziw uses in his tinkering are not as high-tech as one might assume.

“I go through a dozen notepads a week, just sketching out problems,” he says, adding he’s a visual person and just entering info into a computer doesn’t work for him. “I need to see a real example and work through it mechanically to have it make sense to me.”

Another contribution of Matisziw’s latest model is that it allows planners to take into account the levels of activity among nodes at a particular time when searching for vulnerabilities. That’s important, he explains, because “it’s not only the presence of a network infrastructure that matters; it’s how it’s used.”

Imagine the goal is to boost security for the three most important nodes in a network. One approach would be to find the three nodes that, if eliminated, would result in the loss of the most connectivity. But Matisziw realized that the importance of connectivity between a pair of nodes changes relative to the level of activity occurring between them, a relationship that can vary considerably over time.

Take telecommunications, he says. “You can have a telecommunication connection between two cities, but if it’s not being used, or it’s being used very little by that pair of cities, then its loss at that time wouldn’t affect interactions between those cities too much,” he says.

Thus, Matisziw continues, “a network’s resilience varies over space and time, making it imperative that planners take variations in network use into account in their network representations.

Matisziw emphasizes that determining best- and worst-case scenarios doesn’t imply those scenarios are going to actually happen. A terrorist, for example, might not target the three most critical routers in the digital network. Or the least productive employee might, in fact, turn out to be the owner’s son. But finding those best and worst scenarios provides planners with valuable strategic decision support.

“The tendency in a lot of planning applications is to propose a back-of-the-envelope solution, saying, 'We’re going to add some nodes here and connections here, and that should best increase efficiency,’” Matisziw says. But until someone has studied all of the alternative solutions, there’s no knowing how close the proposal comes to maximizing efficiency. Matisziw’s models allow planners to gauge that. So if there’s a big gap between a proposed plan and the theoretical best, then that suggests the existence of many other alternatives that could do better.

On the other hand, if the proposed solution is close to the theoretical best, then planners can celebrate, knowing they’ve done well.

“So it’s a benchmark,” Matisziw says. “Without having that benchmark, it’s impossible to tell how well you’re doing.”

And that’s the message that Matisziw has found can be hard to get planners to accept. Sometimes this is because “experts” would prefer to trust their intuition and tradition rather than the output of “some model,” and sometimes it’s because techniques for interpreting data just don’t have the same luster as the technologies for gathering it.

“Especially in my area, where you’re looking at vulnerability and robustness, trying to convince the military and intelligence agencies to use these tools — they’re really focused on the sexiness of technology,” Matisziw says. “There’s always been this tendency by decision-makers to focus on investing in equipment for collecting data rather than on analysis techniques.”

“But now,” he adds, “the decision makers are realizing we need analysis techniques to help us make sense of these massive amounts of data. I train my students in the development and use of these analysis methods. Later, when they are working in these industries, they can demonstrate their utility to the higher-ups; they can make a difference.”

Post a Comment

Reader comments are reviewed by Illumination staff before they are posted, so please keep your message civil and appropriate. All fields are required.

– Will not be published

Back to Top

University of Missouri

Published by the Office of Research

© 2014 The Curators of the University of Missouri