3
$\begingroup$

Can someone please point me in the direction of any theory on graphs where the edge weights are not scalars but represent some relation between the nodes that is a simple function of a single variable (simple, say piecewise linear).

In particular, I'm interested in various basic graph properties and also thinking of the graph as representing a network. So, for example, if the graph represented a communication network over time then the edge weights would be a function represented connectivity as a function of time, how do you find a valid path between nodes? I'm looking for help both on specific algorithms but also general theory if it exists?

I'm aware of time-extended networks where you explicitly expand out the dependence on the variable but, from what I've read, this incomplete and of limited applicability.

  • 0
    I'm not sure I understand the second sentence of the second paragraph. What is a valid path, exactly?2010-09-01
  • 0
    Edges are not scalars. Edges are relations between two nodes. e.g. suppose if (u,v) is an edge in a graph then they are related by some function f(u) = v. u, v and f can be anything. e.g. u and v can be column vectors and f can be a matrix. I am not sure I understand your question properly.2010-09-01
  • 0
    @TheMachineCharmer: I believe nai is referring to the _weights_ on the edges, e.g. the entries in the adjacency matrix.2010-09-01
  • 0
    @Qiaochu Yuan:humm.. you are right. I don't know if theory exists to take care of this. But I think it must be perfectly valid to assign non-scalars as *weights*. e.g. in finite state machine they are transition conditions; also if u,v are vectors we can use u-v as 'weight'. In general, I think we can assign whatever we want to edges,nodes or weights if we can assign meanings to them and be able to interpret without getting into trouble.2010-09-01
  • 0
    @nai By connectivity is a function of time if you mean there is function of time that decides if there is edge between nodes i.e. f(u,v,t) then you will have different graph at different 't's. So, you will have to input the value of 't' and get the graph at time 't' i.e. G(t) and then operate algorithms that work for normal graphs on it.2010-09-01
  • 0
    Thanks for the comments: to clarify... Yes, I mean that the weights on the edges are functions of time. So rather than (a possibly weighted) adjacency matrix of scalars, it's a matrix of functions. It may help if I give an example. Think of the graph of a communication network where the edges represent connectivity via radio between the nodes. Now, allow the nodes to move about so the connectivity changes with time, i.e. the idea of an 'edge' changes over time. Given this dynamic network, how would you find a path (sequence of edges at times) that connects two nodes.2010-09-01
  • 0
    This is a specific example but I'm very interested in more theoretical ideas on how to treat such graphs, e.g. algebraic or spectral graph theoretic ideas. One brute force approach is to time expand the network where you (approximately) enumerate over all instantaneous G(t), for the range of t, and then link them together through time. I.e. you create a huge static graph representing the dynamic time graph. I'm looking for something more practical and elegant.2010-09-01
  • 0
    If the functions which map the time to the weights of edges are just functions and do not have any good properties, it is just a bunch of graphs varying over time in a weird way, and I would not expect anything better than that. If the functions satisfy some nice conditions (e.g. they are linear), there may be a room that something can be done.2010-09-01
  • 1
    Can you edit the title and the text of the question to clarify that you are considering the case where edge _weights_ are functions?2010-09-01

2 Answers 2

2

So, basically you have a graph G that varies over time.

    1    2    3
1  f11  f12  f13
2  f21  f22  f23
3  f31  f32  f33

Evaluate $f_{ij}(t)$ for $t$ to get $G(t)$ graph at time t.

Then you can use graph traversal algorithms like Depth-First Search, Breadth-First Search etc. for finding out which nodes are reachable.

However if you are allowing traveler to wait at nodes then problem becomes more difficult.

You can create one big graph by connecting G(t) for various time values. You can keep that graph small if you can limit time to wait at each node. If you know period of $f_{ij}(t)$ then also you can simplify this.

  • 0
    Thanks TheMachineCharmer, this is roughly what I've been using so far but it doesn't scale or generalize well. I'm hoping someone knows of a more general approach, perhaps it's not even in the field of graph theory!?2010-09-01
1

I came across a similar problem of using non-scalars as edge weights (vectors in my special case) and got to the conclusion that this is valid as long as you can define a total order on the edge weights and they are elements from a vector space that implements a linear operator.

The linearity together with the total order gives you characteristics of a equivalence relation, e. g. the transitivity that we need to get the weight of paths, since we can't just 'add up' the weights of the edges in the path.

Algorithms rely on that order (that is inherent in scalars). E. g. dijkstra that picks a unvisited node with the minimum distance. If those requirements are met one can easily adjust the algorithms to be applied to that graph instance.


More specific change the algorithms that you use to keep track of time (or introduce time steps that increase after each piece of solution your algorithm derived) and evaluate the edge functions each time you need them. If the functions do not take up too much computation time, you should be fine.