Math Is Fun Forum

h0cked

Member

Registered: 2011-07-15

Posts: 1

Is this a linear programming problem?

I have been pulling my hair out on one problem... The overall problem is complicated... but let me try my best to explain the part that really matters...

I have a graph where each edge represents the correlation between the connected two nodes. Each node is a time course (TC) (i.e., 400 time points), where events will occur at different time points. The correlation between two nodes is defined as the percentage of overlapped events. For the simplicity of this example, let us assume that the total number of events happening on each node is the same as $tn$. And if two TCs (nodes) have $on$ overlapped events (i.e., events that happened at exactly the same time point). Then, the correlation can be defined simply as $on$/$tn$.

Now, I have a network of 11 nodes; and I know the correlation between every two nodes. How do I generate the TCs for all 11 nodes that meet the correlation constraints???

It is easy to do this for two nodes when you know the correlation between the two. Assume TC_1 and TC_2 have a correlation value of 0.6, which means there are 60 percent overlapped events in two TCs. Also, assume that the total number of events are the same for both TC_1 and TC_2 as $tn$. A simple algorithm to place the events in the two TCs is first randomly pick 0.6$tn$ time points, and consider those as time slots where overlapped events happened in both TCs. Next, randomly pick (1-0.6)$tn$ time points in TC_1 to place the rest of the events for TC_1. Finally, randomly pick (1-0.6)*$tn$ time points in TC_2 where no events happened in correspondent time points in TC_1.

However, it starts to get harder, when you consider a 3-node network, where the generated three TCs need to meet all three correlation constraints (i.e., 3 edges)... It's hardly possible to do this for a 11-node network...

Does this make any sense to you? Please let me know if it's not...

I was thinking that this is just a trick computer science programing issue... but the more I think about it, it's more like a linear programing problem, isn't it?

Anyone has a reasonable solution? I am doing this in R, but any code is ok...