[News]

News: Welcome to The Oktave Forum.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Here's a problem I want to solve. Some of you might also find it interesting. I am describing it in an informal manner; let me know if it is not clear.

Given a free (unrooted) tree, how do I transform it into a desired target tree? Node labels are not important; only the structure or the topology matters. It is unrooted, and orientations don't matter (as in, there is no left or right subtree). The reason I am mentioning this is that there seem to be standard ways of transforming labeled and/or rooted trees.

OTOH, my problem, for example is, how do I transform a star into a straight line? Or how do I transform a 'T' or 'E' shaped tree into a straight line? Also, what is a good measure of 'distance' between two such trees?

We typically talk about edit distances between graphs. But edit distance is in terms of number of edge additions, deletions or replacements. Here, we need not talk in terms of edges. For example, if I want to transform a 'T' shaped tree into a straight line, I can simply make a "cut" at the intersection of the horizontal and vertical bars, and "attach" them end to end. That is only one operation, whereas edit distance between the two trees might be different.

Let me know your ideas.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Here's a simple approach. I think it works:

Call the source tree S and the target tree T. Let's say each has N nodes. Note that each tree has exactly N-1 edges.

1. Arbitrarily assign a number from [1..N-1] to each edge

2. For each node, assign a number from [1..N-1] such that a node assigned number i is incident on an edge numbered i.

3. There will be one node left out. Assign this the number 0 and call it the "root"

4. Now for each node with id i, call the edge with id i, as its "parent" link and the node on the other end as the "parent" of node i

5. For each node i = [1..N-1] in T do
5.1 See what node is the parent of i in T
5.2 Assign the same numbered node as the parent of node i in S
end

==============

This is obviously not the optimal transformation algorithm. But then, the worst case complexity is O(N) or N-1 edits. So there is not much to worry about optimality for the transformation in any case.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Not sure I follow this completely. I also found a simple method and implemented it. It seems to work. I will explain it below. That might also clarify what I was trying to do some more.

I want to transform one tree topology into another. One thing this implies is that I want to move from a set of degrees S to a set of degrees T. (I am using degree set instead of degree sequence as the order does not matter.) The total degree remains the same, of course. For example, a star with 8 nodes has the following degrees, S = {7, 1, 1, 1, 1, 1, 1, 1}, and a straight line has degrees, T = {2, 1, 1, 2, 2, 2, 2, 2}. So, a transformation here is basically a "redistribution of node degrees". In this example, we simply take 5 degrees from the node with a degree of 7 in S and add a degree 1 to 5 of the 7 remaining nodes. The "amount" of degrees redistributed is the cost of transforming from S to T.

This can be easily generalised. I still don't know whether this is the best way or if this is valid all the time. But it seems to work. You can derive some mildly interesting results based on the above intuition.
(1) The cost of transforming an arbitrary tree S into a straight line is -- (the no. of pendants in S - 2). Think of this as "tying lose ends" together to form a long thread; a thread has 2 lose ends.
(2) The cost of transforming an arbitrary tree S into a star is -- (n - 1 - the highest node degree in S). Well, you greedily chose the biggest hub and move the rest of the edges to it.

Yes, in any case, the editing cost is O(n). So, the algorithms themselves might not be all that interesting. At least, not as far as trees are concerned.

What might be more interesting is the motivation for this problem, which I'll briefly talk about. The idea is about "flexibility" or "adaptability" in networks. A highly optimized (in terms of efficiency and robustness) yet static network may not always be useful. You may want to be able to "switch" a network from a configuration that is optimal under some circumstances to another which is optimal under changed circumstances. It is desirable that this switch is easy. So, the motivation here is to find topologies that are flexible. One way to measure them is to find this switching cost from a topology to a set of known optimal topologies; by optimizing on the switching cost, we might be able to find the most adaptive topologies.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Hmmm.. if switching costs is what is the main question, then the pertinent question to ask is what is the "lower bound" on the number of edits given any optimal transformation algorithm. For which I don't know the answer.

My response was to find a transformation algorithm itself where the algorithm basically shows how to transform one degree sequence into another and ensuring that the target remains a tree. It does not guarantee optimality or the lowest possible switching cost however.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Sure, my main problem is to minimize the switching cost, but the general problem of transforming graphs might be of some interest independent of this application. So, finding good algorithms to transform an unlabelled graph (not just trees) to another (which might have different number of edges) is still an interesting algorithms exercise, if it is not already solved. Again there are interesting issues there. When do we say that the a graph has transformed to a given target? Isomorphism is one way. Some other measure such as "they both have the same degree sequence" might also make sense. Depending on that we may need different algorithms.

[aditya]

aditya

aditya

Show aditya's last posts.

Show general stats for aditya.

• 
• Administrator
• Jr. Member
• Karma: 8
• Posts: 52

... So, a transformation here is basically a "redistribution of node degrees". In this example, we simply take 5 degrees from the node with a degree of 7 in S and add a degree 1 to 5 of the 7 remaining nodes. The "amount" of degrees redistributed is the cost of transforming from S to T.

How about these two graphs (Drawing them on a paper might help)

Graph 1
a---b
a---c
b---d
c---d
a---e
e---f
f---g
g---h
h---d

Graph 2
a---b
a---c
a---d
b---e
e---f
f---d
c---g
g---h
h---d

Both the graphs have the same degree sets and each node has the same degree but they are not equivalent. So is transforming from one degree set to another using redistribution good enough?

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Well, your examples are not trees; I was essentially talking about trees. But it might be possible to find counterexamples for trees also. Need to prove it one way or the other.

That aside, if by equivalence you mean isomorphism, yes, two non-isomorphic graphs can have the same degree sequence. In fact, two graphs can have a number of properties that are the same but still be non-isomorphic. You may find an old post on my blog interesting in this regard - http://1stprinciples.wordpress.com/2008/03/25/graph-invariants-identifiers-and-reconstruction/

[aditya]

aditya

aditya

Show aditya's last posts.

Show general stats for aditya.

• 
• Administrator
• Jr. Member
• Karma: 8
• Posts: 52

Well, your examples are not trees; I was essentially talking about trees. But it might be possible to find counterexamples for trees also. Need to prove it one way or the other.

Sorry for the silly mistake.

What I wanted to convey was that I can have two trees (unrooted and undirected) with the same degree sets but are not isomorphic. Is that in any way significant? Are you looking only at transforming to pure topologies like Star and Line?

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

Degree sequence cannot uniquely identify a graph. I can't think of an example off the cuff right now; but if it were to be true, graph isomorphism would be very simple to compute.

Re: the general problem of graph transformation, yes it is an interesting problem with several applications. I think the approach to solving that would be to somehow compute graph encodings of both the source and target graphs that makes it easier to determine whether the transformation is complete. For instance, it is easier to compute isomorphism (or detect non-isomorphisms) for labeled graphs and rooted trees/graphs than for unlabelled and unrooted ones.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Aditya:

Those are good questions. Two isomorphic graphs have the same structural properties. But two graphs can be 'functionally' equivalent in some sense like having the same degree or centrality distribution despite being non-isomorphic. Is isomorphism significant? It probably is if adjacency relations are strong. Isomorphism might not be significant in cases where nodes are functionally homogeneous (I think; correct me if I am wrong), such as soldiers in a field and several p2p networks. Functional homogeneity is also the idea behind unlabeled trees -- it doesn't matter who's talking to whom as long as everything is working well.

Indeed, I don't know how well the problem of transforming networks is understood, but I think it is an important problem in several applications. For example, why are er.. terrorist networks robust? The robustness comes from flexibility. Can we use those ideas in building useful networks?

Re using star and straight line, well, it's simply because their properties are well understood. In fact, starting from trees is also because they are easier to deal with.