Graph Powers

Earlier I had talked about multiplying the adjacency matrix of a graph by itself and how it leads to some interesting results. Multiplying the adjacency matrix by itself essentially corresponds to raising the graph by some integer exponent while maintaining the same number of nodes.

The powers of graphs are interesting structures. The p^th power, G^p of a graph G is obtained by adding edges between nodes in G that are separated by a pathlength (greater than 1 and) less than or equal to p. Specifically, the square of a graph is the graph resulting from joining all nodes that are separated by a pathlength 2. A cube of a graph is obtained by short-circuiting all 2 length and 3 length paths in the graph.

An important consequence of raising the graph to a power is diameter reduction. If G has diameter d, then graph G^p has diameter \ceil{d/p}. There are several other interesting properties of graph powers that we can observe, which are important in the design of optimal topologies. I’d be interested in knowing your ideas.

Advertisements

5 Responses to Graph Powers

  1. Joe says:

    Another way of powering up a graph is to take the Kronecker product of its adjacency matrix. There are quite a few open questions about this operation.

  2. sanket says:

    Joe: Thanks for the input!

  3. Shabnam says:

    Hello. I just read about your interestng graph powers. I ran into your article because I was looking for something similar but not identical. My question is: What would be the new diameter if the adjacency matrices of two strongly connected networks (non-zero diagonals) are multiplied? The two networks are strongly connceted and both have the same diameter m, and the same number of nodes. So would the resulting network (matrix) have the diamter ceil(m/2)?

    On a related question, what would happen if one of the networks has diameter less than m, like k < m. (I know that in this case the resulting diameter can not be greater than k.

    Or if you know of a reference that I can go to for further information?

    I sincerely appreciate your response/commets.

    Shabnam

  4. Kevin C. says:

    Shabnam,

    Unfortunately, I’m not sure that just multiplying the adjacency matrices would lead to a diameter reduction.

    For example, what would happen if both of the original networks were complete bipartite on the same partition of vertices? In this case both of the original graphs have diameter two, but the product of their adjacency matrices corresponds to two disjoint complete graphs, and doesn’t even have finite diameter.

    In the original post this was dodged because the graph power was defined by taking $A^k+A^{k-1}+\dots+A$ instead of just $A^k$.

  5. sanket says:

    Shabnam:

    Sorry about the delay in responding.

    If I understand you correctly, you are talking about multiplying the adjacency matrices of two different graphs. Whereas graph power is about multiplying the adjacency matrix by itself. So, in case of multiplying two different adjacency matrices, we need to be clear about the semantics of the operation.

    In case of graph power, $G^p$, what we are basically doing is: (1) computing a transitive closure of node reachability up to a level $p$ and (2) adding whenever a node is reachable from another in p or less (transitive) steps, we add an edge to make it a direct path. This reduces the diameter.

    Now, when you say multiplying two networks, are you talking about a graph product such as, say, graph composition (http://mathworld.wolfram.com/GraphComposition.html)? In that case, the product is a new network, with a different number of nodes. If not, can you explain how the multiplication works?

    Kevin:

    Thanks for the comments. Again, I am a bit stuck regarding the multiplication of two networks. Perhaps you can explain with an example how this works.

    Your other point is also interesting — taking only $A^k$. In other words, adding an edge only if there is a k-length path (and not where, $1 < pathlength <= k$). What happens do diameter when you short-circuit all k-length paths in a network, is an interesting question. This has an associated question — can we determine bounds on the number of k-length paths that exist in a network? I had investigated these questions a little. I call it the power* operation. I only have very elementary results though.

%d bloggers like this: