search

open-connectome-classes / StatConn-Spring-2015-Info

introductory material
18 stars 4 forks source link

Partial Subgraph Matching #207

Open imichaelnorris opened 9 years ago

imichaelnorris commented 9 years ago

In the Seeded Graph Matching (SGM) algorithm that Jason talked about today, the top left blocks in the adjacency matrices A and B were required to both be manually assigned. The permutation matrix has an identity matrix in the top left part because it does not permute this block because everything has already been done there.

What would happen if we had the same partitioning as was presented in class, but only partially assigned the top left blocks of A and B. For instance, what if we predicted that we only got 50% of all matches between block A_1,1 and B_1,1? We can't use SGM yet because it requires the block to be fully matched.

Is there an algorithm that can resolve a partially assigned graph?

Maybe the solution is for SGM to be applied on the top left blocks of A and B first.

DSP137 commented 9 years ago

Just to make sure I understand the question, are you supposing that we did some sort of spot check of the seeds and are sure we got some wrong (namely half of them wrong) but are unsure of which ones those are?

imichaelnorris commented 9 years ago

My intention was if we only assigned half of the edges in the block (so there are 10 edges and I assigned 5 but didn't want to assign the other 5). However, this would be equivalent to saying that the half of edges that were not assigned were incorrectly assigned.