finding degree and neighbor of each vertex in a subgraph H but indexing according to original graph

I have a graph G with vertex set V=[1:10];

s=[1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6];

t=[2, 3, 6, 10, 7, 9, 4, 5, 5, 8, 8, 7, 8, 10];

G=graph(s,t);

G.Nodes.Name=string(1:numnodes(g))';

I want to find degree and neighbor of each vertex of a subset of V i.e., S=[1,2,3,4,5,6,8];

H=subgraph(G,S);

when computing neighbors, I want that neighbor index should be according to original graph G. For ex:

plot(H) %it plot H correctly

neighbors(H, 6)'

it returns value 1,7 and I want 1,8 acc to G

Answer 1

[Dyuman Joshi]

The output you get is the index of nodes which are neighbors to the input and not the name of the node.

And the input to the function is the index of the node, not the Node name.

V = 1:10;
s = [1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6];
t = [2, 3, 6, 10, 7, 9, 4, 5, 5, 8, 8, 7, 8, 10];
G = graph(s,t);
G.Nodes.Name=string(1:numnodes(G))';
figure
S=[1,2,3,4,5,6,8];
H=subgraph(G,S);
H.Nodes

ans = 7×1 table
    Name 
    _____

    {'1'}
    {'2'}
    {'3'}
    {'4'}
    {'5'}
    {'6'}
    {'8'}

plot(H)

%Indices of neighbors of the 6th node
z1=neighbors(H, 6)'

z1 = 1×2

1 7

%Access the names of the neighbors of the 6th node
H.Nodes(z1,:)

ans = 2×1 table
    Name 
    _____

    {'1'}
    {'8'}

Another case -

%Indices of neighbors of the 4th node
z2=neighbors(H,4)'

z2 = 1×3

3 5 7

You can observe that here that the output, as mentioned above, is the indices, meaning that the 3rd, 5th and 7th node of the graphs are neighbors to the 4th node of the graph.

You will have to access the names via indexing as done below -

%Name of the neighbors of the 7th node
H.Nodes(z2,:)

ans = 3×1 table
    Name 
    _____

    {'3'}
    {'5'}
    {'8'}

%If you try to get the neighbor of 8th node under the assumption that name
%of the node is the input, you will get an error
z3=neighbors(H,8)'

Error using graph/validateNodeID
Numeric node IDs must be positive integers not greater than the number of nodes in the graph (7).

Error in graph/neighbors (line 17)
id = validateNodeID(G, nodeid);

It can be referred from the error what the expected input is.

H.Nodes(z3,:)

Answer 2

[Christine Tobler]

I think the easiest will be to build on what you started by giving the nodes in graph G names which are just the string version of their numbers.

% This block is just your code from above, so I can use the variables later on.
s=[1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6];
t=[2, 3, 6, 10, 7, 9, 4, 5, 5, 8, 8, 7, 8, 10];
G=graph(s,t);
G.Nodes.Name=string(1:numnodes(G))';
% I want to find degree and neighbor of each vertex of a subset of V i.e., 
S=[1,2,3,4,5,6,8];
H=subgraph(G,S);
% when computing neighbors, I want that neighbor index should be according to original graph G. For ex:
plot(H)   %it plot H correctly 

neighbors(H, 6)'   %it returns value 1,7 and I want 1,8 acc to G

ans = 1×2

1 7

H.Nodes

ans = 7×1 table
    Name 
    _____

    {'1'}
    {'2'}
    {'3'}
    {'4'}
    {'5'}
    {'6'}
    {'8'}

In graph H, node 7 has name "8". The number 7 is just counting up all nodes in H, while the name "8" is the index from graph G. So you can call neighbors with either of these, depending on whether you put the input in quotations:

neighbors(H, "6")'

ans = 1×2 string array
    "1"    "8"

neighbors(H, "8")'

ans = 1×3 string array
    "4"    "5"    "6"

If you need to convert between numbers and strings containing numbers, you can use:

num = 8;
string(num)

ans = "8"

str = "3";
double(str)

ans = 3

All this should be fine for smaller graphs, for very large graphs the conversion to/from string might slow you down. Let me know if this is your case, I can add some (less compact) code for that case.

[Urvashi]

yes it works on small graphs very well but I have vertex set around 56000, please guide me with large graph varient.

[Dyuman Joshi]

@Urvashi - Did you try the above answer(s) on your data?

If not, why not? If yes, then what is the problem you are facing?

[Christine Tobler]

All right, here's a variant that uses a numeric array of indexes instead of strings containing numbers. This should be more efficient, but is also less intuitive, as you need to be careful to distinguish between an index into the original graph and its projection into the subgraph.

% This block is just your code from above, so I can use the variables later on.
s=[1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6];
t=[2, 3, 6, 10, 7, 9, 4, 5, 5, 8, 8, 7, 8, 10];
G=graph(s,t);
G.Nodes.ID=(1:numnodes(G))'; % Set a different variable name than Name, which must be string
plot(G)

% I want to find degree and neighbor of each vertex of a subset of V i.e., 
S=[1,2,3,4,5,6,8];
H=subgraph(G,S);
h2g = H.Nodes.ID; % h2g(i) tells us the node id of node i in H, in the original graph G.
g2h = zeros(1, numnodes(G));
g2h(h2g) = 1:numnodes(H); % g2h is the reverse transformation.
g2h

g2h = 1×10

1 2 3 4 5 6 0 7 0 0

% If node i in G is part of 
% when computing neighbors, I want that neighbor index should be according to original graph G. For ex:
plot(H, NodeLabel=string(h2g))   %it plot H correctly 

h2g(neighbors(H, g2h(6)))   %it returns value 1,7 and I want 1,8 acc to G

ans = 2×1

1 8

H.Nodes

ans = 7×1 table
    ID
    __

    1 
    2 
    3 
    4 
    5 
    6 
    8 

In graph H, node 7 is what was node 8 in graph G. The number 7 is just counting up all nodes in H, while the number 8 is the index from graph G. So when you call neighbors on H using the indexes from G, you need to (a) transform the input from indexing into G to indexing into H and (b) transform the output from node IDs in H to node IDs in G:

h2g(neighbors(H, g2h(8)))

ans = 3×1

4 5 6

Please let me know if this improves speed for your cases of large graphs.