18
$\begingroup$

I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. Data transfer rates cannot be negative. I am just blanking out while thinking of negative weight edges in graphs.


Can we have a list of say 6 or 7 real-life examples where negative weights make intuitive sense?

$\endgroup$
7
  • 3
    $\begingroup$ Think of foreign exchange graphs. Take the logarithms of the exchange rates. $\endgroup$ Dec 2, 2021 at 10:40
  • 3
    $\begingroup$ @RodrigodeAzevedo Using the logarithm in this case does not seem to be very "real life"-like. $\endgroup$
    – Nathaniel
    Dec 2, 2021 at 12:13
  • 4
    $\begingroup$ Does this answer your question? What is the significance of negative weight edges in a graph? $\endgroup$
    – Nathaniel
    Dec 2, 2021 at 12:17
  • 2
    $\begingroup$ Hint: Don't think in terms of things like distances in space, think in terms of things like cost vs gains, obstacles vs boosts; furthermore, nodes don't have to represent points in space - they can be states of things. $\endgroup$ Dec 3, 2021 at 8:03
  • 12
    $\begingroup$ @Nathaniel: On the contrary: when you change from currency to currency to currency, you multiply the exchange rates together to get at the final amount. But in graph theory, you typically add edge weights together to get the cost of a path. How to resolve the two? Take logarithms, and label the edges with those... then you can add the edge costs of a path together, and raise the result to a power, and that'll give you the result of doing all those exchanges :) $\endgroup$
    – psmears
    Dec 3, 2021 at 11:53

6 Answers 6

34
$\begingroup$

Distance between cities can't be negative, but if you are programming for an electric car, then a downhill road segment will regen, thus the energy used is negative. It is very important to take that into account when predicting range.

In a neural network, we can use negative weights to indicate that one neuron firing is inversely correlated with another neuron.

In a clustering network we can use negative edges to indicate that two points should certainly not belong together. This is also relevant in community detection.

In sports, you can use a directed edge from $a$ to $b$ to mean the likelihood that $a$ will win against $b$ when $a$ is home team. In general, when we have non-symmetric relationships, $a\to b$ is different from $b \to a$ and we can't necessarily encode negative numbers with reverse arcs. This is also relevant in finance where $a \to b$ can mean that $a$ either owes money or $b$ owes money. The direction of the arrow can mean who is responsible for the transaction to take place.

Attractive and repulsive forces are used both in graph drawing, but also in particle simulation and simulation of other dynamical systems. These are often undirected positive or negative edges. In simulation of fluids, you will also have negative values denoting different forms of pressures from one area to another.

$\endgroup$
7
$\begingroup$

In a social network. Where the source node is a person the target node is another person and the connection represents the preference the source has for the target. The sign representing the direction of the sentiment.

In quantitative finance where the nodes are securities and the connections are the correlation coefficients.

A few years ago I made a triangular arbitrage algorithm that used a signed metric to determine the transactional inefficiencies an agent is exposed to when they use currency A to buy some currency B. As the agent walks through the graph (they trade from one currency to the next) they keep track of the sum of the values from edges they've traversed, lets call this value s. Once they make it back to the node they started from, the final amount of money they finish with is equal to the amount they started with times s+1. The trick to making money is to find a cycle that leaves you with an s>0. The metric I developed was designed in a way that walking the same cycle but in the opposite direction leaves you with -s.

$\endgroup$
4
$\begingroup$

Negative edge weights are important for abstract planning.

In a typical graph you might use for this, there are two specific properties that are important:

  • The nodes represent possible states of a complex system that is being modeled.
  • The graph is directed.

As a result, the graph is functionally a representation of a state machine.

In such a graph, each edge can then be weighted with a relative value of making the state transition that the edge represents as compared to a value of zero for maintaining the current state (though often the system being modeled will not let you maintain the current state). You can then use the resultant value of a path through the graph to compare it to other paths and decide on which sequence of steps to take.

The ‘classic’ application of this from computer science is writing a chess engine. In chess, each possible board state can be assigned a value for each of the two players indicating how advantageous it is. Once you have a way to assign those values, you can compare the difference between the current position and each possible derivative position to pick the ‘best’ move. This is, at their core, how a majority of ‘traditional’ chess engines work, though they vary in how they assign values to each position (and how many steps ahead they may look).

The same approach though can be used to plan utilization of almost any system you can model as a state machine, be it an abstract strategy game like chess, or a business plan, or even the process of assembling a car, which makes it exceedingly useful for many real-life applications.

$\endgroup$
3
$\begingroup$

Consider someone speedrunning a complex videogame, which we abstract to moving through a graph. While the run is measured in absolute time, they might want to use relative time for judging strategies: how much time a route gains or loses them relative to some baseline "par". Then negative edges would correspond to time saved, and positive edges to time lost.

$\endgroup$
3
$\begingroup$

Say you are traveling city to city and along the way, you can pick up cargo or a passenger or whatever and earn profit on some of the travel hops (there are a number of carpooling services online where people post their to/from/when needs and how much they are willing to pay). So building a graph of possible profits (and on legs without a carpool offer, there will just be a negative cost for gas) can give you a way to plan your cheapest (i.e. most profitable) way to cross the country.

$\endgroup$
0
$\begingroup$

How about an electricity network where the positivity/negativity of the weight indicates the direction of current flow.

$\endgroup$
1
  • 1
    $\begingroup$ That's a network flow problem, not a problem where edges have negative weights $\endgroup$
    – Nayuki
    Dec 2, 2021 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.