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