how to find neighbors/degree of hyperedges of a uniform hypergraph?

I have data set of 10 uniform hyperedges:

T=[1 6 12; 2 6 13; 3 7 12; 4 7 14; 4 7 15; 1 8 16; 2 9 16; 4 8 17; 5 10 13; 1 11 18];

Now, I have to find degree and neighbors of hyperedge. For ex. first edge (1 6 12) have degree 4 and neighbors are hyperedge 2,3,6,10.

I made this code but it is computationally expensive for large data set.

Can we use another approach whose complexity is linear?

T=[1 6 12; 2 6 13; 3 7 12; 4 7 14; 4 7 15; 1 8 16; 2 9 16;  4 8 17; 5 10 13; 1 11 18];
[A,B,C]=deal(T(:,1),T(:,2),T(:,3));
for i=1:size(T,1)
     p=T(i,:);
     [a,b,c]=deal(p(1),p(2),p(3));                                                                                          
     D=[];
     %to find degree(da) by searching adjacent hyperedges of p in T
     D=[D,find(A'==a)];      
     D=[D,find(B'==b)];
     D=[D,find(C'==c)];
     D=unique(D);
     da=[da,size(D,2)-1];
end

Answer 1

[Christine Tobler]

MATLAB doesn't support hypergraphs, but often a specific problem can be solved with just a graph or multigraph, by interpreting the hyperedges as additional nodes. In this case, we can construct a simple graph where each node represents a hyperedge of the hypergraph, and there is an edge connecting any pair of nodes of the respective hyperedges share a node:

T=[1 6 12; 2 6 13; 3 7 12; 4 7 14; 4 7 15; 1 8 16; 2 9 16;  4 8 17; 5 10 13; 1 11 18];

% Matrix M where M(i, j) = 1 if hyperedge i contains node j.
M = sparse(repmat((1:10)', 1, 3), T, 1);

% Matrix A where A(i, j) >= 1 if hyperedges i and j share at least one node.
A = M*M';

% Make a graph where each node represents a hyperedge
g = graph(M*M', 'omitselfloops');
plot(g)

% Neighbors of hyperedge 1, as expected:
neighbors(g, 1)'

ans = 1×4

2 3 6 10

% Degree of each hyperedge, corresponds to da in original post
degree(g)'

ans = 1×10

4 3 3 3 3 4 2 3 1 2

% By the way, to make a plot of the hypergraph (not just the reinterpration
% above), make a graph where the first 10 nodes represent the hyperedges,
% and the following 18 nodes represent the nodes.
g = graph([sparse(10, 10), M; M', sparse(18, 18)]);

% Then, plot and turn off the markers on the hyperedges:
p = plot(g);
highlight(p, 1:10, Marker="none", NodeLabelColor=[0 0.8 0])

[Urvashi]

thanks for answering, it really works.

I tried to convert this code on second type of data set:

T=[0 0 0; 0 1 1; 1 0 2; 2 2 2; 3 2 3; 4 3 0; 4 4 4; 5 3 5];

this is the hypergraph where each partition have vertices from 0 to size(T)-1.

I am facing some problem in sparse matrix, Is this work on this data type?

[Christine Tobler]

This appears to be zero-based, MATLAB uses 1-based indexing. Setting T = T+1 may solve your problem.

[Urvashi]

I used +1 thing but the problem is that resulted Matrix entries is not unique w.r.t each column. So M has 8*6 dimension, and it isn't the desired matrix. To solve this problem, I thought to convert t into

T=[1 7 11; 1 8 12; 2 7 13; 3 9 13; 4 9 14; 5 10 11; 5 11 15; 6 10 16] By checking each column of t (row wise) and respectively give unique entries to T, but this will take 2 loops and several steps for checking.

Can we do it through vectorization? to reduce complexity.

Or can this be done through other approach?

[Christine Tobler]

Sorry, I didn't look at the matrix T carefully enough initially - I hadn't noticed that it has multiple identical nodes in some of the hyperedges.

The code above will treat this as being a hyperedge that only connects to each node once - am I right to assume you would like this to be treated as still a hyperedge with 3 nodes? That is, the hyperedge [1 1 1] will mean the degree of node 1 is 3?

Say I have a set of hyperedges defined by T = [1 1 1; 1 1 2], what would the degree of these hyperedges be? Do they both have degree 6, because there are 6 combinations of moving from hyperedge 1 through node 1 to hyperedge 2? Or just degree 1, because there is only 1 unique hyperedge that is their direct neighbor?

If what you are looking for in the above example is degree 6, I believe the following modification of the code above will work:

T=[0 0 0; 0 1 1; 1 0 2; 2 2 2; 3 2 3; 4 3 0; 4 4 4; 5 3 5] + 1;
e = size(T, 1);
% Matrix M where M(i, j) = 1 if hyperedge i contains node j.
M = sparse(repmat((1:e)', 1, size(T, 2)), T, 1);
% Matrix A where A(i, j) >= 1 if hyperedges i and j share at least one node.
A = M*M';
% Make a graph where each node represents a hyperedge
g = graph(M*M', 'omitselfloops');
plot(g, EdgeLabel=g.Edges.Weight) % weights show number of connections

degreeCountingMultiples = full(sum(adjacency(g, 'weighted')))

degreeCountingMultiples = 1×8

9 7 11 6 8 11 3 3

And here's again a plot that shows both the nodes and the hyperedges of this graph

n = size(M, 2); % number of nodes
gBoth = graph(repmat((1:e)', 1, size(T, 2))+n, T);

% Then, plot and turn off the markers on the hyperedges:
p = plot(gBoth);
highlight(p, n+1:n+e, Marker="none", NodeLabelColor=[0 0.8 0])
labelnode(p, n+1:n+e, 1:e)