MATLAB Answers

How to group connected pairs

조회 수: 2(최근 30일)
Genevieve
Genevieve 2014년 8월 11일
댓글: Genevieve 2014년 8월 11일
Hi, I have a serie of recording instruments and I compute the correlation between the measurements of each instrument pair. This gives a square upper-triangular matrix of correlation coefficients (call it "cc"). I want to select the instruments that corresponds to correlation coefficients over some threshold "T".
[ir,ic]=find(cc>T);
This gives the row and column index of all the pairs of instrument that satisfy my condition. However, I want to add a consistency constraint, namely, I want to identify only the "connected pairs". For example, if I have the pairs (1,2), (2,3), (5,8),(8,10),(8,11),(11,6), (14,15), then I have the following groups of connected instruments: [1,2,3], [5,6,8,10,11] and [14,15].
I tried something like this, as a start:
pp=[ir,ic];
ccpairs=zeros(length(ir),length(ir));
for ip1=1:size(pp,1)-1
for ip2=ip1+1:size(pp,1)
if ~isempty(intersect(pp(ip1,:),pp(ip2,:)))
ccpairs(ip1,ip2)=1
end
end
end
However, if I have more than 1 group with more than 2 connected instruments, then I would need to set ccpairs(ip1,ip2) to a different index so I can identify the groups. This double for loop is also very slow for the number of pairs I usually get (>100).
Does anybody have an idea of how to do this efficiently?

채택된 답변

Kelly Kearney
Kelly Kearney 2014년 8월 11일
There are several graph theory-related entries on the FEX that provide connected components algorithms. This one is a nice, self-contained version that I've used before.
% Example data
sub = [1 2; 2 3; 5 8; 8 10; 8 11; 11 6; 14 15];
ir = sub(:,1);
ic = sub(:,2);
% Find the connected components
nval = length(ir);
nnode = max([ir; ic]);
adj = sparse(ir, ic, ones(nval,1), nnode, nnode);
lbl = graph_connected_components(adj);
grp = accumarray(lbl', (1:nnode)', [max(lbl) 1], @(x) {x});
  댓글 수: 1
Genevieve
Genevieve 2014년 8월 11일
Elegant solution. It does exactly what I need. Thank you very much!

댓글을 달려면 로그인하십시오.

추가 답변(0개)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by