How to search all elements in two cell arrays?

Hi,

I have two cell arrays, each cell in these two arrays represent a connected component in a graph.

 C = {[21,45,87,99,121],[37,918],[150,700],[218,851],[420,728],[464,761],[695,709],16,34}; % Connected components in Graph G
 B = {[4,600,303,5,56,88,87,63],[142,257,481,785],[103,33,509],[99,588],[251,524],[572,683],8,65,105} % Connected components in Graph H

I want to go through each cell in array C and check if it's members (Nodes) connected to other cell's members (nodes) in B.

That is, if the nodes [37,918] in C (in the same component) are connected to the two nodes 251 and 588 in B (different component) remove the edge between 37,918.

I would appreciate your help and tips.

[Christine Tobler]

How are the nodes in the two graphs connected up? Are there edges between the nodes in one graph and the nodes in the other, or is there just a one-on-one mapping from nodes of graph G to nodes of graph H?

[Asaf McRock]

The two graphs are generated using WattsStrogatz and then I added edges from nodes of graph G to nodes of graph H.

[Asaf McRock]

Hi Dr. Tobler,

I forgot to mention that I removed some edges within both graphs after I generted them in order to have different components or clusters. Also, there is no preference in chosing WattsStrogatz; both graphs could be generated based on any method.

[Christine Tobler]

It looks like B and C represent only a subset of the connected components in the graph (not all numbers from 1 to 918 appear here, so the other nodes must be in different components. Correct?

So is each node in B connected to exactly one node in C? If not, does it mean that for nodes [37, 918] in C, you want to go through every pair of nodes x, y in B where x is connected to 37 in C and y is connected to 588 in B, and remove the edge between [37, 918] unless every pair of nodes (x, y) in B is connected by an edge?

On performance, the first thing I would recommend is to try to use the default output from conncomp, which is a vector bins where bins(i) gives the component that node i is in. It's much faster to check whether two nodes are in the same component using bins(i) == bins(j) than using the cell array output.

Answer 1

[Christine Tobler]

All right, let's assume you have a graph containing both G and H stored as graph object GH, and that this graph contains the black and red edges from your picture, but not the purple ones which are just the mapping between G and H.

I'll also assume you have a vector which mapGH which maps between those two sets of points (that's the purple lines): mapGH(i) == j and mapGH(j) == i, where i is a node in G and j is its corresponding node in H.

Am I right to assume these inputs are available?

Then, we can find all edges to remove as follows:

bins = conncomp(GH);
[s, t] = findedge(GH); % list start and end nodes of all edges in GH
st = [s, t];
% We know bins(s) == bins(t), because two nodes connected by an edge are always in the same component.
% Check if their mapped edges are also in the same component:
needRemoveEdge = bins(mapGH(s)) ~= bins(mapGH(t));
GH = rmedge(GH, find(needRemoveEdge));

This removes all edges where the mapped nodes aren't in the same component of the other graph. But removing these edges will change the connected components, so it's probably a good idea to do this several times (stages), until there are no edges that have to be removed:

bins = conncomp(GH);
[s, t] = findedge(GH); % list start and end nodes of all edges in GH
st = [s, t];
% We know bins(s) == bins(t), because two nodes connected by an edge are always in the same component.
% Check if their mapped edges are also in the same component:
needRemoveEdge = bins(mapGH(s)) ~= bins(mapGH(t));
while any(needRemoveEdge)
    GH = rmedge(GH, find(needRemoveEdge));
    bins = conncomp(GH);
    [s, t] = findedge(GH); % list start and end nodes of all edges in GH
    st = [s, t];
    % We know bins(s) == bins(t), because two nodes connected by an edge are always in the same component.
    % Check if their mapped edges are also in the same component:
    needRemoveEdge = bins(mapGH(s)) ~= bins(mapGH(t));
end

This will never be an infinite loop because every iteration removes at least one edge from GH.

Keep in mind I haven't tested this because I don't have time to write up example inputs right now. Can you try it and let me know if it works? If not, could you include some example data for GH and mapGH?

[Asaf McRock]

Thank you so much Doctor.

Below is some example data for GH and mapGH:

G = WattsStrogatz(10,2,.2);
H = WattsStrogatz(10,2,.2);
N = numnodes(G);
GH = graph([G.Edges{:,:}(:,1),H.Edges{:,:}(:,1)+N],[G.Edges{:,:}(:,2),H.Edges{:,:}(:,2)+N]);
idxG = randperm(N,N);
idxH = N+1:N+N;
mapGH = zeros(1, N);
mapGH(idxG) = idxH;
mapGH(idxH) = idxG ;

Is that what you meant by saying "G and H stored as graph object GH"? I hope that I created the row vector mapGH correctly.

I also removed two nodes from graph GH, one node from G and the other is it's corresponding node in H before running your code, just to break down the giant component in graph GH into number of connected components.

[Asaf McRock]

I think once we store the edges of both graphs in one graph object, it would be impossible to perform what I was looking for.

Anyways, thank you so much Dr. Tobler for your help and time. I really admire your beautiful mind. God bless you.

[Asaf McRock]

Hi Dr. Tobler,

I know that this question has been answered by you several months ago, but I have one question please and I would appreciate your help. Is it expected to have a big number of stages if my two graphs have larger number of nodes, say 10000 nodes? I'm getting only 7 stages when I tested this code for large number of nodes. I have concern that I should get like 50-100 stages for larger no. of nodes.

Thanks